Алгоритм Гровера

Алгоритм Гровера (также GSA от англ. Grover search algorithm) — квантовый алгоритм решения задачи перебора, то есть нахождения решения уравнения

(1)\qquad f(x)=1,

где $f$ есть булева функция от n переменных.^[1] Был предложен американским математиком Ловом Гровером в 1996 году.

Предполагается, что функция $f$ задана в виде чёрного ящика, или оракула, то есть в ходе решения можно задавать оракулу только вопрос типа: «чему равна $f$ на данном $x$ ?», и использовать ответ в дальнейших вычислениях. То есть, задача решения уравнения (1) является общей формой задачи перебора: здесь требуется отыскать «пароль к устройству $f$ », что классически требует полного перебора всех $N=2^{n}$ вариантов.

Алгоритм Гровера находит какой-нибудь корень уравнения, используя ${\frac {\pi }{4}}{\sqrt {N}}$ обращений к функции $f$ , с использованием $O(n)$ кубитов.^[2]

Смысл алгоритма Гровера состоит в «усилении амплитуды^[англ.]» целевого состояния за счёт убывания амплитуды всех других состояний. Геометрически алгоритм Гровера заключается во вращении текущего вектора состояния квантового компьютера по направлению точно к целевому состоянию (движение по наикратчайшему пути обеспечивает оптимальность алгоритма Гровера). Каждый шаг дает вращение на угол $2\alpha$ , где угол между $I_{\tilde {0}}$ и $I_{x_{tar}}$ составляет $\pi /2-\alpha$ . Дальнейшее продолжение итераций оператора G даст продолжение обхода окружности в вещественной плоскости, порождённой данными векторами.

Гроверовское «усиление амплитуды» является, по-видимому, фундаментальным физическим феноменом в квантовой теории многих тел. Например, его учёт необходим для оценки вероятностей событий, которые кажутся «редкими». Процесс, реализующий схему алгоритма Гровера, приводит к взрывному росту первоначально пренебрежимо малой амплитуды, что способно быстро довести её до реально наблюдаемых величин.

Алгоритм Гровера также может быть использован для нахождения медианы и среднего арифметического числового ряда. Кроме того, он может применяться для решения NP-полных задач путём исчерпывающего поиска среди множества возможных решений. Это может повлечь значительный прирост скорости по сравнению с классическими алгоритмами, хотя и не предоставляя «полиномиального решения» в общем виде.

Описание

Пусть $I_{a}$ есть унитарный оператор, зеркально отражающий гильбертово пространство относительно гиперплоскости, перпендикулярной вектору $a$ , $|x_{tar}\rangle$ — состояние, соответствующее корню уравнения (1), $|{\tilde {0}}\rangle ={\frac {1}{\sqrt {N}}}\sum \limits _{j}|j\rangle$ — равномерная суперпозиция всех состояний.

Алгоритм Гровера состоит в применении оператора $G=-I_{\tilde {0}}I_{x_{tar}}$ к состоянию $|{\tilde {0}}\rangle$ число раз, равное целой части $\pi {\sqrt {N}}/4$ . Результат будет почти совпадать с состоянием $|x_{tar}\rangle$ . Измерив полученное состояние, получаем ответ с вероятностью, близкой к единице.

Замечания

Предположим, уравнение (1) имеет $l$ корней. Классический алгоритм решения такой задачи (линейный поиск), очевидно, требует $O({\tfrac {N}{l}})$ обращений к $f$ для того, чтобы решить задачу с вероятностью ${\tfrac {1}{2}}$ . Алгоритм Гровера позволяет решить задачу поиска за время $O({\sqrt {\tfrac {N}{l}}})$ , то есть порядка квадратного корня из классического, что является огромным ускорением. Доказано, что Алгоритм Гровера является оптимальным в следующих отношениях:

Константу ${\tfrac {\pi }{4}}$ нельзя улучшить^[3].
Большего квантового ускорения, чем квадратичное, нельзя получить^[4].

Алгоритм Гровера есть пример массовой задачи, зависящей от оракула. Для более частных задач удаётся получить большее квантовое ускорение. Например, алгоритм факторизации Шора даёт экспоненциальный выигрыш по сравнению с соответствующими классическими алгоритмами.

То, что f задана в виде чёрного ящика, никак не влияет в общем случае на сложность как квантовых, так и классических алгоритмов. Знание «устройства» функции f (например, знание задающей её схемы из функциональных элементов) в общем случае никак не может помочь в решении уравнения (1). Поиск в базе данных соотносится с обращением функции, которая принимает определённое значение, если аргумент x соответствует искомой записи в базе данных.

Алгоритмы, использующие схему Гровера

Алгоритм поиска экстремума целочисленной функции (P. Hoyer и др.). Ищется наибольшее значение функции $f\colon \{0,1\}^{n}\rightarrow \{0,1\}^{n}$ . Квантовый алгоритм находит максимум за $O({\sqrt {N}})$ обращений к f.
Алгоритм структурного поиска (Farhi, Gutman). Ищется решение уравнения (1) при дополнительном условии $g(x_{1})=1$ , где $x=x_{1}x_{2}$ разбиение строки $x$ на две строки одинаковой длины. Алгоритм имеет сложность порядка квадратного корня из классического времени.
Алгоритм поиска совпадающих строк в базе данных (Амбайнис). Ищется пара разных аргументов $x_{1}\neq x_{2}$ , на которых функция $f\colon \{0,1\}^{n}\rightarrow \{0,1\}^{n}$ принимает одно и то же значение. Алгоритм требует $O(N^{3/4})$ обращений к f.

Вариации и обобщения

Непрерывные версии алгоритма Гровера

Пусть гамильтониан квантовой системы имеет вид $H=H_{1}+H_{2}$ , где $\exp(iH_{1})$ и $\exp(iH_{2})$ представляют собой операторы $I_{\tilde {0}}$ и $I_{x_{tar}}$ соответственно. Тогда непрерывная унитарная эволюция с гамильтонианом $H$ , стартуя с $|{\tilde {0}}\rangle$ , естественно приводит к $|x_{tar}\rangle$ . Сложность такого непрерывного аналога алгоритма Гровера точно та же, что и для дискретного случая.
Адиабатический вариант алгоритма Гровера. Медленная эволюция основного состояния типа $|{\tilde {0}}\rangle$ под действием гамильтониана, зависящего от f, согласно адиабатической теореме, за время порядка ${\sqrt {N}}$ ведет к состоянию $|x_{tar}\rangle$ .

Примечания

↑ Иногда GSA неточно называют поиском в базе данных.
↑ Сложность работы алгоритма, для задачи с оракулом называемая ещё временем его работы, определяется числом обращений к оракулу.
↑ Christof Zalka, Grover’s quantum searching algorithm is optimal, Phys.Rev. A60 (1999) 2746—2751 [1] (недоступная ссылка)
↑ Yuri Ozhigov, Lower Bounds of Quantum Search for Extreme Point, Proc.Roy.Soc.Lond. A455 (1999) 2165—2172 [2]