WikiSort.ru - Не сортированное

Алгоритм Гровера (также 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]

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

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

• Алгоритм поиска экстремума целочисленной функции (P. Hoyer и др.). Ищется наибольшее значение функции ${\displaystyle f:\ \{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:\ \{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 }$ .

Примечания

Ссылки

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