Следующий текст — вклад в предысторию квантового вычисления. Это последние три параграфа введения в [Ma2] (1980). За эту ссылку я благодарен А. Китаеву [Ki].
«Может быть, для лучшего понимания этого явления [репликации ДНК] нам нужна математическая теория квантовых автоматов. Такая теория дала бы нам математические модели детерминированных процессов с совершенно необычными свойствами. Один из доводов в пользу этого — то, что квантовое пространство состояний имеет гораздо большую емкость, чем классическое: для классической системы с $N$ состояниями ее квантовый аналог, допускающий суперпозицию, насчитывает $c^N$ состояний. Когда мы соединяем две классических системы, количества их состояний $N_1$ и $N_2$ перемножаются, а в квантовом случае мы получаем экспоненциальный рост $c^{N_1{N}_2}$.

Эти грубые оценки показывают, что квантовое поведение системы может быть гораздо более сложным, чем его классическое моделирование. В частности, поскольку нет единственного разложения квантовой системы на ее составляющие части, состояние квантового автомата может быть многими способами представлено в виде состояния разных виртуальных классических автоматов. Ср. следующий инструктивный комментарий в конце статьи [Ро]: «Квантовомеханическое вычисление одной молекулы метана требует ${10}^{42}$ точек сетки. Предполагая, что в каждой точке нам надо выполнить только 10 элементарных операций и что вычисление выполняется при крайне низкой температуре $T=3\cdot {10}^{-3}K$, нам все еще потребуется вся энергия, произведенная на Земле за последнее столетие.»

Первую трудность, которую мы должны преодолеть — выбор правильного баланса между математическими и физическими принципами. Квантовый автомат должен быть абстрактным: его математическая модель должна использовать только общие принципы квантовой физики, без описания физической реализации. Тогда модель эволюции унитарное вращение в конечномерном гильбертовом пространстве, а разложение системы на ее виртуальные части соответствует тензорному произведению пространства состояний. Где-то в этой картине мы должны разместить взаимодействие, которое описано матрицами плотности и вероятностями.»