5.8. Алгоритм Гровера
Алгоритм Гровера
направлен на поиск записи в
неструктурированной базе данных. Он
обеспечивает поиск решения за
шагов в базе из
элементов. Заметим, что классический
алгоритм способен решит задачу только
за
шагов.
Рассмотрим квантовую постановку задачи. Пусть имеется состояний.
Допустим, что
задача имеет
решений (
).
-
частный случай в рассматриваемой
постановке.
Рассмотрим функцию
такую, что
,
если
- решение и
,
если
не есть решение. Унитарный оператор
,
обеспечивающий рассматриваемую функцию,
называется оракулом и обозначается
буквой
.
Действие оракула поясняется схемой
Рис. 5.9 Схема действия оракула
Таким образом, оракул выполняет следующее преобразование
Оракул способен распознать решение и пометить его:
,
если
- решение
,
если
не есть решение
Пусть состояния
,
где
мы поочередно подаем на вход оракула и
ждем, когда кубит оракула перевернётся
и тем самым будет получено решение.
Очевидно, что таким образом будет
реализован небыстрый алгоритм поиска
и он будет обеспечивать решение за
шагов.
Наша задача состоит в том, чтобы за счёт квантового параллелизма (т.е. за счет подачи на вход некоторой суперпозиции состояний) предложить быстрый алгоритм, обеспечивающий поиск за шагов.
Последовательность осуществления алгоритма следующая.
Пусть
.
Такое состояние уже использовалось
нами в реализации алгоритма Дойча. Это
состояние играет роль «катализатора»,
который сам не меняется, но обеспечивает
изменение состояния других кубитов.
Действительно, действие оракула в
рассматриваемом случае сводится к
преобразованию:
Договоримся о сокращенной записи (опуская неизменный кубит- «катализатор»)
Таким образом, мы видим, что оракул помечает решение посредством фазы .
Введем теперь некоторый унитарный оператор (так называемый оператор условного сдвига фазы)
,
где - единичный (тождественный) оператор.
Покажем, что введенный выше оператор действительно является унитарным. Используем условие полноты системы базисных функций
Тогда для оператора условного сдвига фазы получаем
Отсюда видим, что
и
,
если
Рассмотрим теперь состояние, играющее центральную роль в квантовых алгоритмах и неоднократно использовавшееся нами ранее. Это состояние представляет собой равномерную суперпозицию всех базисных состояний:
Далее значком
будем обозначать это конкретное
состояние.
Задача 5.16 Докажите справедливость тождества
Теперь мы готовы
ввести оператор Гровера. Он определяется
последовательностью двух операторов:
действием сперва оракулом
,
а затем оператором
,
в результате получаем оператор Гровера:
Решение задачи поиска сводится к последовательному действию оператором Гровера на исходное состояние . Опишем подробности алгоритма.
Заметим вначале, что состояние можно представить в виде суперпозиции двух состояний, одно из которых есть сумма всех решений, а другое- сумма всех «не- решений»:
Здесь
-
нормированная сумма всех решений
Аналогично,
-
нормированная сумма всех «не- решений»
В представленных формулах мы помечаем решения одним штрихом, а «не- решения»- двумя штрихами.
Действие оператора Гровера лучше всего изображать графически на двумерном графике, оси которого образованы состояниями и . Действие оператора оракула сводится к отражению относительно оси . Аналогично, действие оператора сводится к отражению относительно состояния . Первая итерация Гровера изображена на рисунке
Рис.5.10 Графическая иллюстрация алгоритма Гровера
Задача 5.17
Пусть
,
.
Покажите, что результат действия
итераций Гровера может быть представлен
в виде:
Из полученного результата мы видим, итерации Гровера приводят к постепенному вращению вектора состояния в сторону вертикальной оси (т.е. в сторону решений задачи). Итерационный процесс следует закончить, когда будет приближенно выполняться равенство:
Отсюда следует, что необходимое число итераций задается приближенно условием:
В результате измерения, проведенного после итераций Гровера с высокой (хотя и не равной единице) вероятностью будет найдено одно из решений задачи поиска.
Алгоритм Гровера имеет важное значение в области квантового моделирования