нитарную эволюцию состояний, не должно интерферировать со спинами. Когда этот определенный цикл манипуляций завершен, ориентации спинов измеряются (рис. 9d).

Полученный набор измеренных ориентации является итогом вычисления.

Если задана такая парадигма квантового компьютера, то как может выглядеть его язык высокого уровня (его компьютерный код)? Наиболее серьезная трудность, с которой приходится сталкиваться, состоит в том, что квантовая информация управляется обычным компьютером абсолютно слепым образом - без какого-либо доступа к значениям этой квантовой информации. Это означает, что программа не может использовать сокращения, обусловленные значением квантовой переменной (или регистром, или битом). Например, циклы должны итерироваться точно то же самое число раз независимо от значений квантовых переменных. Аналогично, операции условного перехода через большие куски программы должны быть разбиты на повторяющиеся условия для каждого шага. К тому же каждая команда, выполняемая с квантовыми битами, должна быть логически обратимой. Так, обычное присвоение значения переменной, такое как \а) = п, незаконно, а, вместо этого, оно должно выполняться как приращение первоначально равной нулю переменной \а) = \а) + п.

Пример такой программы, которая могла бы выполняться на этой машине, мог бы выглядеть следующим образом [22

do 10 к = 1, worstdiv

q) = к) + 1

а) = \а) - п if (а) = 0) continue

do 20 к = 1, worstdiv if {к > \q)) \а) = а) + n continue

Этот фрагмент программы может быть использован для вычисления частного и остатка, помещенных в 1) и \а) соответственно, для деления \а) на щ постоянная worstdiv - число раз, которое в худшем случае должен пробегаться цикл. Здесь 1) первоначально равен нулю. Каждая команда здесь - либо обычная компьютерная команда, либо программа, включающая квантовые переменные. Первые являются прямыми командами для внешнего компьютера, в то время как

последние следует интерпретировать как последовательность манипу-яций, которые должны совершаться с квантовыми битами. Так, как на написана, эта программа является необратимой (и также не очень ффективной), например, идентификатор 10 не дает описания того, какой путь должен бы быть использован, чтобы добраться до него. Она, днако, легко может быть переписана [22

9. Квантовый параллелизм. Период последовательности

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

Рассмотрим последовательность

/(0),/(!),...,/(?-1),

где q = 2, чтобы найти ее период, мы используем квантовый парал-елизм. Начнем с совокупности частиц, спины которых первоначально направлены вниз. Сгруппируем их в два набора (два квантовых регистра, или квантовые переменные):

0; 0) . ;, ,...),

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

Применив к каждому биту первого регистра однобитную операцию С/ 7г/2? получим суперпозицию всех возможных двоичных строк длины к в этом регистре:

-;Еа;0>.

V а=0

Следующий шаг состоит в том, что вычисление функции f{a) разбива-тся на ряд однобитных и двубитных унитарных операций. Последовательность операций конструируется таким образом, чтобы преобразовать состояние а;0) в состояние а;/(а)) для любого а. Число битов.

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

V а=0

Экспоненциально большое число вычислений проводится по существу есплатно.

Конечный вычислительный шаг, также как и первый, опять является чисто квантовомеханическим. Рассмотрим дискретное «квантовое» преобразование Фурье первого регистра

егко заметить, что оно обратимо в результате обратного преобразования (нетрудно проверить, что оно унитарно). Эффективный способ вычисления этого преобразования с помощью однобитных и двубитных гейтов был описан Копперсмитом (рис. 10) [23, 24, 6].

Рис. 10. Цепь для квантового преобразования Фурье переменной а/г 1... aitto), использующая метод Копперсмита быстрого преобразования Фурье [23, 24, 6]. Двубитные «Хп»-гейты, в свою очередь, могут быть разложены в некоторые однобитные и XOR-гейты [14].