Лов К. Гровер
(Lov K. Grover) ${ }^{1}$

Хотя транзисторные компьютеры подчиняются квантовой механике, их логические состояния — это только 1 и 0 . Однако, если разрешить квантовую суперпозицию состояний логических элементов, становятся возможными быстрые решения некоторых трудных задач. Один такой пример — поиск полным перебором: нужно опознать элемент, обладающий некоторым специфическим свойством, из неупорядоченного списка из $N$ элементов. Как только элемент проверяется, легко сказать, обладает он или нет этим свойством. Однако список не имеет никакой известной структуры, по которой можно бы было предвидеть, какой из элементов обладает этим свойством с большей вероятностью. При таких условиях любому классическому алгоритму, как вероятностному, так и детерминистическому, потребуется проверить по крайней мере $0.5 \mathrm{~N}$ элементов, чтобы добиться успеха с вероятностью 0.5 . Квантовые компьютеры могут находиться в суперпозиции состояний и одновременно экзаменовать множество элементов; значит, имеется возможность искать быстрее, чем с классическими компьютерами. Не так давно было показано, что квантовый компьютер может осуществить поиск в списке меньше, чем за $\sqrt{N}$ шагов [1]. Этот результат вызвал значительный интерес, так как именно полным перебором решаются некоторые важные задачи [2]. Недавно быстрый квантовый алгоритм поиска был осуществлен на молекулах жидкости с помощью ядерного магнитного резонанса [3]; смотрите также комментарий Джонса в статье [4].

Квантовый алгоритм поиска начинается с перевода состояния системы в суперпозицию $N$ состояний, соответствующих всем $N$ элементам, среди которых производится поиск. После этого можно проверять все $N$ элементов одновременно. Однако, если запрограммировать немедленный вывод проверенного элемента, правильный элемент будет
${ }^{1}$ Bell Labs, Lucent Technologies, Murray Hill, № 107974, USA.

E-mail: lkgrover@bell-labs.com.
Перевод О. Д. Тимофеевской.
Рис. 1. Расщепление личности. Квантово-механические системы могут одновременно находиться во множестве состояний и производить множество вычислений. Алгоритм квантового поиска увеличивает вероятность в желаемом состоянии посредством последовательности простых унитарных операций.

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

Квантовая система определяется заданием амплитуды каждого состоянии, которая в общем случае есть комплексное число, и вероятность каждого состояния — это квадрат абсолютной величины этой амплитуды. В точности так же, как классические вероятностные процессы, квантовые операции должны следовать своему собственному закону сохранения, который приводит к ограничению, что все квантовые операции должны быть унитарны; то есть они должны быть жесткими вращениями амплитуд вектора состояния в $N$-мерном пространстве состояний. Это приводит к волновому поведению частиц на микроскопическом уровне. Среди многих квантовых преобразований есть две элементарные квантовые операции — это квантовая диффузия и фазовые вращения. Фактически, квантовый алгоритм поиска состоит из чередующейся последовательности операций квантовой диффузии и квантовых вращений.

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

Рис. 2. От состояния к состоянию. Квантовая диффузия — это перенос малой мнимой амплитуды от одного состояния к другому. Если фаза одного состояния повернута по отношению к фазе другого, имеется суммарный перенос от одного состояния к другому.

повернута по отношению к амплитуде в другом состоянии, тогда имеется суммарный перенос от одного состояния к другому. Как результат этого переноса, результирующий угол поворота между двумя состояниями уменьшается. В уравнении Шредингера, когда состояния — точки мельчайшей решетки, имеется квантовая диффузия между соседними точками решетки вместе с непрерывным поворотом фазы, который определяется потенциалом. В результате возникает средний перенос в состояния с низким потенциалом, как раз то, что можно ожидать классически.

В точности как и классический компьютер, квантовый компьютер может быть представлен множеством бинарных систем. Каждая бинарная система — это квантово-механический бит, называемый кубитом, который находится в суперпозиции двух состояний. Квантовый алгоритм поиска начинается с установки системы $n$ кубитов в однородную суперпозицию всех $N=2^{n}$ состояний. Затем проводится чередующаяся последовательность квантовых диффузий и фазовых поворотов. После примерно $\pi \sqrt{N / 4}$ повторений амплитуда концентрируется на требуемом состоянии. Теперь измерение обнаруживает нужное состояние с достоверностью.

Версия этого алгоритма была недавно осуществлена для частного случая $N=4$ с помощью техники ядерного магнитного резонанса на органической молекуле в качестве двубитного квантового компьютеpa $[3,4]$.

Чтобы с достоверностью найти элемент в неупорядоченном списке из четырех элементов, потребовался один-единственный вопрос; любой классический алгоритм потребова. бы в среднем 2.25 вопросов, а в наихудшем случае — 3 вопроса.
Такие вехи прогресса, как демонстрация важного квантового алгоритма, предоставляют удобный случай остановиться и по достоинству оценить состояние искусства. Есть два вида задач, стоящих перед квантовыми компьютерами: аппаратное обеспечение и программное обеспечение. Аппаратные проблемы возникают из того факта, что физика квантовых вычислительных приборов отлична от физики существующих, и мы не знаем, какой будет их конечная структура. Здесь должны быть удовлетворены в какой-то мере противоречивые требования: во-первых, компьютер должен быть изолирован, чтобы предотвратить возмущения окружающей среды, и, во-вторых, различные части системы должны взаимодействовать контролируемым образом. Существующие приборы, такие как транзисторы, очень тесно связаны с окружающей средой. Ядерный магнитный резонанс в некоторой степени удовлетворяет обоим условиям. Следующая большая аппаратная проблема состоит в увеличении числа кубитов от двух до величины порядка пяти-десяти, что допустит более мудреные алгоритмы. Проблема программного обеспечения: найти применения, которые оправдают усилия, затраченные на строительство квантового компьютера. Показано, что квантовый алгоритм поиска не может быть еще больше улучшен для приложений к задачам, решаемых полным перебором. Тем не менее, существуют многочисленные возможности его применения к другим задачам.