Любая существующая общая модель вычислений — эффективно классическая. Это означает, что полное описание ее состояния в каждый момент эквивалентно определению множества чисел, все эти числа в принципе измеримы. Однако, квантовая теория утверждает, что систем с таким свойством не существует. Тот факт, что классическая физика и классическая универсальная машина Тьюринга не обеспечивают принципа Чёрча-Тьюринга в строгой физической форме (1.2) — одна из мотиваций поиска истинно квантовой модели. Более настоятельная мотивация, конечно, то, что классическая физика ложна.

Бенёв (1982) построил модель вычисления в рамках квантовой кинематики и динамики, но все еще эффективно классическую в вышеупомянутом смысле. Она построена так, что в конце каждого элементарного шага вычислений ни одно из характерных квантовых свойств интерференция, неразличимость, неопределенность — не обнаруживается. Ее вычисление может быть полностью моделировано машиной Тьюринга.

Фейнман (1982) подошел еще на один шаг к настоящему квантовому компьютеру с его «универсальным квантовым имитатором» (universal quantum simulator). Он состоит из решетки спиновых систем с взаимодействиями ближайших соседей. Хотя квантовый имитатор может с уверенностью моделировать любую систему с конечным пространством состояний (я не понимаю, почему Фейнман сомневается, что он может моделировать систему фермионов), он не является вычислительной машиной в смысле этой статьи. «Программирование» имитатора
${ }^{1}$ Кто будет стеречь самих сторожей? (Прим. ред.)
состоит в настройке его в соответствии с желаемыми динамическими законами и затем в приведении его в требуемое начальное состояние. Но механизм, который позволяет выбрать произвольные динамические законы, не моделируется. Динамика настоящего «компьютера» в моем смысле должна быть зафиксирована раз и навсегда, а программирование должно состоять целиком в подготовке его в подходящее состояние (или смешанный случай).

Альберт (Albert) (1983) описал квантово-механический измерительный «автомат» и заметил, что его свойство измерять самого себя не имеет аналогов среди классических автоматов. Автоматы Альберта, хотя и не являются вычислительными машинами общего назначения, суть настоящие квантовые компьютеры, члены некоторого общего класса, который я буду изучать в этом разделе.

Здесь будет представлена общая, полностью квантовая модель вычислений. Затем я опишу универсальный квантовый компьютер $\mathcal{Q}$, который может полностью моделировать любую конечную реализуемую систему. Он может моделировать идеальные замкнутые (при нулевой температуре) системы, включая все другие примеры квантовых компьютеров и квантовых имитаторов с произвольно высокой, но не полной точностью. Для вычисления определенных функций из $\mathbb{Z}$ в $\mathbb{Z}$ он генерирует в точности классические рекурсивные функции $C(\mathcal{T})$ (проявление принципа эквивалентности). В отличие от $\mathcal{T}$ он может моделировать любое конечное классическое свойство дискретного случайного процесса. Более того, как мы увидим в $§ 3$, у него есть много замечательных возможностей, которые не имеют классических аналогов.

Как и машина Тьюринга, модель квантового компьютера $\mathcal{Q}$ содержит две части: конечный процессор и бесконечную память, из которой в каждый момент используется только конечная часть. Вычисление заключается в выполнении шагов фиксированной длительности $T$, и на протяжении каждого шага взаимодействуют только процессор и конечная часть памяти, остальная память остается статичной.
Процессор состоит из $M$ наблюдаемых с двумя состояниями
\[
\left\{\widehat{n}_{i}\right\} \quad\left(i \in \mathbb{Z}_{M}\right),
\]

где $\mathbb{Z}_{M}$ — множество целых чисел от 0 до $M-1$. Память состоит из
бесконечной последовательности
\[
\left\{\widehat{m}_{i}\right\} \quad(i \in \mathbb{Z})
\]

наблюдаемых с двумя состояниями. Это соответствует бесконечно длинной «ленте» памяти в машине Тьюринга. Я буду обозначать $\left\{\widehat{n}_{i}\right\}$ в целом как $\widehat{\boldsymbol{n}}$, а $\left\{\widehat{m}_{i}\right\}$ — как $\widehat{\boldsymbol{m}}$. Положению ленты машины Тьюринга соответствует наблюдаемая $\widehat{x}$, спектр которой образует все множество $\mathbb{Z}$. Наблюдаемая $\widehat{x}$ «адресует» номер места ленты, сканируемого в настоящий момент. Поскольку «лента» — бесконечно длинная, но находится в движении на протяжении вычислений, она не должна быть жесткой или ее нельзя заставить двигаться «конечным способом». Механизм, который движет ленту в соответствии с сигналами, передаваемыми с конечной скоростью только между смежными сегментами, должен удовлетворять требованию «конечности средств» и должен быть способен выполнить то, что описано далее. Удовлетворившись тем, что такой механизм возможен, мы не нуждаемся в том, чтобы моделировать его явно. Таким образом, состояние $\mathcal{Q}$ — единичный вектор в пространстве $\mathscr{H}$, натянутом на общие собственные вектора
\[
|x ; \boldsymbol{n}, \boldsymbol{m}\rangle \equiv\left|x ; n_{0}, n_{1}, \ldots, n_{M-1} ; \ldots, m_{-1}, m_{0}, m_{1}, \ldots\right\rangle
\]

величин $\widehat{x}, \widehat{\boldsymbol{n}}, \widehat{\boldsymbol{m}}$, помеченные соответствующими собственными значениями $x, \boldsymbol{n}, \boldsymbol{m}$. Я называю (2.3) «состояниями вычислительного базиса». Удобно считать, что спектр наших наблюдаемых величин с двумя состояниями $-\mathbb{Z}_{2}$, т. е. множество $\{0,1\}$, а не $\left\{-\frac{1}{2},+\frac{1}{2}\right\}$, как это обычно считается в физике. Наблюдаемая величина со спектром $\{0,1\}$ имеет естественную интерпретацию как однобитовый элемент памяти.

Динамика $\mathcal{Q}$ определяется в общем унитарным оператором $\mathrm{U}$ на $\mathscr{H}$. Оператор U описывает эволюцию любого состояния $|\Psi(t)\rangle \in \mathscr{H}$ (в картине Шредингера во время $t$ ) на протяжении одного шага вычисления,
\[
\begin{array}{c}
|\Psi(n T)\rangle=\mathrm{U}^{n}|\Psi(0)\rangle \quad\left(n \in \mathbb{Z}^{+}\right), \\
\mathrm{U}^{\dagger} \mathrm{U}=\mathrm{UU}^{\dagger}=\widehat{1} .
\end{array}
\]

Нам не нужно определять состояние в моменты времени, отличные от неотрицательных целых кратных $T$. Вычисление начинается в $t=0$. В

этот момент времени $\widehat{x}$ и $\widehat{n}$ готовятся с нулевым значением, состояние конечного числа элементов $\widehat{\boldsymbol{m}}$ готовится как «программа» и «вход» в смысле $\S 1$, а оставшиеся элементы устанавливаются в нулевые состояния. Таким образом,
\[
\left.\begin{array}{c}
|\Psi(0)\rangle=\sum_{m} \lambda_{m}|0 ; 0 ; \boldsymbol{m}\rangle, \\
\sum_{m}\left|\lambda_{m}\right|^{2}=1,
\end{array}\right\}
\]

где только конечное число $\lambda_{m}$ — ненулевые и $\lambda_{m}$ становятся нулевыми, как только бесконечное число $\boldsymbol{m}$ становится ненулевым.

Чтобы удовлетворить тому требованию, что $\mathcal{Q}$ действует «конечным образом», элементы матрицы U берутся в форме:
\[
\begin{array}{l}
\left\langle x^{\prime} ; \boldsymbol{n}^{\prime} ; \boldsymbol{m}^{\prime}|\mathrm{U}| x ; \boldsymbol{n} ; \boldsymbol{m}\right\rangle= \\
\quad=\left[\delta_{x^{\prime}}^{x+1} \mathrm{U}^{+}\left(\boldsymbol{n}^{\prime}, m_{x}^{\prime} \mid \boldsymbol{n} m_{x}\right)+\delta_{x^{\prime}}^{x-1} \mathrm{U}^{-}\left(\boldsymbol{n}^{\prime}, m_{x}^{\prime} \mid \boldsymbol{n}, m_{x}\right)\right] \prod_{y
eq x} \delta_{m_{y}^{\prime}}^{m_{y}} .
\end{array}
\]

Бесконечное произведение в правой части обеспечивает то, что только один, $x$-й, бит памяти участвует в вычислении. Члены $\delta_{x^{\prime}}^{x \pm 1}$ обеспечивают то, что на протяжении каждого шага позиция ленты $x$ не может измениться более чем на единицу вперед или назад, или в обе стороны. Функции $\mathrm{U}^{ \pm}\left(\boldsymbol{n}^{\prime} m^{\prime} \mid \boldsymbol{n} m\right)$, которые представляют динамическое движение, зависящее только от «локальных» наблюдаемых величин $\widehat{\boldsymbol{n}}$ и $\widehat{m}_{x}$, произвольны за исключением требований (2.5), что $\mathrm{U}$ — унитарный оператор. Каждый выбор определяет новый квантовый компьютер $\mathcal{Q}\left[\mathrm{U}^{+}, \mathrm{U}^{-}\right]$.

Говорят, что машина Тьюринга «останавливается», сообщая о конце вычисления, когда два последовательных состояния идентичны. «Правильной» называется программа, вызывающая остановку машины после конечного числа шагов. Тем не менее, (2.4) показывает, что два последовательных состояния квантового компьютера $\mathcal{Q}$ никогда не могут совпасть после нетривиального вычисления. (Это верно для любого обратимого компьютера.)

Более того, $\mathcal{Q}$ не должен наблюдаться до того, как вычисление закончится, поскольку это в общем случае изменило бы его соответствующее состояние. Поэтому требуется, чтобы квантовые компьютеры активно сигнализировали о том, что они останавливаются. Для этой цели должен быть выбран один из внутренних битов процессора, например $\widehat{n}_{0}$. Каждая правильная $\mathcal{Q}$-программа устанавливает $n_{0}$ в 1 , когда она останавливается, и не взаимодействует с $\widehat{n}_{0}$ в других случаях. Тогда наблюдаемая $\widehat{n}_{0}$ может периодически наблюдаться извне без влияния на действие $\mathcal{Q}$. Аналог классического условия о правильности программы может заключаться в том, что математическое ожидание значения $\widehat{n}_{0}$ должно перейти в единицу за конечное время. Тем не менее, физически разумно разрешить более широкий класс $\mathcal{Q}$-программ. $\mathcal{Q}$-программа правильна, если математическое ожидание ее времени работы конечно.

По причине унитарности динамика $\mathcal{Q}$, как динамика любой квантовой системы, необходимо обратима. С другой стороны, машины Тьюринга совершают необратимые изменения в процессе вычислений и до недавнего времени действительно был широко распространен взгляд, согласно которому необратимость — существенная черта вычисления. Тем не менее, Беннетт (1973) доказал, что это не так, явно построив обратимую классическую модель вычислительной машины, эквивалентную (т.е. порождающую те же вычислимые функции) $\mathcal{T}$ (см. также Тоффоли (Toffoli), 1979). (Машины Бенёва эквивалентны машинам Беннетта, но используют квантовую динамику.)

Квантовые компьютеры $\mathcal{Q}\left[\mathrm{U}^{+}, \mathrm{U}^{-}\right]$, эквивалентные любой обратимой машине Тьюринга, можно получить, приняв
\[
\mathrm{U}^{ \pm}\left(\boldsymbol{n}^{\prime}, m^{\prime} \mid \boldsymbol{n}, m\right)=\frac{1}{2} \delta_{n^{\prime}}^{A(n, m)} \delta_{m^{\prime}}^{B(n, m)}[1 \pm C(\boldsymbol{n}, m)],
\]

где $A, B, C-$ функции со значениями $\left(\mathbb{Z}_{2}\right)^{M}, \mathbb{Z}_{2}$ и $\{-1,1\}$, соответственно. Другими словами, машины Тьюринга — это те квантовые компьютеры, динамика которых обеспечивает то, что они остаются в основных вычислительных состояниях в конце каждого шага, если они стартуют в основном состоянии. Чтобы обеспечить унитарность, необходимо и достаточно, чтобы отображение
\[
\{(\boldsymbol{n}, m)\} \Longleftrightarrow\{(\boldsymbol{A}(\boldsymbol{n}, m), B(\boldsymbol{n}, m), C(\boldsymbol{n}, m))\}
\]

было бы биективно. Поскольку составляющие функции $A, B, C$ в
остальном произвольны, должны, в частности, существовать варианты, которые делают $\mathcal{Q}$ эквивалентным универсальной машине Тьюринга $\mathcal{T}$.

Описать универсальный квантовый компьютер $\mathcal{Q}$ непосредственно в терминах его составляющих преобразований $\mathrm{U}^{ \pm}$можно, но неоправданно утомительно. Свойства $\mathcal{Q}$ лучше определить с помощью перехода к описанию более высокого уровня, оставляя явное построение $\mathrm{U}^{ \pm}$ в качестве упражнения для читателя. Далее я несколько раз буду использовать свойство «универсальности» $\mathcal{T}$.

Для любой рекурсивной функции $f$ существует программа $\pi(f)$ для $\mathcal{T}$ такая, что если за образом $\pi(f)$ следует образ любого целого $i$ на входе $\mathcal{T}$, то $\mathcal{T}$ останавливается на $\pi(f)$ и $i$ на выходе, за которыми следует образ $f(i)$, а все другие биты по-прежнему (или снова) установлены в нуль. Т.е. для некоторого положительного целого числа $n$
\[
\mathrm{U}^{n}|0 ; \mathbf{0} ; \pi(f), i, \mathbf{0}\rangle=|0 ; 1, \mathbf{0} ; \pi(f), i, f(i), \mathbf{0}\rangle .
\]

Здесь 0 означает последовательность нулей, а нулевые собственные значения $\widehat{m}_{i}(i<0)$ не показаны явно. $\mathcal{T}$ не теряет общности, если требуется, чтобы каждая программа распределяла память как бесконечную последовательность ячеек, в каждой из которых может содержать произвольное целое число. (Например, $a$-я ячейка могла бы состоять из битов, помеченных последовательными степенями $a$-го простого числа.) Для каждой рекурсивной функции $f$ и целых чисел $a$ и $b$ существует программа $\pi(f, a, b)$, которая вычисляет функцию $f$ на содержимом ячейки $a$ и помещает результат в ячейку $b$, оставляя ячейку $a$ без изменения. Если ячейка $b$ первоначально не содержала нуля, то обратимость требует, чтобы ее старое значение не забивалось, а комбинировалось некоторым обратимым способом со значением функции. Таким образом, опуская явное упоминание всех излишних подробностей, мы можем представить действия программы $\pi$ с помощью диаграммы:
где $\oplus$ — любая ассоциативная, коммутативная операция со свойствами:
\[
\left.\begin{array}{c}
i \oplus i=0, \\
i \oplus 0=i,
\end{array}\right\}
\]
(подходит, например, функция «исключающее или»). Через $\pi_{1} \cdot \pi_{2}$ я обозначаю сцепление двух программ $\pi_{1}$ и $\pi_{2}$, которое всегда существует, если $\pi_{1}$ и $\pi_{2}$ — правильные программы; $\pi_{1} \cdot \pi_{2}$ — программа, действие которой есть действие $\pi_{1}$, за которым следует действие $\pi_{2}$.

Для любой биективной рекурсивной функции $g$ существует программа $\Phi(g, a)$, единственное действие которой — заменить любое целое $i$ в ячейке $a$ на $g(i)$. Доказательство получить нетрудно, поскольку если некоторая ячейка начально содержит нуль, то
\[
\Phi(g, a)=\pi(g, a, b) \cdot \pi\left(g^{-1}, b, a\right) \cdot \pi(I, b, a) \cdot \pi(I, a, b) .
\]

Здесь $I$ — функция «полного измерения» (Дойч 1985)
\[
|\pi(I, 2,3), i, j\rangle \rightarrow|\pi(I, 2,3), i, j \oplus i\rangle .
\]

Универсальный компьютер $\mathcal{Q}$ имеет все только что описанные свойства $\mathcal{T}$, как указано в (2.10) и (2.14). Но $\mathcal{Q}$ допускает также и класс программ, которые преобразуют базисные состояния в их линейные суперпозиции.

Все программы для $\mathcal{Q}$ могут быть выражены в терминах обычных тьюринговых операций и в точности восьми добавочных операций. Это — унитарные преобразования, ограниченные на простое двумерное гильбертово пространство $\mathscr{K}$, пространство состояний одного бита. Эти преобразования образуют семейство с четырьмя (вещественными) параметрами. Пусть $\alpha$ — любое иррациональное кратное $\pi$. Тогда четыре преобразования
\[
\left.\begin{array}{ll}
V_{0}=\left[\begin{array}{cc}
\cos \alpha & \sin \alpha \\
-\sin \alpha & \cos \alpha
\end{array}\right], & V_{1}=\left[\begin{array}{cc}
\cos \alpha & i \sin \alpha \\
i \sin \alpha & \cos \alpha
\end{array}\right], \\
V_{2}=\left[\begin{array}{cc}
e^{i \alpha} & 0 \\
0 & 1
\end{array}\right], & V_{3}=\left[\begin{array}{cc}
1 & 0 \\
0 & e^{i \alpha}
\end{array}\right],
\end{array}\right\}
\]
и их обратные $V_{4}, V_{5}, V_{6}, V_{7}$ порождают относительно композиции группу, плотную в группе всех унитарных преобразований $\mathscr{K}$. Удобно, хотя и не существенно, добавить еще две образующих:
\[
V_{8}=2^{-\frac{1}{2}}\left[\begin{array}{cc}
1 & 1 \\
-1 & 1
\end{array}\right] \quad \text { и } \quad V_{9}=2^{-\frac{1}{2}}\left[\begin{array}{cc}
1 & i \\
i & 1
\end{array}\right],
\]

которые соответствуют «поворотам спина» на $90^{\circ}$. Каждой образующей $V_{i}$ соответствуют элементы вычислительного базиса, представляющие программы $\Phi\left(V_{i}, a\right)$, которые выполняют $V_{i}$ над наименьшим значащим битом $a$-ой ячейки. Так, если $j$ есть нуль или единица, эти базисные элементы действуют в соответствии с формулой
\[
\left|\Phi\left(V_{i}, 2\right), j\right\rangle \rightarrow \sum_{k=0}^{1}\left\langle k\left|V_{i}\right| j\right\rangle\left|\Phi\left(V_{i}, 2\right), k\right\rangle .
\]

Композиция $V_{i}$ может быть выполнена с помощью сцепления $\Phi\left(V_{i}, a\right)$. Таким образом, существуют программы, которые действуют на состояние любого одного бита унитарным преобразованием, сколь угодно близким к желаемому.

Аналогичные заключения справедливы для совместного состояния конечного числа $L$ заданных битов. Это — не тривиальное наблюдение, поскольку такое состояние не обязательно есть прямое произведение состояний ограниченных на гильбертовы пространства отдельных битов, а, вообще говоря, линейная суперпозиция таких произведений. Тем не менее, я сейчас приведу набросок доказательства существования программы, которая порождает унитарное преобразование $L$ битов, сколь угодно близкое к любому желаемому унитарному преобразованию. Далее «точный» означает «сколь угодно точный относительно нормы внутреннего произведения». Случай $L=1$ тривиален. Докажем предположение для $L$ битов по индукции.

Во-первых, заметим, что все $\left(2^{L}\right)$ ! возможных перестановок из $2^{L}$ состояний вычислительного базиса $L$ — обратимые рекурсивные функции и, значит, могут быть вызваны программами $\mathcal{T}$ и, следовательно, $\mathcal{Q}$.

Далее мы покажем, что $\mathcal{Q}$ может порождать $2^{L}$-мерные унитарные преобразования, диагональные в вычислительном базисе, сколь угодно близко к любому диагональному преобразованию в этом базисе. Согласно индуктивному предположению, $(L-1)$-битовые диагональные преобразования точно $\mathcal{Q}$-вычислимы и, значит, порождаются определенными $2^{L}$-мерными диагональными унитарными матрицами, все собственные значения которых имеют четное вырождение. Перестановки базисных состояний позволяют $\mathcal{Q}$ точно вызвать любое диагональное унитарное преобразование с этим вырождением. Замыкание этого множества вырожденных преобразований относительно умножения — группа диагональных преобразований, плотная в группе всех $2^{L}$-мерных диагональных унитарных преобразований.

Далее мы покажем, что для каждого $L$-битового состояния $|\Psi\rangle$ существует $\mathcal{Q}$-программа $\rho(|\Psi\rangle)$, которая точно переводит $|\Psi\rangle$ в базисное состояние $\left|0_{L}\right\rangle$, в котором все $L$ битов — нули. Запишем
\[
|\Psi\rangle=c_{0}|0\rangle\left|\Psi_{0}\right\rangle+c_{1}|1\rangle\left|\Psi_{1}\right\rangle,
\]

где $\left|\Psi_{0}\right\rangle$ и $\left|\Psi_{1}\right\rangle$ — состояния $L-1$ битов, с номерами от 2 до $L$. По индуктивному предположению существуют $\mathcal{Q}$-программы $\rho_{0}$ и $\rho_{i}$, которые точно переводят $\left|\Psi_{0}\right\rangle$ и $\left|\Psi_{1}\right\rangle$ соответственно в ( $L-1$ )-кратное произведение $\left|0_{L-1}\right\rangle$. Поэтому существует $\mathcal{Q}$-программа со следующим действием: если бит 1 — нуль, выполнить $\rho_{0}$, иначе — $\rho_{1}$. Она преобразует (2.18) точно к
\[
\left(c_{0}|0\rangle+c_{1}|1\rangle\right)\left|0_{L-1}\right\rangle,
\]

затем (2.19) может быть точно переведено в $\left|0_{L}\right\rangle$ преобразованием бита номер 1.

Наконец, произвольное $2^{L}$-мерное преобразование $\mathrm{U}$ точно вызывается последовательным преобразованием каждого собственного вектора $|\Psi\rangle$ матрицы $\mathrm{U}$ точно в $\left|0_{L}\right\rangle$ (выполнением программы $\rho^{-1}(|\Psi\rangle)$ ), затем — выполнением диагонального унитарного преобразования, которое точно умножает $\left|0_{L}\right\rangle$ на собственное значение (фазовый множитель), соответствующие $|\Psi\rangle$, но имеет сколь угодно малое действие на любое другое состояние вычислительного базиса, и затем — выполнением $\rho(|\Psi\rangle)$.

Это устанавливает смысл, в котором $\mathcal{Q}$ — универсальный квантовый компьютер. Он может моделировать с произвольной точностью любой другой квантовый компьютер $\mathcal{Q}\left[\mathrm{U}^{+}, \mathrm{U}^{-}\right]$. Это так, поскольку, хотя квантовый компьютер имеет бесконечномерное пространство состояний, чтобы промоделировать его эволюцию, на каждом шаге нужно только конечномерное унитарное преобразование.