Квантовые вычисления - Стин Э.
Скачать (прямая ссылка):
(Miquel et. al. 1996), Ведралом (Vedral et. al 1996) и Бекманом (Beckman
et. al 1996) и содержит порядка 300(log7V)3 логических гейтов. Таким
образом, для разложения на множители чисел порядка Ю130, предельных для
современных классических методов решения, необходимо примерно 2 • Ю10
гейтов или 7 часов работы компьютера при "частоте переключения" 1 МГц3.
Принимая в расчет трудности, связанные с созданием квантового компьютера,
можно сказать, что данный алгоритм не обладает преимуществом перед
классическими вычислениями. Однако, если увеличить число десятичных
знаков до 260, то задача может считаться классически неразрешимой (см.
раз-
3Для успешного выполнения алгоритм должен выполняться около log г ~ 60
раз.
Однако в среднем число необходимых выполнений гораздо меньше.
7.3. Алгоритм поиска Гровера
75
дел 3.2). С другой стороны, квантовому компьютеру для ее решения
потребуется лишь в восемь раз больше времени. Существование такого
мощного метода является серьезным познанием в квантовой теории.
На первый взгляд алгоритм определения периода функции похож на фокус:
определение квантовым компьютером периода похоже на вынимание фокусником
кролика из шляпы - не до конца ясно, как это ему удается. Анализируя рис.
11 и уравнения (34)-(38), можно сказать, что наиболее важные особенности
находятся в уравнении (35). Здесь речь идет не столько об уже упомянутом
квантовом параллелизме, сколько о квантовом зацеплении и, в конечном
счете, о квантовой интерференции. Посредством зацепления регистров х и у,
определяемое уравнением (35), каждое значение функции f(x) связано со
своим аргументом х. "Фокус" заключается в том, что при измерении регистра
у квантовое зацепление позволяет создать в регистре х состояние \ф)
(уравнение (36), см. также Jozsa 1997). Заключительное преобразование
Фурье может рассматриваться как интерференция различных наложенных
состояний, находящихся в регистре х (сравните с действием дифракционной
решетки).
Эффект интерференции может использоваться для вычислений с помощью
световых или даже морских волн, т. е. он не является характерной
квантовой особенностью. С другой стороны, в классических системах нельзя
столкнуться с экспоненциально большими числами взаимодействующих
состояний или с зацеплением.
7.3. Алгоритм поиска Гровера
Несмотря на все усилия людей, занимающихся квантовыми вычислениями, число
новых практически важных алгоритмов по-прежнему мало. Как правило, часть
данных алгоритмов представляет варианты вышеуказанного алгоритма поиска
периода функции. Другая часть предназначена для решения совершенно
отличной от первой задачи: поиск записи в неупорядоченной базе данных
(НБД). Гровер (Grover 1997) составил алгоритм для следующей задачи: дана
НБД, содержащая множество записей {ж,}. Необходимо найти запись Х{ = t.
Для примера можно рассматривать поиск номера телефона в справочнике
(причем имя абонента неизвестно). Нетрудно доказать, что классические
алгоритмы сводятся к просмотру БД и при N записях требуют в среднем N/2
шагов.
76
Глава 7
Алгоритму Гровера, в свою очередь, требуется лишь y/N шагов. Данная
задача, с точки зрения вычислений, по-прежнему остается сложной: ее
нельзя отнести к новому классу сложности, однако, что очень важно,
скорость решения даже такой, на первый взгляд, нерешаемой задачи может
быть увеличена. "Квантовая скорость" y/N/2 превышает скорость действия
алгоритма Шора по разложению на множители (~ ехр(2(1п]У)1/,э). Она играет
большую роль при наличии больших множеств (N ~ 1016) как, например, в
случае с задачей дешифрации зашифрованных сообщений (Bassard 1997).
Важно отметить следующее: Беннетт доказал, что алгоритм Гровера является
оптимальным, т. е. что ни один квантовый алгоритм не может работать
быстрее, чем О (y/N).
Не вдаваясь в подробности, работу алгоритма Гровера можно описать
следующим образом: каждая запись имеет метку г, необходимо однозначно
определить, является ли данная запись той, которую нужно найти. Другими
словами, должен существовать единичный оператор S такой, что 5|г) = |г),
если i ф j и S'Ij) = - |j), где j - метка специально определяемого
элемента. Например, проверкой необходимо определить, является ли г
решением некоторой сложной вычислительной задачи4. Как и в случае с
алгоритмом определения периода функции (уравнение (34)) данный метод
начинается с представления одного квантового регистра в виде суперпозиции
всех вычислительных состояний. Определим
|*(9)> = Sm*|j> + -pi?? Ю, <40>
где j - метка записи t = х, которую предстоит найти. Данное начальное
состояние |Ф(0О)>, гДе sinflo = 1 /у/N является равновзвешенной
суперпозицией. Затем необходимо последовательно применить оператор S,
который изменит знак определяемого элемента записи на противоположный,
воспользоваться преобразованием Фурье, изменить знак всех составляющих,
кроме составляющей с состоянием |0) и вновь обратиться к обратному
преобразованию Фурье. В результате данных операций может наблюдаться
