А.С, для Б = О

В ф {А.С) = <

(AND) (XOR) (NOT)

А® В, для С = 1

Б, для А = с = 1 А, для Б = О, С = 1 (FANOUT)

где А.В изображает AND-гейт, А® В изображает XOR-гейт и А изображает NOT-гейт. Мы видим, что этот гейт является универсальным, поскольку он выполняет AND, XOR, NOT или FANOUT, в зависимости

т того, что имеется на входе.

Комбинация многих таких гейтов может затем использоваться для

юбого вычисления и будет оставаться обратимой.

А В С

В® (А.С) С

Рис. 4. Универсальный обратимый Тоффоли-гейт с тройным входом и тройным выходом. Этот гейт, очевидно, является обратимым, т. к. повторное его применение воспроизводит первоначальные входные данные.

Как было замечено Ландауэром, эта процедура приводит к прямой проблеме из-за отсутствия примитивного ERASE. Чем больше гейтов мы используем, тем больше «мусорных» битов мы накопим: в каждом гейте мы должны хранить входные биты для сохранения обратимости. Другими словами, компьютер, построенный из логически обратимых гейтов вместо обычных, логически необратимых гейтов, вел бы себя как

/: а (а, j(a),/(a)),

с большим числом дополнительных мусорных битов j{a).

Беннетт решил эту проблему, показав, что мусорные биты могут ыть обратимым образом стерты на промежуточных шагах с минимальными затратами времени и памяти [12, 13]. Идею решения Беннетта можно истолковать на языке следующей процедуры:

/: а (а, j(a), /(а)), FANOUT: (а, i(a), /(а)) (а, i(a), /(а), /(а)),

/t:(a,i(a),/(a),/(a))(a, /(а)),

где р обозначает возвращение к невычисленному /, как противоположное к вычислению /~. Сначала вычисляется / и при этом получаются

мусорные биты и искомый выходной результат. Затем применяется FANOUT-гейт для дублирования выходного результата. В конце мы возвращаемся к невычисленной исходной функции /, выполняя в обратную сторону операцию ее вычисления. Эта процедура удаляет мусорные биты и первоначальный выходной результат. Однако дубликат остается!

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

6. Элементарные квантовые понятия

Одну из простых квантовых систем, в которой имеется два уровня, представляет собой частица со спином Ее базисные состояния, спин вниз I \) и спин вверх t), могут быть переобозначены для представления двоичных нуля и единицы, т. е., соответственно, 0) и 1). Состояние одной такой частицы описывается волновой функцией ф = а0) + /?1).

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

одно

ичным строкам длины к. Например, 25) = 11001) = из таких состояний для А: = 5.

Размерность гильбертова пространства растет экспоненциально с величением к.

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

7. Логические гейты для квантовых битов

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

Мы начнем с рассмотрения различных однобитных операций и одной двубитной - XOR-операции. Их комбинации достаточны для по-

строения Тоффоли-гейта для квантовых битов, или, на самом деле, любой унитарной операции на конечном числе битов.

Начнем с одного квантового бита. Если представить состояния 1) t) (т. е. 0) и 1)) как векторы (J) и соответственно, то наиболее

общему унитарному преобразованию отвечает матрица 2x2 вида

gi(++r) e-*(+-) sin {в/2)\

i{s-ar) gjj 02) e*(--) cos (0/2) )

в которой обычно полагают S = а = т = О [14]. Используя этот оператор, мы можем инвертировать биты:

С/,0) = -1), С/.1) = 0).

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