где q = 2. Наш компьютер находится теперь в суперпозиции экспоненциально большого числа целых чисел а от О до 2 - 1. Предположим, что мы можем теперь построить унитарную операцию, которая отображает пару двоичных строк а;0) в пару для некоторой функции /(а).

Тогда такой унитарный оператор, действуя на суперпозицию состояний

вычисляет функцию f{a) параллельно экспоненциально большое число раз для различных входных значений а.

Чтобы понять, как такие унитарные операторы могут быть постро-

ны из нескольких элементарных операторов, рассмотрим XOR-гейт

14, 15].

Записывая двухчастичные базисные состояния как вектора /1\ /0\ /0\ /0\

2 . 01)= J , 10)= J , 11)= 2

\о) \о) \о) \1/

мы можем представить XOR гейт унитарным оператором

00) =

CXOR

1 о о

о о о 1

Здесь первая частица действует как условный гейт для инвертирования состояния второй частицы. Легко проверить, что состояние второй частицы отвечает действию XOR-гейт, заданного в таблице 1. Квантовая цепь для XOR-гейта изображен на рис. 6.

А) -т- \А)

1АеБ)

Рис. 6. Диаграмма квантового цикла для XOR-гейта. Низший бит \В) инвертируется всякий раз, когда верхний бит \А) является единицей.

Эта цепь эквивалентна элементарной команде: если {\А) = 1), В) N0T5), что можно понимать как пример программы квантового компьютера [22]. Скобки ) являются напоминанием того, что

мы имеем дело с квантовыми, а не классическими битами. XOR-гейт позволяет перемещать информацию, как показано на рис. 7.

Рис. 7. Цикл для перестановки местами пары битов.

Как построить Тоффоли-гейт? Главная проблема с этим гейтом заключается в том, что он требует три бита на входе и три на выходе. Кажется, что это соответствует квантовому процессу рассеяния, включающему трехчастичные столкновения [16], требующие (возможно) непомерного контроля за частицами [5]. К счастью, Тоффоли-гейт может быть построен только из процессов двухчастичного рассеяния [15, 17, 18, 19, 20]. В частности, здесь мы показываем конструкцию, включающую XOR-гейт и некоторые однобитные гейты Uq (рис. 8) [14].

А) -,-,- А)

В) -

и ,-\АЦА.С))

Рис. 8. Тоффоли-гейт, построенный из двубитных XOR-гейтов плюс некоторых однобитных гейтов [5, 14]. Эта цепь вводит некоторые дополнительные знаки в унитарной матрице C/xor, которые могут быть удалены на более позднем этапе.

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

кие гейты

2, 6

8. Модельный квантовый компьютер и квантовые коды

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

Ф Ф Ф Ф •

Ф Ф Ф Ф • • •

Ф Ф Ф Ф Ф Ф •

Рис. 9. Модельный квантовый компьютер в представлении Шора [21]. Первоначально все частицы имеют спины вниз. Этап а) классическая машина

ерет отдельные спины или пары спинов и на этапе Ь) производит подобранную однобитную или двубитную операцию; на этапе с) «скрещенные» частицы возвращаются на свои первоначальные места. Эти три этапа повторяются много раз в соответствии с командами, заданными обычным классическим компьютером. Когда этот цикл завершен, этап d) состоит в измерении со-

тояния частиц (помещая их в некоторую частную двоичную строку); эта

воичная строка является результатом вычисления.

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

го уровня довольно сложной. Мы обсудим некоторые из правил для написания такого кода квантового компьютера как языка высокого уровня и приведем пример.

Рассмотрим следующую модель действия квантового компьютера. Несколько тысяч частиц спина У2 (или двухуровневых систем) первоначально находятся в некотором определенном состоянии, например, со всеми спинами вниз. Классическая машина берет отдельные спины или пары спинов и скрещивает их (производя элементарную однобитную перацию Ue или двубитный XOR-гейт); см. рис. 9а, & и с. Эти этапы повторяются на разных парах спинов согласно предписаниям обычной компьютерной программы. Т. к. спины скрещиваются, то мы не должны выделять состояния спинов на промежуточных этапах.

Ф Ф Ф Ф Ф Ф •