Рассмотрим теперь, как такой компьютер можно построить, используя законы квантовой механики. Мы собираемся записать гамильтониан для системы, состоящей из взаимодействующих частей, которая будет вести себя в некотором смысле как большая система, служащая универсальным компьютером. Конечно, большая система также подчиняется квантовой механике, но она взаимодействует с термостатом и другими вещами, что могло бы сделать ее существенно необратимой. Что бы мы хотели, так это сделать компьютер настолько малым и настолько простым, насколько это возможно. Наш гамильтониан будет детально описывать все внутренние вычислительные действия, но, разумеется, не взаимодействия с внешней средой, включающие в себя введение входных данных (приготовление начального состояния) и считывание выходной информации.

Насколько малым может быть такой компьютер? Насколько малым, например, может быть число? Как известно, число может быть представлено битами, состоящими из единиц и нулей. Представим себе, что у нас есть двухуровневые системы (т.е. такие, которые могут находиться в одном из двух состояний), которые мы будем называть «атомами». В таком случае $n$-битное число представляется некоторым состоянием «регистра» – набора $n$ двухуровневых систем. Очевидно, мы можем представить любое число, помещая каждый атом в одно или другое из его двух состояний, которые мы обозначим как $|1\rangle$ и $|0\rangle$. И число может быть считано с такого регистра путем определения или измерения, в каком состоянии каждый из атомов находится в данный момент. Таким образом, один бит будет представляться одним атомом, находящимся в одном из двух состояний, которые мы будем называть $|1\rangle$ и $|0\rangle$.

Для того чтобы понять, что мы должны сделать дальше, рассмотрим один пример; а именно пример элемента CONTROLLED CONTROLLED NOT. Пусть $G$ – некоторая операция над тремя атомами $a, b$ и $c$, которая переводит начальное состояние $a, b$ и $c$ в некоторое соответствующее состояние $a^{\prime}, b^{\prime}, c^{\prime}$, такое, что связь между $a^{\prime}, b^{\prime}, c^{\prime}$ и $a, b, c$ такова, какую следовало бы ожидать, если бы $a, b, c$ и $a^{\prime}, b^{\prime}, c^{\prime}$ представляли, соответственно, входные и выходные линии элемента CONTROLLED CONTROLLED NOT. Здесь надо принять во внимание, что в данный момент мы не пытаемся перевести информацию с одного места в другое; мы просто собираемся изменить ее. В отличие от того, что имеет место в настоящем компьютере, в котором напряжение передается с одного провода на другой, то, что мы делаем здесь, нечто более простое – а именно, имея три атома в некотором определенном состоянии, мы производим операцию, которая изменяет их состояния на новые $a^{\prime}, b^{\prime}, c^{\prime}$.

В этом случае мы имели бы, что состояние $\left|a^{\prime}, b^{\prime}, c^{\prime}\right\rangle$ получается в результате некоторой операции $G$ над состоянием $|a, b, c\rangle$. В квантовой механике операторы, которые изменяют состояния, являются линейными операторами, поэтому мы предположим, что $G$ линеен. Таким образом, $G$ есть матрица, и ее матричные элементы $G_{a^{\prime}, b^{\prime}, c^{\prime}, a, b, c}$ все равны нулю, кроме тех, которые соответствуют состояниям, задаваемым таблицей 1 , и которые, очевидно, равны 1.

Это то же самое, что таблица достоверных значений для CONTROLLED CONTROLLED NOT. Очевидно, что эта операция обратима, что может быть представлено формулой $G^{*} G=1$, где * означает эрмитово сопряжение. То есть $G$ – унитарная матрица. (В действительности $G$ является вещественной матрицей $G^{*}=G$, но это только в данном случае.) Для большей определенности матрицу для данного $G$ будем записывать как $A_{a b, c}$. Мы будем использовать то же обозначение $A$ с разным числом индексов для матриц, соответствующих другим примитивным элементам.

Для простого примера NOT, который будем представлять оператором $A_{a}$, матрица имеет вид
\[
\left[\begin{array}{ll}
0 & 1 \\
1 & 0
\end{array}\right] .
\]

Это матрица $2 \times 2$, которая может быть представлена разными способами, в разных обозначениях, но мы изберем тот способ, который основан на методе операторов рождения и уничтожения. Рассмотрим в этом случае действия на одну линию $a$. Используя ту же букву, обозначим через $\underline{a}$ матрицу
\[
\underline{a}=\left[\begin{array}{ll}
0 & 1 \\
0 & 0
\end{array}\right],
\]

которая уничтожает 1 на атоме $a$, превращая ее в 0 ; другими словами, $\underline{a}$ есть оператор, который переводит состояние $|1\rangle$ в состояние $|0\rangle$. Но если атом был первоначально в состоянии $|0\rangle$, то оператор $\underline{a}$ дает число 0 . То есть он не меняет состояние, он просто дает численное значение 0 , действуя на это состояние. Сопряженным ему, очевидно, является
\[
\underline{a}^{*}=\left[\begin{array}{ll}
0 & 0 \\
1 & 0
\end{array}\right],
\]

который есть оператор рождения, в том смысле, что, действуя на состояние $|0\rangle$, он переводит его в состояние $|1\rangle$. Действуя на состояние $|1\rangle$, он дает числовое значение 0 , поскольку не существует дальнейших состояний, которые можно создать. Любой другой $2 \times 2$ матричный оператор может быть представлен в терминах этих $\underline{a}$ и $\underline{a}^{*}$. Например, произведение $\underline{a}^{*} \underline{a}$ равно матрице
\[
\underline{a}^{*} \underline{a}=\left[\begin{array}{ll}
1 & 0 \\
0 & 0
\end{array}\right],
\]

которую можно назвать $N_{a}$. Она дает 1 , действуя на состояние $|1\rangle$, и 0 , действуя на состояние $|0\rangle$, или, другими словами, номер состояния, в котором находится атом. Аналогично произведение
\[
\underline{a}^{*}=\left[\begin{array}{ll}
0 & 0 \\
0 & 1
\end{array}\right]
\]

есть $1-N_{a}$, дает 0 для верхнего состояния и 1 для нижнего. Будем использовать 1 для обозначения диагональной матрицы
\[
\left[\begin{array}{ll}
1 & 0 \\
0 & 1
\end{array}\right] .
\]

Из сказанного выше следует, что $\underline{a}^{*}+\underline{a}^{*} \underline{a}=1$.
Очевидно теперь, что наша матрица для NOT, оператор, который производит NOT, есть $A_{a}=\underline{a}+\underline{a}^{*}$, и далее, то, что он является обратимым и унитарным $A_{a} * A_{a}=1$.

Подобным образом может быть получена и матрица $A_{a, b}$ для CONTROLLED NOT. Если вы посмотрите на таблицу значений CONTROLLED NOT, то увидите, что она может быть записана следующим образом:
\[
\underline{a}^{*} \underline{a}\left(\underline{b}+\underline{b}^{*}\right)+\underline{a}^{*} \underline{a}^{*} .
\]

В первом слагаемом $\underline{a}^{*} \underline{a}$ выделяет условие, что линия $a=1$, в этом случае мы хотим, чтобы $\underline{b}+\underline{b}^{*}$, NOT, применялось к $b$. Второе слагаемое выделяет условие того, что линия $a$ равна 0 ; в этом случае мы не хотим, чтобы что-то действовало на $b$, т. е. подразумевается, что на $b$ действует единичная матрица. Это может быть также записано как
\[
1+\underline{a}^{*} \underline{a}\left(\underline{b}+\underline{b}^{*}-1\right) .
\]
Здесь 1 соответствует тому, что все линии проходят без изменений, но в случае $a=1$ мы хотели бы исправить это, поместив NOT вместо того, чтобы оставить линию $b$ без изменения.

Как, возможно, вы уже заметили, матрица для CONTROLLED CONTROLLED NOT имеет вид
\[
A_{a b, c}=1+\underline{a}^{*} \underline{a}^{*} \underline{b}\left(\underline{c}+\underline{c}^{*}-1\right) .
\]

Следующий вопрос – как выглядит матрица для логического блока общего вида, который состоит из последовательности примитивных элементов. В качестве примера рассмотрим случай полного сумматора, который был описан раньше (см. рис. 5). Теперь у нас будет в общем случае четыре провода, представляемых как $a, b, c$ и $d$; необязательно полагать $d$ равным 0 во всех случаях, и мы хотели бы описать, как объект действует в общем случае (если $d$ становится равным 1 , то $d^{\prime}$ получается действием на него NOT). В результате получатся новые числа $a^{\prime}, b^{\prime}, c^{\prime}$ и $d^{\prime}$; и мы могли бы представить себе нашу систему как состоящую из четырех атомов $a, b, c, d$, находящихся в состоянии $|a, b, c, d\rangle$. Матрица $M$ действует, изменяя эти самые четыре атома так, что они оказываются в состоянии $\left|a^{\prime}, b^{\prime}, c^{\prime}, d^{\prime}\right\rangle$, соответствующем этому логическому блоку. То есть, если $\left|\psi_{\text {in }}\right\rangle$ представляет собой входящее состояние четырех битов, то $M$ – матрица, которая генерирует выходящее состояние $\left|\psi_{\text {out }}\right\rangle=M\left|\psi_{\text {in }}\right\rangle$ для этих четырех битов.

Например, если входящее состояние было бы $|1,0,1,0\rangle$, то, как мы знаем, выходящее состояние должно быть $|1,0,0,1\rangle$; первые два, $a^{\prime}, b^{\prime}$, должны быть 1,0 , так как эти две первые линии проходят без изменений, а последние две, $c^{\prime}, d^{\prime}$, должны быть 0,1 , потому что они представляют сумму и перенос первых трех битов, $a, b, c$, в начальном входе, так как $d=0$. Теперь матрица $M$ для сумматора может рассматриваться как результат пяти последовательных примитивных операций и, таким образом, является матричным произведением пяти следующих одна за другой матриц, представляющих эти примитивные объекты:
\[
M=A_{a, b} A_{b, c} A_{b c, d} A_{a, b} A_{a b, d} .
\]

Первой матрицей, самой крайней правой, является $A_{a b, d}$, так как она представляет CONTROLLED CONTROLLED NOT, в котором $a$
и $b$ служат контрольными линиями, а NOT появляется на линии $d$. Взглянув на диаграмму на рис. 5 , мы немедленно увидим, чему соответствуют другие множители. Например, последний множитель $A_{a, b}$ представляет CONTROLLED NOT с контрольной линией $a$ и NOT на линии $b$. Эта матрица обладает свойством унитарности, $M^{*} M=1$, так как является произведением унитарных матриц $A$. То есть $M-$ обратимая операция и $M^{*}$ – ее обратная.

Наша главная задача, таким образом, заключается в следующем. Пусть $A_{1}, \ldots, A_{k}$ – последовательность требуемых в некотором логическом блоке операций, действующих на $n$ линий. Матрица $M$ размерности $2^{n} \times 2^{n}$, необходимая для выполнения той же цели, есть произведение $A_{k} \ldots A_{2} A_{1}$, где каждая $A$ – некоторая простая матрица. Как мы можем воспроизвести эту матрицу физически, если мы знаем, как сделать более простые элементы?

В общем случае в квантовой механике для системы с гамильтонианом $H$ состояние на выходе в момент времени $t$ есть $e^{i H t} \psi_{\text {in }}$, где $\psi_{\text {in }}-$ состояние на входе. Попытка найти для некоторого данного конкретного времени $t$ гамильтониан, который приводил бы к $M=e^{i H t}$, где $M-$ такое произведение некоммутирующих матриц, исходя из некоторого простого свойства этих матриц, оказывается очень сложной.

Заметим однако, что, если мы разложим $e^{i H t}$ (как $1+i H t-$ $-H^{2} t^{2} / 2-\ldots$ ), то мы найдем, что оператор $H$ действует произвольное число раз (один раз, дважды, трижды и так далее), и полное состояние получается суперпозицией всех возможностей. Это предполагает, что мы сможем решить проблему построения этих $A$ следующим образом. Добавим к $n$ атомам, которые находятся в нашем регистре, полностью новый набор из $k+1$ атомов, которые мы назовем «программно считающие ячейки». Обозначим через $q_{i}$ и $q_{i}^{*}$ операторы уничтожения и рождения для ячейки $i, i=0, \ldots, k$. Можно представлять себе в качестве примера электрон, переходящий из одной свободной ячейки в другую. Если ячейка $i$ занята электроном, то его состояние есть $|1\rangle$, если же ячейка свободна, то его состоянием является $|0\rangle$.
В качестве нашего гамильтониана примем
\[
\begin{array}{c}
H=\sum_{i=0}^{k} q_{i+1}^{*} q_{i} A_{i+1}+\text { комплексно сопряженное }= \\
=q_{1}^{*} q_{0} A_{1}+q_{2}^{*} q_{1} A_{2}+q_{3}^{*} q_{2} A_{3}+\ldots+ \\
+q_{0}^{*} q_{1} A_{1}^{*}+q_{1}^{*} q_{2} A_{2}^{*}+q_{2}^{*} q_{3} A_{3}^{*}+\ldots
\end{array}
\]

Прежде всего заметим, что если все программные ячейки не заняты, то есть все программные атомы первоначально находятся в состоянии $|0\rangle$, то ничего не будет происходить, потому что каждый член в гамильтониане начинает действовать с оператора уничтожения, что дает 0 .

Во-вторых, заметим, что если только одна (та или другая) из программных ячеек занята (в состоянии $|1\rangle$ ), а все остальные не заняты (в состоянии $|0\rangle$ ), то это утверждение справедливо всегда. Действительно, число программных ячеек, находящихся в состоянии $|1\rangle$, является сохраняющейся величиной. Мы будем предполагать, что при действии этого компьютера или ни одна ячейка не занята (в этом случае ничего не происходит), или занята только одна ячейка. Две или более программных ячеек никогда не бывают заняты одновременно в течение нормальной операции.

Давайте начнем с начального состояния, в котором ячейка 0 занята (находится в состоянии $|1\rangle$ ), а все остальные – свободны (в состоянии $|0\rangle$ ). Если позже, в некоторый момент времени, конечная ячейка $k$ окажется в состоянии $|1\rangle$ (и, таким образом, все другие в состоянии $|0\rangle$ ), то мы утверждаем, что регистр был умножен на матрицу
\[
M=A_{k} \ldots A_{2} A_{1} \text {, что и требовалось. }
\]

Позвольте мне объяснить, как это работает. Предположим, что регистр начинает в некотором начальном состоянии $\psi_{\text {іл }}$ и что программная ячейка 0 занята. Тогда единетвенный член во всем гамильтониане, который может вначале действовать, поскольку гамильтониан действует последовательно, – это первое слагаемое $q_{1}^{*} q_{0} A_{1}$. Оператор $q_{0}$ сделает так, что ячейка номер 0 станет незанятой, а оператор $q_{1}^{*}$ сделает занятой ячейку номер 1 . Таким образом, член $q_{1}^{*} q_{0}$ просто передвигает занятую ячейку из позиции 0 в позицию 1 . Но все это умножается на матрицу $A_{1}$, которая действует только на $n$ атомов регистра. Таким образом, начальное состояние $n$ атомов регистра умножается на $A_{1}$.

Теперь, если гамильтониану доводится действовать второй раз, этот первый член ничего не даст, потому что $q_{0}$, действуя на незанятую нулевую ячейку, дает 0 . Оператором же, который действует на сей раз, является второе слагаемое $q_{2}^{*} q_{1} A_{2}$, поскольку именно оно может сдвинуть занятую ячейку, которую я буду называть «курсором». Курсор может сдвинуться из ячейки 1 в ячейку 2 , а матрица $A_{2}$ теперь действует на регистр; таким образом, на регистр в результате действует матрица $A_{2} A_{1}$. В результате последовательных действий гамильтониана курсор передвинулся бы последовательно от 0 к $k$, и вы получили бы одну за другой матрицы $A$, действующие на $n$ атомов регистра в порядке, который необходим для конструирования полной матрицы $M$.

Однако гамильтониан должен быть эрмитовым, и поэтому должно присутствовать сопряжение всех этих операторов. Предположим, что на данной стадии мы имеем курсор на ячейке номер 2 и матрицу $A_{2} A_{1}$, действующую на регистр. Оператор $q_{2}$, который требуется для перевода курсора в новую позицию, может встретиться и в другом слагаемом. В действительности он возникает в слагаемом $q_{1}^{*} q_{2} A_{2}^{*}$, которое сдвинуло бы курсор из позиции 2 в позицию 1 . Но заметьте, что когда это происходит, оператор $A_{2}^{*}$ также действует на регистр, и, таким образом, в этом случае полный оператор, действующий на регистр, есть $A_{2}^{*} A_{2} A_{1}$. Но так как $A_{2}^{*}, A_{2}=1$, то остается только $A_{1}$. Таким образом, мы видим, что когда курсор возвращается в позицию 1 , только оператор $A_{1}$ реально действует на регистр. В итоге по мере того как разные члены в гамильтониане двигают курсор назад или вперед, матрицы $A$ либо накапливаются в произведении, либо число этих сомножителей опять уменьшается. На любом этапе, например, если бы курсор находился в положении $j$, матрицы от $A_{1}$ до $A_{j}$ действовали бы последовательно на регистр $n$. Не имеет значения, как курсор попал в положение $j$, двигаясь ли прямо от 0 до $j$, или проходя дальше и возвращаясь, или двигаясь назад и вперед любым образом, важно лишь, что он в конце концов оказался в положении $j$. Таким образом, если курсор находится в ячейке $k$, то матрица $M$ действует на начальное состояние $n$ атомов регистра, что и требовалось.

Как мы теперь могли бы производить операции на этом компьютере? Мы начинаем с того, что загружаем входные биты на регистр и помещаем курсор в ячейку 0 . Затем мы проверяем ячейку $k$, скажем, посредством рассеяния электронов, на предмет того, свободна ли она или курсор находится на ней. В тот момент, когда мы находим курсор на ячейке $k$, мы удаляем курсор так, чтобы он не мог вернуться на программную линию. После этого мы знаем, что регистр содержит выходные данные. Когда нам будет удобно, мы можем их измерить. Конечно, в процесс измерения и определения всего этого включены и внешние факторы, которые не являются частью нашего компьютера. Очевидно, в конце концов компьютер должен быть во взаимодействии с внешним миром как для загрузки данных, так и для считывания их.

Математически оказывается, что передвижение курсора вверх и вниз вдоль программной линии в точности эквивалентно тому, как если бы в гамильтониане не было бы операторов $A$. Другими словами, это представляет просто волны, знакомые из задачи распространения сильно связанных электронов, или спиновые волны в одном измерении, которые хорошо известны. Это волны, которые движутся вверх и вниз по линии, у вас могут быть пакеты волн и так далее. Мы могли бы усовершенствовать действие этого компьютера и превратить его в баллистическое действие, создав линию ячеек в дополнении к ячейкам внутри, которые мы действительно используем для вычисления, линию из многих ячеек до и после. Это было бы в точности, как если бы мы имели значения индекса $i$ для $q_{i}$, которые меньше 0 и больше $k$, для каждого из которых вместо умножения на матрицу $A$ было бы умножение на 1. Тогда у нас была бы длинная спиновая цепочка, и мы могли бы начинать, вместо того чтобы помещать курсор точно на начальную ячейку 0 , помещая курсор с разными амплитудами на разные ячейки, представляя начальную входящую спиновую волну, широкий пакет с приблизительно определенным импульсом. Эта спиновая волна прошла бы затем через весь компьютер баллистическим образом и вышла с другой стороны из выходного устройства, которое мы добавим к цепочке наших программных ячеек, и где ответ, если он имеется, может быть легко определен или перемещен в какое-либо другое место, будучи захваченным курсором. Таким образом, логический элемент может действовать баллистическим путем.

Это очень важный момент, и, по крайней мере, специалисты в теории вычислений могут показать, что мы могли бы построить универсальный компьютер, если, как нам известно, мы сможем сделать любой логический элемент. Пока не очевидно, как представить универсальный компьютер для заданной совокупности логических элементов и их связей, для этого необходимы некие дополнительные сведения, которых мы в дальнейшем коснемся.