Физика квантовой информации - Бауместер Д.
ISBN 5-94057-017-8
Скачать (прямая ссылка):
4.2. 7 Квантовый поиск и NP.
Предположим, что у нас есть база данных, представляющая собой неупорядоченный неструктурированный лист из N записей, по крайней мере, одна из которых удовлетворяет некоторому заданному интересующему нас свойству. Мы хотим найти эту особенную запись. Любому классическому методу, определяющему местонахождение этой записи с некоторой постоянной (не зависящей от N) вероятностью потребуется 0(N) шагов. Ибо, согласно элементарной теории вероятностей, если мы проверим к записей, то найдем нужную с вероятностью k/N. Эта вероятность стремится к 0 при увеличении N, если только само число к - не порядка N. Алгоритм квантового поиска Гровера [120, 150] решает задачу всего лишь за 0(л/гДг) шагов. В этой задаче квантовые эффекты ускоряют решение в корень из числа шагов, в отличие от намного более сильного экспоненциального ускорения в квантовых алгоритмах, которые мы обсуждали выше. В алгоритме Гровера нам потребуется возможность проверять суперпозиции записей, точно так же, как в предыдущих алгоритмах оценивались значения функций от суперпозиций входных данных.
Предположение о неструктурированное™ базы данных очень важно для нашего результата. Например, если бы база данных состояла из N случайных чисел, отсортированных в возрастающем порядке, то нам понадобилось бы всего 0(log N) шагов, чтобы классически (с помощью стандартного метода деления пополам) отыскать любое из этих чисел. Аналогично, можно было бы использовать любую заранее известную структуру базы данных, чтобы уменьшить время поиска. Предположение о неструктурированности аналогично тому, как мы ранее использовали оракулы (или черные ящики), внутренняя структура которых была нам недоступна. На самом деле, можно следую-
Квантовые алгоритмы 161
щим образом более аккуратно переформулировать задачу поиска в базе данных на языке оракулов, нам дан черный ящик, который вычисляет функцию от N входных данных, со значениями на выходе О или 1. Кроме того, известно, что/(х) = 1 только для одного вводного значения х0. Наша задача - найти х0.
Сейчас мы кратко опишем алгоритм квантового поиска Гровера для нахождения х0 за 0( VN) шагов. (Дальнейшие технические детали можно при желании при первом чтении пропустить. Следует только запомнить черты этого алгоритма, описанные выше). Как и при обсуждении алгоритма Дойча и квантового параллельного вычисления, предположим, что оракул задан как унитарное преобразование Uf, которое преобразует |х)|у) в |х)|у ©/(х)). Здесь 1 < х < Л/, j= 0 или 1, и Ф обозначает сложение по модулю 2. Будет также удобно ограничить наше внимание случаем, когда N = 2", то есть, когда N'- степень двойки, так что/есть функция от п битов со значениями на одном бите. Пусть йвп есть гильбертово пространство п кубитов (т.е. входного регистра) со стандартным базисом {|х)}, помеченным всеми «-битными строками х. В своей первоначальной форме алгоритм Гровера основан на двух унитарных операциях, / и D, каждая из которых действует на СВп.
I - это унитарная операция, которая просто инвертирует амплитуду
|*°\
1*о>:
, . fix) если х ^ хп
*Н • (4-30)
0 I-|х) еслих = х0
Ее легко сконструировать с помощью Uf, заранее установив ее выходной регистр (последние и+1 кубитов) в состояние 1/ V2(|0)-|l)), как это мы делали в алгоритме Дойча. Тогда применение Uf будет эквивалентно действию на входном регистре, в то время как выходной регистр останется в состоянии 1/VT(|0)-|1»(CM. Рис. 4.8).
' X ) --------->-
0) - ,1)----------------->
-(-1)/(^|х)=/1о|Л) -|0)- |1)
Рис. 4.8. Создание 1% с помощью Uj. Здесь/обозначает оракул, который помечает *0. 0
Оператор D определяется следующим образом. Пусть Нп обозначает применение Н (см. (4.1)) к каждому из п кубитов, и пусть /0 будет оператором 1х с х = 00...О. Тогда D определяется как
D = -HnI0H„ ,Х° (4.31)
162 Концепция квантовых вычислений
Прямое вычисление матричных элементов D [120, 150] показывает, что все недиагональные матричные элементы равны 2IN, а все диагональные равны -1+2IN (напомним, что здесь N = 2п). Следовательно
cW = -W-<45» ¦ (4'32>
IV у
У D есть простая геометрическая интерпретация: «инверсия относительно среднего». Для любого состояния \у/) = Eojx), положим D\у/) = Ea'Jx), и пусть а=(1 A/V)!^ обозначает среднюю амплитуду для состояния \у/). С помощью (4.32) получаем 2_
N\
Обозначив А а= а- а, получим, что ах-а + А ах на' = а - А ах, так что значения амплитуд просто отражены относительно среднего а.
Чтобы выполнить алгоритм Гровера, начнем с равной суперпозиции |ц/Q) = (lA/TV7)! |х), которую можно приготовить, например, применив Нп к |0...0). Это состояние соответствует проверке всех элементов базы данных в равной суперпозиции. Наша цель - так изменить |\|/0), чтобы сконцентрировать всю амплитуду на х = х0. Алгоритм состоит из многократного применения оператора Dlx , что приводит к последовательности состояний |^/к):
Wk+i) = DI,aWk) ¦ (4.34)
С помощью выражений для D и I , легко видеть, что амплитуды
всех |х) сх^х0 остаются равными друг другу, так что каждое состо-
яние | у/^ имеет вид
