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

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

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

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

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

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

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

Смысл алгоритма Гровера состоит в «усилении амплитуды» целевого состояния за счёт убывания амплитуды всех других состояний. Геометрически алгоритм Гровера заключается во вращении текущего вектора состояния квантового компьютера по направлению точно к целевому состоянию (движение по наикратчайшему пути обеспечивает оптимальность алгоритма Гровера). Каждый шаг дает вращение на угол $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}}$ нельзя улучшить.
• Большего квантового ускорения, чем квадратичное, нельзя получить.

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

То, что 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$.

Ссылки

• Гровер Л. К. Квантовая механика помогает найти иголку в стоге сена (для скачивания)
• Логинов О. В. и Цыганов А. В. Квантовый алгоритм Гровера, Санкт-Петербургский Государственный Университет
• Исходные тексты симулятора квантового компьютера на C++ и реализации алгоритма Гровера с подробным описанием и схемами квантовых вентилей