Мы выполним то, что намеревались сделать – найти какой-нибудь квантовомеханический гамильтониан системы, которая может быть использована в вычислениях, и это все, что следует сказать. Но имеет место некий интерес заняться определенными вопросами, связанными с простейшей реализацией. Гамильтониан, который мы выпишем, содержит члены, отражающие особый вид взаимодействия между пятью атомами. К примеру, три таких атома в регистре для осуществления операции CONTROLLED CONTROLLED NOT, а два других будут использоваться как дополнительные ячейки в качестве программных счетчиков.

Возможно, это достаточно сложно сделать. Вопрос заключается в следующем: можем ли мы построить такую систему из простейших частей. Оказывается, да. Мы можем это сделать так, что в каждом взаимодействии будут учитываться только три атома. Мы собираемся стартовать с новых примитивных элементов, вместо тех, с которых мы начинали раньше. Мы будем иметь ту же операцию NOT, но в дополнение к ней мы будем производить простой «переключатель» (см. также Priese [5]).

Предположим, что мы имеем следующий член в гамильтониане $q^{*} c p+r^{*} c^{*} p$ плюс член ему комплексно сопряженный (во всех случаях мы будем использовать буквы из начала алфавита для обозначения значений атомов регистра и из конца алфавита для обозначения программного места). См. рисунок 7. Здесь показано действие переключателя: если $c$ в начальный момент находится в состоянии $|1\rangle$, курсор из $p$ будет двигаться в $q$, в противном случае, если $c$ находится в состоянии $|0\rangle$, курсор из $p$ перейдет в $r$. В течение этой операции контролируемый атом $c$ изменяет свое состояние. (Возможно также записать выражение, в котором контролируемый атом не меняет своего состояния, а именно, $q^{*} c^{*} c p+r^{*} c c^{*} p$ плюс его комплексное сопряжение, это не приносит никаких частных преимуществ или недостатков, мы исследуем самый простой случай.) Комплексное сопряжение приводит к обратному результату. Однако, если курсор находится в $q$ и $c$ находится в состоянии $|1\rangle$ (или курсор на $r$, а $c$ в состоянии $|0\rangle$ ), тогда $H$
равен 0 , а курсор возвращается назад. Мы воспроизведем все наши схемы и выберем начальные состояния таким образом, что эти условия не будут возникать при нормальном функционировании и будет работать идеальная баллистическая мода.

С таким переключателем мы можем сделать большое число операций. Например, мы можем получить CONTROLLED NOT операцию, как это показано на рисунке 8. Переключатель $a$ контролирует операцию 0. Предположим, что курсор находится в состоянии $s$. Если $a=1$, программный курсор движется вдоль верхней линии, тогда как если $a=0$, курсор движется вдоль нижней линии, в обоих случаях мы получим в конце концов программное состояние $t$.
Рис. 8. Реализация CONTROLLED NOT с помощью переключателя
На этих диаграммах горизонтальные и вертикальные линии обозначают программные атомы. Переключатели воспроизведены как диагональные линии, и под прямоуго.ьником мы подразумеваем действующие на регистры матрицы, такие как NOT $b$. Таким образом, гамильтониан для этого небольшого участка CONTROLLED NOT операции, стартующий с состояния $s$ и заканчивающийся в состоянии $t$, дается следующим выражением:
\[
H_{c}(s, t)=s_{M}^{*} a s+t^{*} a^{*} t_{M}+t_{M}^{*}\left(b+b^{*}\right) s_{M}+s_{N}^{*} a^{*} s+t^{*} a t_{N}+t_{N}^{*} s_{N}+\text { к.с. }
\]
(Под к.с. понимается комплексное сопряжение предыдущих членов.) Хотя кажется, что существует два пути получения всех видов полных характеристик квантовой механики, но это не так. Если вычислительная система начинает с какого-то определенного состояния атома $a$ и со временем курсор достигает состояния $s$, то атом $a$ все еще будет находиться в некотором определенном состоянии (хотя, возможно, и отличном от исходного, благодаря произведенным над ним ранее вычислительным операциям). Поэтому возможен только один из двух путей. Выражение можно упростить, опуская член $s_{N}^{*} t_{N}$ и полагая $t_{N}=s_{N}$.

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

Изучая далее этот вопрос, рассмотрим соединенные вместе отрезки. Отрезок цепи $M$ (см. рисунок 9) может быть представлен как логический элемент взаимодействующих частей, под которыми мы понимаем начальное состояние курсора $s_{M}$ и конечное его состояние $t_{M}$. Все оставшиеся программные состояния, находящиеся между $s_{M}$ и $t_{M}$, представлены внутренними частями $M$, и $M$ содержит собственные регистры. Только состояния $s_{M}$ и $t_{M}$ могут быть связаны внешним образом.

Рис. 9. Один из «отрезков линии». $s_{M}$ – начальное программное состояние для отрезка, $t_{M}$ – конечное программное состояние для отрезка. $H_{M}\left(s_{M}, t_{M}\right)$ – часть гамильтониана, соответствующая всем «атомам» и программным состояниям, входящим в бокс $M$, а также их взаимодействие с $s_{M}$ и $t_{M}$

Гамильтониан такой подсистемы мы будем обозначать как $H_{M}$, а под $s_{M}$ и $t_{M}$ мы будем понимать начальное и конечное программные состояния и записывать это как $H_{M}\left(s_{M}, t_{M}\right)$. И, следовательно, $H_{M}-$ часть гамильтониана, представляющая все входящие в бокс $M$ атомы и их внешние начальные и конечные состояния.
Особенно важный и интересный для рассмотрения случай – это когда внешние данные (на атомах регистра) приходят от определенного логического элемента, и нам необходимо перенести эти данные на другой (см. рис. 10). Предположим, что мы представили, что бокс $M$ начинает работу с состояния своего входного регистра, содержащего 0 , и состояния выходного регистра (возможно, того же самого), равного также 0 . Тогда мы могли бы использовать его следующим образом. Мы могли бы сделать программную линию, пусть, скажем, она начинается с состояния $s_{M}^{\prime}$, и чья первая операция будет заключаться в перемещении информации с внешнего регистра, содержащего входные данные, на $M$-й входной регистр, содержащий в данный момент нули. Тогда первым шагом наших вычислений мог бы быть, начиная, скажем с $s_{M}^{\prime}$, обмен информацией с внутренним регистром $M$. При этом заносятся нули в исходный входной регистр, а входные данные записываются внутрь бокса $M$. Теперь курсор находится в позиции $s_{M}$. (Мы уже разъясняли, как происходит обмен информацией на примере операции CONTROLLED NOT.) После проведения программных действий от $s_{M}$ до $t_{M}$ мы находим выходные данные в боксе $M$. После этого выходной регистр бокса $M$ очищается, а содержащаяся в нем информация заносится в заранее подготовленный внешний регистр, первоначально содержащий нули. Таким образом, на этапе от $t_{M}$ до $t_{M}^{\prime}$ мы обмениваемся информацией между пустым внешним регистром и выходным регистром бокса $M$.

Сейчас мы можем рассмотреть с разных сторон связь таких логических элементом. К примеру, наиболее очевидный способ такой связи можно осуществить при помощи последовательности. Если мы сначала хотим произвести действие бокса $M$, а затем действие бокса $N$, мы можем связать конечную позицию первого и начальную позицию второго, как это показано на рисунке 11. Таким образом, получается новая операция $K$, гамильтониан $H_{K}$ которой имеет вид
\[
H_{K}\left(s_{K}, t_{K}\right)=H_{M}\left(s_{K}, t\right)+H_{N}\left(t, t_{K}\right) .
\]

Пусть теперь действие происходит по условию: если $a=1$, то выполняется $M$, но если $a=0$, то выполняется $N$, как это показано на ри-
Рис. 10. Участок с внешним входом и выходом

сунке 12. Для этой операции гамильтониан имеет вид
\[
\begin{array}{l}
H_{\text {cond }}\left(s_{c}, t_{c}\right)=\left(s_{M}^{*} a s_{c}+t_{c}^{*} a^{*} t_{M}+s_{N}^{*} a^{*} s_{c}+t_{c}^{*} a t_{N}+c . c .\right)+ \\
+H_{M}\left(s_{M}, t_{M}\right)+H_{N}\left(s_{N}, t_{N}\right) .
\end{array}
\]

Операция CONTROLLED NOT является частным случаем приведенного выше с $M=N O T b$, для которого гамильтониан имеет вид
\[
H_{\text {NOT }}(s, t)=s^{*}\left(b+b^{*}\right) t+c . c .
\]

и $N$ – операция $s^{*} t$.
\[
\begin{array}{c}
s_{K}-{ }_{t} t_{K}=s_{K}-K \\
H_{K}\left(s_{K}, t_{K}\right)=H_{M}\left(s_{K}, t\right)+H_{N}\left(t, t_{K}\right)
\end{array}
\]

Рис. 11. Последовательность операций
В качестве другого примера мы можем рассмотреть «уничтожитель мусора» (уже рассмотренный на рисунке 6), сделанный не из двух
Рис. 12. Контролируемая операция: если $a=1$, то выполняется $M$, но если $a=0$, то выполняется $N$

устройств, прямого и обратного к нему, а использующий ту же самую машину, но только посылая данные обратно в устройство в обратном направлении, используя изображенный на рисунке 13 наш переключатель. Предположим, что такая система имеет специальный флаг, который изначально всегда находится в нуле. Мы также предположим, что исходные данные содержатся во внешнем регистре, а пустой внешний регистр используется для выходных данных, а также все машинные регистры пусты (содержат нули). Таким образом, мы получили начальное состояние системы $s$. Первое, что мы сделаем, это скопируем (используя операцию CONTROLLED NOT) содержимое нашего внешнего регистра в $M$. Затем действует $M$, и курсор переходит на верхнюю позицию на нашем рисунке. Далее копируем выходные данные действия оператора $M$ во внешний выходной регистр. В $M$ сейчас содержится мусор. Теперь меняем $f$ на NOT $f$ и возвращаемся назад по другой линии переключателя, проходим в обратную сторону по $M$, очищая его от мусора, и все копируем снова во внешний входной регистр. Когда вы копируете данные, а затем делаете это снова, вы обнуляете один из регистров, тот, в который вы копировали в первый раз. После такого копирования данные уходят (поскольку $f$ теперь изменен) по другой линии, где мы восстанавливаем в $f$ нулевое значение и выходим в момент $t$. Таким образом, на промежутке от $s$ до $t$ мы теперь имеем новое устройство, обладающее следующими свойствами.

В начале работы в регистре, названном IN, содержатся входные данные. Во внешнем регистре, названном OUT, содержатся нули. Внутренний флаг находится в положении ноль, а бокс $M$ не содержит ни-
Рис. 13. Уборщик «мусора»

каких данных. В результате произведенных действий в момент $t$ во входном регистре так и будут находиться входные данные, а выходной регистр содержит результат действия оператора $M$. $M$, однако, продолжает оставаться пустым, а флаг $f$ находится в нуле.

Также очень важным для компьютерной программы является возможность использования одной и той же подпрограммы несколько раз. Конечно, с логической точки зрения этого можно достичь, записывая этот участок программы еще и еще раз, столько раз, сколько нам необходимо, но в практических вычислениях было бы гораздо лучше, если мы могли построить такой раздел компьютера, который производил бы некое частное действие, а затем использовать его снова и снова. Для того чтобы показать такую возможность, мы для начала предположим, что нам необходимо произвести двойное последовательное повторение определенной операции (см. рисунок 14). Мы начнем в момент $s$, флаг $a$ находится в состоянии 0 . Далее мы будем двигаться вдоль линии, и первое, что произойдет, – изменится значение $a$. Затем мы произведем операцию $M$. Теперь, так как значение $a$ изменено, вместо того чтобы уйти по верхней линии, с которой мы начинали, мы возвращаемся назад по нижней линии, которая возвращает программу назад на момент очередного изменения значения флага $a$. Таким образом, все начинается снова. На этот раз, пройдя сквозь $M$, мы выйдем из подпрограммы по верхней линии и таким образом достигнем конечного момента $t$. Гамильтониан этой системы имеет вид
\[
\begin{array}{c}
H_{M M}(s, t)=\left(s_{N}^{*} a^{*} s+s_{M}^{*}\left(a^{*}+a\right) s_{N}+x^{*} a^{*} t_{M}+s_{N}^{*} a x+t^{*} a t_{M}+c . c\right)+ \\
+H_{M}\left(s_{M}, t_{M}\right) .
\end{array}
\]
Используя такие схемы с переключателем несколько раз, мы, конечно, можем повторять операции сколько угодно раз. Например, используя ту же идею последовательно три раза подряд, строя вложенный цикл, мы можем повторить операцию восемь раз с помощью устройства, изображенного на рисунке 15 . Для того чтобы это сделать, нам понадобилось три флага: $a, b$ и $c$. Флаги нужны для того, чтобы можно было повторять операции по той причине, что мы должны проследить, сколько раз эта операция повторяется и в каком месте программы она возникает, в противном случае мы никогда не добьемся обратимости.
Рис. 14. Устройство, дважды производящее операцию $M$
Подпрограмма в обычном компьютере может быть использована, обнулена и снова использована без каких-либо записей о том, что произошло. Но в данном случае мы должны сохранять и делать то же самое с флагами, чтобы точно знать, в каком месте цикла использования подпрограммы мы находимся. Если подпрограмма вызывается из определенного места программы и должна вернуться в какое-нибудь другое место, то во время ее вторичного вызова ее начальное и конечное положения отличны от предыдущего случая. Нам необходимо знать и держать в памяти, откуда это пришло и куда предполагается обратиться индивидуально для каждого такого случая, таким образом, необходимо хранить большое количество данных. Использование подпрограмм снова и снова в обратимых машинах только немного сложнее, чем на обыкновенных машинах. Все эти рассуждения появились в работах Фредкина, Тоффоли и Беннетта.

Стало ясно, что с использованием такого флага или последовательности используемых древовидных структур переключателей, мы могли бы направить данные в любое место в памяти. Под памятью мы
Рис. 15. Устройство, производящее операцию $M$ восемь раз
Рис. 16. Нарастающий счетчик (трехбитный)

понимаем место, где находятся регистры, в которых записаны данные и к которым обращается программа. Курсор будет перемещаться по таким данным. Я полагаю, что должны существовать и другие древовидные системы из переключателей, позволяющие проводить курсор в обратном направлении после записи данных, причем система остается обратимой.

На рисунке 16 показан пошагово приращиваемый бинарной счетчик (содержащий три бита $a, b$ и $c$, причем $c$ – наиболее важный бит), который сохраняет информацию о том, сколько раз курсор прошел от $s$ до $t$. Этих примеров должно быть вполне достаточно, чтобы показать, что мы действительно можем построить любую вычислительную функцию, используя наши переключатели и операции NOT. Мы не будем далее вникать в подробности.