В 1994 году Шор открыл квантовый алгоритм факторизации, скорость которого экспоненциально велика по сравнению со скоростью известных классических алгоритмов [1]. В данной статье представлен квантовый алгоритм поиска, который работает всего лишь полиномиально быстрее, чем любой классический алгоритм; однако это не связано с тем, что он наталкивается на недоказанные трудности проблемы факторизации. Задача поиска состоит в следующем: имеется неупорядоченная база данных, состоящая из $N$ элементов, из которых лишь
${ }^{1}$ 3C-404A Bell Labs, 600 Mountain Avenue, Murray Hill NJ 07974.

E-mail: lkgrover@bell-labs.com
(C) Phys. Rev. Lett., 79(2), 325-328 (1997).
Перевод О. Д. Тимофеевской.
один удовлетворяет данным условиям – именно этот элемент нужно найти. Если элемент можно осмотреть, то определение того, удовлетворяет он требуемым условиям или нет, осуществляется за один шаг. Однако база данных такова, что в ней не существует какого-либо упорядочения, которое могло бы помочь выбору элемента. Наиболее эффективный классический алгоритм для этой задачи состоит в проверке элементов из базы данных одного за другим. Если элемент удовлетворяет требуемым условиям, поиск окончен, если нет, то данный элемент откладывается так, так чтобы он вновь не подвергался проверке. Очевидно, что в этом алгоритме требуется проверить в среднем $\frac{N}{2}$ элементов прежде, чем будет найден нужный.

В квантово-механической системе можно произвести свободное от взаимодействия измерение методом, использующим дуальные свойства фотонов [2]. В этом методе можно определить присутствие (или отсутствие) объекта, допуская очень малую вероятность взаимодействия фотона с объектом. Следовательно, более вероятно, что фотон не будет взаимодействовать, однако даже возможности взаимодействия с малой вероятностью оказывается достаточно, чтобы произвести измерение. Таким образом, в задаче поиска также возможно обнаружить объект без обследования всех объектов, если лишь допустима определенная вероятность подвергнуть проверке нужный объект.

Данная работа показывает, что, используя то же самое оборудование, как в классическом случае, но задавая вход и выход в виде cynерпозиции состояний, можно найти объект за $O(\sqrt{N})$ квантовомеханических шагов вместо $O(N)$ классических шагов. Каждый квантовомеханический шаг состоит из элементарной унитарной операции (их мы обсудим в следующем параграфе).