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

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

${\displaystyle (1)\qquad f(x)=1,}$

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

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

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

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

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

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

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

Описание

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

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

Замечания

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

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

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

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

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

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

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

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

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

Примечания

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

Ссылки

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