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

В квантовых вычислениях , алгоритм Гровера также известный как алгоритм квантового поиска , представляет собой квантовый алгоритм неструктурированного поиска, который с высокой вероятностью находит уникальные входные данные для функции черного ящика , которая создает определенное выходное значение, используя всего лишь $O({\sqrt {N}})$ оценки функции, где $N$ функции — размер области определения . Его разработал Лов Гровер в 1996 году.

Аналогичная задача в классических вычислениях не может быть решена менее чем за $O(N)$ оценки (поскольку в среднем нужно проверить половину домена, чтобы получить 50% шанс найти правильный ввод). Чарльз Х. Беннетт , Итан Бернштейн, Жиль Брассар и Умеш Вазирани доказали, что любое квантовое решение проблемы должно оценивать функцию $\Omega ({\sqrt {N}})$ раз, поэтому алгоритм Гровера асимптотически оптимален . Поскольку классические алгоритмы для NP-полных задач требуют экспоненциально большого количества шагов, а алгоритм Гровера обеспечивает не более чем квадратичное ускорение по сравнению с классическим решением для неструктурированного поиска, это предполагает, что алгоритм Гровера сам по себе не обеспечит решения за полиномиальное время для NP-полных задач ( поскольку квадратный корень из показательной функции является экспоненциальной, а не полиномиальной функцией).

В отличие от других квантовых алгоритмов, которые могут обеспечить экспоненциальное ускорение по сравнению со своими классическими аналогами, алгоритм Гровера обеспечивает только квадратичное ускорение. Однако даже квадратичное ускорение оказывается значительным, когда $N$ велик, и алгоритм Гровера можно применять для ускорения работы широких классов алгоритмов. Алгоритм Гровера мог подобрать 128-битный симметричный криптографический ключ примерно за 2 ⁶⁴ итераций или 256-битный ключ примерно за 2 ¹²⁸ итерации. Однако это может быть не так, что алгоритм Гровера представляет значительно повышенный риск шифрования по сравнению с существующими классическими алгоритмами.

Приложения и ограничения

Алгоритм Гровера, наряду с такими вариантами, как усиление амплитуды , можно использовать для ускорения широкого спектра алгоритмов. В частности, алгоритмы для NP-полных задач, которые содержат в качестве подпрограммы исчерпывающий перебор, могут быть ускорены с помощью алгоритма Гровера. Текущий теоретически лучший алгоритм с точки зрения сложности в наихудшем случае для 3SAT является одним из таких примеров. Общие проблемы удовлетворения ограничений также приводят к квадратичному ускорению с Гровером. Эти алгоритмы не требуют, чтобы входные данные были даны в форме оракула, поскольку алгоритм Гровера применяется с явной функцией, например, функцией проверки того, что набор битов удовлетворяет экземпляру 3SAT. Однако неясно, сможет ли алгоритм Гровера ускорить лучшие практические алгоритмы для решения этих задач.

Алгоритм Гровера также может обеспечить доказуемое ускорение решения задач черного ящика при сложности квантовых запросов , включая различимость элементов. и проблема столкновения (решено с помощью алгоритма Брассара – Хойера – Тэппа ). В задачах такого типа функция оракула f рассматривается как база данных, и цель состоит в том, чтобы использовать квантовый запрос к этой функции как можно меньше раз.

Криптография

Алгоритм Гровера по сути решает задачу обращения функции . Грубо говоря, если у нас есть функция $y=f(x)$ которые можно вычислить на квантовом компьютере, алгоритм Гровера позволяет нам вычислить $x$ когда дано $y$. Следовательно, алгоритм Гровера обеспечивает широкое асимптотическое ускорение многих видов атак методом перебора на криптографию с симметричным ключом , включая атаки коллизий и атаки прообразов . Однако это не обязательно может быть самый эффективный алгоритм, поскольку, например, алгоритм параллельного ро может находить коллизии в SHA2 более эффективно, чем алгоритм Гровера.

Ограничения

В оригинальной статье Гровера этот алгоритм описывался как алгоритм поиска в базе данных, и это описание до сих пор распространено. База данных в этой аналогии представляет собой таблицу всех выходных данных функции, индексированных по соответствующим входным данным. Однако эта база данных не представлена ​​явно. Вместо этого вызывается оракул для оценки элемента по его индексу. Чтение всей базы данных поэлементно и преобразование ее в такое представление может занять намного больше времени, чем поиск Гровера. Чтобы учесть такие эффекты, алгоритм Гровера можно рассматривать как решение уравнения или удовлетворение ограничения . В таких приложениях оракул является способом проверки ограничения и не связан с алгоритмом поиска. Такое разделение обычно предотвращает алгоритмическую оптимизацию, тогда как традиционные алгоритмы поиска часто полагаются на такую ​​оптимизацию и избегают исчерпывающего поиска. К счастью, быстрая реализация оракула Гровера возможна для многих задач удовлетворения ограничений и оптимизации.

Основным препятствием для реализации ускорения с помощью алгоритма Гровера является то, что достигаемое квадратичное ускорение слишком скромное, чтобы преодолеть большие накладные расходы ближайших квантовых компьютеров. Однако более поздние поколения отказоустойчивых квантовых компьютеров с более высокой производительностью оборудования, возможно, смогут реализовать такое ускорение для практических случаев обработки данных.

Описание проблемы

Предположим, что в качестве входных данных для алгоритма Гровера у нас есть функция $f\colon \{0,1,\ldots ,N-1\}\to \{0,1\}$. В аналогии с «неструктурированной базой данных» домен представляет собой индексы базы данных, а f ( x ) = 1 тогда и только тогда, когда данные, на которые указывает x, удовлетворяют критерию поиска. Мы дополнительно предполагаем, что только один индекс удовлетворяет условию f ( x ) = 1 , и называем этот индекс ω . Наша цель — идентифицировать ω .

Мы можем получить доступ к f с помощью подпрограммы (иногда называемой оракулом ) в форме унитарного оператора U _ω , который действует следующим образом:

${\begin{cases}U_{\omega }|x\rangle =-|x\rangle &{\text{for }}x=\omega {\text{, that is, }}f(x)=1,\\U_{\omega }|x\rangle =|x\rangle &{\text{for }}x\neq \omega {\text{, that is, }}f(x)=0.\end{cases}}$

При этом используется $N$-мерное пространство состояний ${\mathcal {H}}$, который предоставляется регистром с $n=\lceil \log _{2}N\rceil$ кубиты . Часто это пишут как

$U_{\omega }|x\rangle =(-1)^{f(x)}|x\rangle .$

Алгоритм Гровера выводит ω с вероятностью не менее 1/2, используя $O({\sqrt {N}})$ приложения U _ω . Эту вероятность можно сделать сколь угодно большой, запустив алгоритм Гровера несколько раз. Если использовать алгоритм Гровера до тех пор, пока не будет найдено ω , ожидаемое количество приложений по-прежнему будет $O({\sqrt {N}})$, поскольку в среднем он будет запускаться только дважды.

Альтернативное определение оракула

В этом разделе сравнивается приведенный выше оракул $U_{\omega }$ с оракулом $U_{f}$.

U _ω отличается от стандартного квантового оракула для функции f . Этот стандартный оракул, обозначенный здесь как U _f , использует вспомогательную систему кубитов . Тогда операция представляет собой инверсию ( НЕ-вентиль ) в основной системе, обусловленную значением f ( x ) из вспомогательной системы:

${\begin{cases}U_{f}|x\rangle |y\rangle =|x\rangle |\neg y\rangle &{\text{for }}x=\omega {\text{, that is, }}f(x)=1,\\U_{f}|x\rangle |y\rangle =|x\rangle |y\rangle &{\text{for }}x\neq \omega {\text{, that is, }}f(x)=0,\end{cases}}$

или кратко,

$U_{f}|x\rangle |y\rangle =|x\rangle |y\oplus f(x)\rangle .$

Эти оракулы обычно реализуются с использованием невычислений .

Если нам дан U _f в качестве нашего оракула, то мы также можем реализовать U _ω , поскольку U _ω — это U _f, когда вспомогательный кубит находится в состоянии $|-\rangle ={\frac {1}{\sqrt {2}}}{\big (}|0\rangle -|1\rangle {\big )}=H|1\rangle$:

${\begin{aligned}U_{f}{\big (}|x\rangle \otimes |-\rangle {\big )}&={\frac {1}{\sqrt {2}}}\left(U_{f}|x\rangle |0\rangle -U_{f}|x\rangle |1\rangle \right)\\&={\frac {1}{\sqrt {2}}}\left(|x\rangle |f(x)\rangle -|x\rangle |1\oplus f(x)\rangle \right)\\&={\begin{cases}{\frac {1}{\sqrt {2}}}\left(-|x\rangle |0\rangle +|x\rangle |1\rangle \right)&{\text{if }}f(x)=1,\\{\frac {1}{\sqrt {2}}}\left(|x\rangle |0\rangle -|x\rangle |1\rangle \right)&{\text{if }}f(x)=0\end{cases}}\\&=(U_{\omega }|x\rangle )\otimes |-\rangle \end{aligned}}$

Итак, алгоритм Гровера можно запускать независимо от того, какой оракул задан. Если U _{f , то мы должны поддерживать дополнительный кубит в состоянии} задан $|-\rangle$ и примените U _f вместо U _ω .

Алгоритм

Представление квантовой схемы алгоритма Гровера

Шаги алгоритма Гровера выглядят следующим образом:

1. Инициализируйте систему для равномерной суперпозиции всех состояний.
   $|s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle .$
2. Выполните следующую «итерацию Гровера» $r(N)$ раз:
   1. Применить оператор $U_{\omega }$
   2. Примените диффузии Гровера оператор $U_{s}=2\left|s\right\rangle \left\langle s\right|-I$
3. Измерьте полученное квантовое состояние в вычислительной базе.

При правильно выбранном значении $r$, результат будет $|\omega \rangle$ с вероятностью, приближающейся к 1 при N ≫ 1. Анализ показывает, что это возможное значение для $r(N)$ удовлетворяет $r(N)\leq {\Big \lceil }{\frac {\pi }{4}}{\sqrt {N}}{\Big \rceil }$.

Реализация шагов этого алгоритма может быть выполнена с использованием ряда вентилей, линейных по количеству кубитов. Таким образом, сложность вентиля этого алгоритма равна $O(\log(N)r(N))$, или $O(\log(N))$ за итерацию.

Геометрическое доказательство правильности

На рисунке показана геометрическая интерпретация первой итерации алгоритма Гровера. Вектор состояния $|s\rangle$ поворачивается к целевому вектору $|\omega \rangle$ как показано.

Существует геометрическая интерпретация алгоритма Гровера, следующая из наблюдения, что квантовое состояние алгоритма Гровера после каждого шага остается в двумерном подпространстве. Рассмотрим плоскость, натянутую на $|s\rangle$ и $|\omega \rangle$; эквивалентно, плоскость, охватываемая $|\omega \rangle$ и перпендикулярный кет $\textstyle |s'\rangle ={\frac {1}{\sqrt {N-1}}}\sum _{x\neq \omega }|x\rangle$.

Алгоритм Гровера начинается с начального кет $|s\rangle$, лежащий в подпространстве. Оператор $U_{\omega }$ является отражением в гиперплоскости, ортогональной $|\omega \rangle$ для векторов в плоскости, натянутой на $|s'\rangle$ и $|\omega \rangle$, т. е. он действует как отражение через $|s'\rangle$. Это можно увидеть, написав $U_{\omega }$ в форме отражения Домохозяина :

$U_{\omega }=I-2|\omega \rangle \langle \omega |.$

Оператор $U_{s}=2|s\rangle \langle s|-I$ является отражением через $|s\rangle$. Оба оператора $U_{s}$ и $U_{\omega }$ брать состояния в плоскости, охватываемой $|s'\rangle$ и $|\omega \rangle$ состояниям в плоскости. Следовательно, алгоритм Гровера остается в этой плоскости на протяжении всего алгоритма.

Несложно проверить, что оператор $U_{s}U_{\omega }$ каждого шага итерации Гровера поворачивает вектор состояния на угол $\theta =2\arcsin {\tfrac {1}{\sqrt {N}}}$. Итак, при достаточном количестве итераций можно повернуть из начального состояния $|s\rangle$ в желаемое состояние вывода $|\omega \rangle$. Исходный кет близок к состоянию, ортогональному $|\omega \rangle$:

$\langle s'|s\rangle ={\sqrt {\frac {N-1}{N}}}.$

В геометрическом плане угол $\theta /2$ между $|s\rangle$ и $|s'\rangle$ дается

$\sin {\frac {\theta }{2}}={\frac {1}{\sqrt {N}}}.$

Нам нужно остановиться, когда вектор состояния пройдет близко к $|\omega \rangle$; последующие итерации поворачивают вектор состояния от после этого $|\omega \rangle$, уменьшая вероятность получения правильного ответа. Точная вероятность измерения правильного ответа равна

$\sin ^{2}\left({\Big (}r+{\frac {1}{2}}{\Big )}\theta \right),$

где r — (целое) количество итераций Гровера. Таким образом, самый ранний момент, когда мы получаем почти оптимальное измерение, — это $r\approx \pi {\sqrt {N}}/4$.

Алгебраическое доказательство правильности

Чтобы завершить алгебраический анализ, нам нужно выяснить, что произойдет, если мы неоднократно применим $U_{s}U_{\omega }$. Естественный способ сделать это — провести анализ собственных значений матрицы. Обратите внимание, что в течение всего расчета состояние алгоритма представляет собой линейную комбинацию $s$ и $\omega$. Мы можем написать действие $U_{s}$ и $U_{\omega }$ в пространстве, охватываемом $\{|s\rangle ,|\omega \rangle \}$ как:

$U_{s}:a|\omega \rangle +b|s\rangle \mapsto [|\omega \rangle \,|s\rangle ]{\begin{bmatrix}-1&0\\2/{\sqrt {N}}&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}.$

$U_{\omega }:a|\omega \rangle +b|s\rangle \mapsto [|\omega \rangle \,|s\rangle ]{\begin{bmatrix}-1&-2/{\sqrt {N}}\\0&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}.$

Итак, в основе $\{|\omega \rangle ,|s\rangle \}$ (который не является ни ортогональным, ни базисом всего пространства) действие $U_{s}U_{\omega }$ применения $U_{\omega }$ с последующим $U_{s}$ задается матрицей

$U_{s}U_{\omega }={\begin{bmatrix}-1&0\\2/{\sqrt {N}}&1\end{bmatrix}}{\begin{bmatrix}-1&-2/{\sqrt {N}}\\0&1\end{bmatrix}}={\begin{bmatrix}1&2/{\sqrt {N}}\\-2/{\sqrt {N}}&1-4/N\end{bmatrix}}.$

Эта матрица имеет очень удобную жорданову форму . Если мы определим $t=\arcsin(1/{\sqrt {N}})$, это

$U_{s}U_{\omega }=M{\begin{bmatrix}e^{2it}&0\\0&e^{-2it}\end{bmatrix}}M^{-1}$ где $M={\begin{bmatrix}-i&i\\e^{it}&e^{-it}\end{bmatrix}}.$

Отсюда следует, что r -я степень матрицы (соответствующая r итерациям) равна

$(U_{s}U_{\omega })^{r}=M{\begin{bmatrix}e^{2rit}&0\\0&e^{-2rit}\end{bmatrix}}M^{-1}.$

Используя эту форму, мы можем использовать тригонометрические тождества для вычисления вероятности наблюдения ω после r итераций, упомянутых в предыдущем разделе:

$\left|{\begin{bmatrix}\langle \omega |\omega \rangle &\langle \omega |s\rangle \end{bmatrix}}(U_{s}U_{\omega })^{r}{\begin{bmatrix}0\\1\end{bmatrix}}\right|^{2}=\sin ^{2}\left((2r+1)t\right).$

В качестве альтернативы можно было бы разумно предположить, что почти оптимальное время для различения будет тогда, когда углы 2 rt и −2 rt находятся как можно дальше друг от друга, что соответствует $2rt\approx \pi /2$, или $r=\pi /4t=\pi /4\arcsin(1/{\sqrt {N}})\approx \pi {\sqrt {N}}/4$. Тогда система находится в состоянии

$[|\omega \rangle \,|s\rangle ](U_{s}U_{\omega })^{r}{\begin{bmatrix}0\\1\end{bmatrix}}\approx [|\omega \rangle \,|s\rangle ]M{\begin{bmatrix}i&0\\0&-i\end{bmatrix}}M^{-1}{\begin{bmatrix}0\\1\end{bmatrix}}=|\omega \rangle {\frac {1}{\cos(t)}}-|s\rangle {\frac {\sin(t)}{\cos(t)}}.$

Короткий расчет теперь показывает, что наблюдение дает правильный ответ ω с ошибкой. $O\left({\frac {1}{N}}\right)$.

Расширения и варианты

Несколько совпадающих записей

Дополнительная информация: Усиление амплитуды.

Если вместо 1 совпадающей записи есть k совпадающих записей, работает тот же алгоритм, но количество итераций должно быть ${\textstyle {\frac {\pi }{4}}{\left({\frac {N}{k}}\right)^{1/2}}}$вместо ${\textstyle {\frac {\pi }{4}}{N^{1/2}}.}$

Есть несколько способов справиться со случаем, когда k неизвестно. Простое решение работает оптимально до постоянного коэффициента: многократно запускайте алгоритм Гровера для все более малых значений k , например, принимая k = N , N /2, N /4,... и т. д., принимая $k=N/2^{t}$ для итерации t, пока не будет найдена соответствующая запись.

С достаточно высокой вероятностью помеченная запись будет найдена итерацией $t=\log _{2}(N/k)+c$ для некоторой постоянной c . Таким образом, общее число выполненных итераций не превышает

${\frac {\pi }{4}}{\Big (}1+{\sqrt {2}}+{\sqrt {4}}+\cdots +{\sqrt {\frac {N}{k2^{c}}}}{\Big )}=O{\big (}{\sqrt {N/k}}{\big )}.$

Другой подход, если k неизвестен, состоит в том, чтобы получить его с помощью предварительного алгоритма квантового счета .

Если $k=N/2$ (или традиционный с пометкой «Алгоритм Гровера», если он запущен с $N=2$), алгоритм не обеспечит усиления. Если $k>N/2$, увеличение k начнет увеличивать количество итераций, необходимых для получения решения. С другой стороны, если $k\geq N/2$, классический запуск проверяющего оракула на одном случайном выборе входных данных, скорее всего, даст правильное решение.

Версия этого алгоритма используется для решения проблемы столкновений .

Квантовый частичный поиск

Модификация алгоритма Гровера, называемая квантовым частичным поиском, была описана Гровером и Радхакришнаном в 2004 году. При частичном поиске не требуется находить точный адрес целевого элемента, а только первые несколько цифр адреса. Аналогично, мы можем подумать о «разбиении» пространства поиска на блоки, а затем спросить: «В каком блоке находится целевой элемент?». Во многих приложениях такой поиск дает достаточно информации, если целевой адрес содержит нужную информацию. Например, если использовать пример, приведенный Л.К. Гровером, если у кого-то есть список студентов, организованный по классам, нас может интересовать только то, находится ли студент в нижних 25%, 25–50%, 50–75% или 75–100% процентиль.

Для описания частичного поиска мы рассматриваем базу данных, разделенную на $K$ блоки, каждый размером $b=N/K$. Задача частичного поиска проще. Рассмотрим классический подход: мы выбираем один блок наугад, а затем выполняем обычный поиск по остальным блокам (на языке теории множеств — дополнению). Если мы не находим цель, то знаем, что она находится в блоке, который мы не искали. Среднее количество итераций снижается с $N/2$ к $(N-b)/2$.

Алгоритм Гровера требует ${\textstyle {\frac {\pi }{4}}{\sqrt {N}}}$ итерации. Частичный поиск будет быстрее в числовом коэффициенте, который зависит от количества блоков. $K$. Частичный поиск использует $n_{1}$ глобальные итерации и $n_{2}$ локальные итерации. Назначен глобальный оператор Гровера $G_{1}$ и назначен местный оператор Гровера $G_{2}$.

На блоки действует глобальный оператор Гровера. По сути, оно дается следующим образом:

1. Выполнять $j_{1}$ стандартные итерации Гровера для всей базы данных.
2. Выполнять $j_{2}$ локальные итерации Гровера. Локальная итерация Гровера представляет собой прямую сумму итераций Гровера по каждому блоку.
3. Выполните одну стандартную итерацию Гровера.

Оптимальные значения $j_{1}$ и $j_{2}$ обсуждаются в статье Гровера и Радхакришнана. Можно также задаться вопросом, что произойдет, если применить последовательные частичные поиски на разных уровнях «разрешения». Эту идею подробно изучили Владимир Корепин и Сюй, которые назвали ее бинарным квантовым поиском. Они доказали, что на самом деле это не быстрее, чем выполнение одного частичного поиска.

Оптимальность

Алгоритм Гровера оптимален с точностью до субпостоянных коэффициентов. То есть любой алгоритм, который обращается к базе данных только с помощью оператора U _ω, должен применять U _ω как минимум $1-o(1)$ дробь столько же раз, сколько алгоритм Гровера. Расширение алгоритма Гровера до k совпадающих записей, π ( N / k ) ^1/2 /4 также является оптимальным. Этот результат важен для понимания ограничений квантовых вычислений.

Если бы проблему поиска Гровера можно было решить с помощью журнала ^с N применений U _ω , которые подразумевают, что NP содержится в BQP , путем преобразования проблем из NP в задачи поиска типа Гровера. Оптимальность алгоритма Гровера предполагает, что квантовые компьютеры не могут решать NP-полные задачи за полиномиальное время, и поэтому NP не содержится в BQP.

Было показано, что класс нелокальных квантовых компьютеров со скрытыми переменными может реализовать поиск $N$- база данных предметов не более $O({\sqrt[{3}]{N}})$ шаги. Это быстрее, чем $O({\sqrt {N}})$ шаги, выполняемые алгоритмом Гровера.

См. также

• Усиление амплитуды
• Алгоритм Брассара – Хойера – Тэппа (для решения проблемы столкновений )
• Алгоритм Шора (для факторизации)
• Поиск квантовых прогулок

Ссылки

• Гровер Л.К.: Быстрый квантово-механический алгоритм для поиска в базе данных , Труды, 28-й ежегодный симпозиум ACM по теории вычислений, (май 1996 г.), с. 212
• Гровер Л.К.: От уравнения Шрёдингера к алгоритму квантового поиска , Американский журнал физики, 69(7): 769–777, 2001. Педагогический обзор алгоритма и его истории.
• Гровер Л.К.: КВАНТОВЫЕ ВЫЧИСЛЕНИЯ: Как странная логика субатомного мира может позволить машинам производить вычисления в миллионы раз быстрее, чем они делают сегодня. The Sciences , июль/август 1999 г., стр. 24–30.
• Нильсен М.А. и Чуанг И.Л. Квантовые вычисления и квантовая информация . Издательство Кембриджского университета, 2000. Глава 6.
• Что такое квантовая телефонная книга? , Лов Гровер, Lucent Technologies

Внешние ссылки

• Дэви Вибирал. «Симулятор квантовых цепей» . Архивировано из оригинала 16 января 2017 г. Проверено 13 января 2017 г.
• Крейг Гидни (5 марта 2013 г.). «Алгоритм квантового поиска Гровера» . Архивировано из оригинала 17 ноября 2020 г. Проверено 8 марта 2013 г.
• Франсуа Шварцентрубер (18 мая 2013 г.). «Алгоритм Гровера» .
• Александр Прокопеня. «Квантовая схема, реализующая алгоритм поиска Гровера» . Вольфрам Альфа .
• «Квантовые вычисления, теория» , Энциклопедия математики , EMS Press , 2001 [1994]
• Роберто Маэстре (11 мая 2018 г.). «Алгоритм Гровера, реализованный в R и C» . Гитхаб .
• Бернхард Омер. «QCL — язык программирования для квантовых компьютеров» . Проверено 30 апреля 2022 г. Реализовано в /qcl-0.6.4/lib/grover.qcl.