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

Алгоритм квантового поиска

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

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

В отличие от других квантовых алгоритмов, которые могут обеспечить экспоненциальное ускорение по сравнению со своими классическими аналогами, алгоритм Гровера обеспечивает только квадратичное ускорение. Однако даже квадратичное ускорение является значительным, если оно велико, и алгоритм Гровера можно применять для ускорения широких классов алгоритмов. ^[3] Алгоритм Гровера мог подобрать 128-битный симметричный криптографический ключ примерно за ²⁶⁴ итерации или 256-битный ключ примерно за 2128 ^{итераций} . Однако это может быть не так, что алгоритм Гровера представляет значительно повышенный риск шифрования по сравнению с существующими классическими алгоритмами. ^[4] ${\displaystyle N}$

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

Алгоритм Гровера, наряду с такими вариантами, как усиление амплитуды , можно использовать для ускорения широкого спектра алгоритмов. ^{[5] [6] [7]} В частности, алгоритмы для NP-полных задач обычно содержат в качестве подпрограммы исчерпывающий поиск, который можно ускорить с помощью алгоритма Гровера. ^[6] Один из таких примеров — лучший на данный момент алгоритм для 3SAT . Общие проблемы удовлетворения ограничений также приводят к квадратичному ускорению с Гровером. ^[8] Эти алгоритмы не требуют, чтобы входные данные были заданы в форме оракула, поскольку алгоритм Гровера применяется с явной функцией, например, функцией проверки того, что набор битов удовлетворяет экземпляру 3SAT.

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

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

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

Ограничения

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

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

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

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

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

${\displaystyle {\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}}}$

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

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

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

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

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

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

${\displaystyle {\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}}}$

или кратко,

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

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

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

${\displaystyle {\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}}}$

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

Алгоритм

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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}}.}$

${\displaystyle 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}}.}$

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

${\displaystyle 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}}.}$

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

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

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

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

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

${\displaystyle \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 находятся как можно дальше друг от друга, что соответствует , или . Тогда система находится в состоянии ${\displaystyle 2rt\approx \pi /2}$ ${\displaystyle r=\pi /4t=\pi /4\arcsin(1/{\sqrt {N}})\approx \pi {\sqrt {N}}/4}$

${\displaystyle [|\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)}}.}$

Короткий расчет теперь показывает, что наблюдение дает правильный ответ ω с ошибкой . ${\displaystyle 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 неизвестно. ^[16] Простое решение работает оптимально до постоянного коэффициента: многократно запускайте алгоритм Гровера для все более малых значений k , например, принимая k = N , N /2, N /4, ... и т. д., принимая итерация t, пока не будет найдена соответствующая запись. ${\displaystyle k=N/2^{t}}$

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

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

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

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

Версия этого алгоритма используется для решения проблемы столкновений . ^{[18] [19]}

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

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

Примечания

1. Гровер, Лов К. (1 июля 1996 г.). «Быстрый квантовомеханический алгоритм поиска в базе данных». Материалы двадцать восьмого ежегодного симпозиума ACM по теории вычислений - STOC '96 . Филадельфия, Пенсильвания, США: Ассоциация вычислительной техники. стр. 212–219. arXiv : Quant-ph/9605043 . Бибкод : 1996quant.ph..5043G. дои : 10.1145/237814.237866. ISBN 978-0-89791-785-8. S2CID  207198067.
2. Беннетт CH; Бернштейн Э.; Брассар Г.; Вазирани У. (1997). «Сильные и слабые стороны квантовых вычислений». SIAM Journal по вычислительной технике . 26 (5): 1510–1523. arXiv : Quant-ph/9701001 . дои : 10.1137/s0097539796300933. S2CID  13403194.
3. Nielsen, Майкл А. (2010). Квантовые вычисления и квантовая информация. Исаак Л. Чуанг. Кембридж: Издательство Кембриджского университета. стр. 276–305. ISBN 978-1-107-00217-3. ОСЛК  665137861.
4. Дэниел Дж. Бернштейн (3 марта 2010 г.). «Гровер против МакЭлиса» (PDF) . {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
5. Гровер, Лов К. (1998). «Основы быстрых квантово-механических алгоритмов». В Виттере, Джеффри Скотт (ред.). Материалы тридцатого ежегодного симпозиума ACM по теории вычислений, Даллас, Техас, США, 23–26 мая 1998 г. Ассоциация вычислительной техники. стр. 53–62. arXiv : Quant-ph/9711043 . дои : 10.1145/276698.276712.
6. Амбайнис, А. (1 июня 2004 г.). «Алгоритмы квантового поиска». Новости ACM SIGACT . 35 (2): 22–35. arXiv : Quant-ph/0504012 . дои : 10.1145/992287.992296. ISSN  0163-5700. S2CID  11326499.
7. Джордан, Стивен. «Зоопарк квантовых алгоритмов». Quantalgorithmzoo.org . Проверено 21 апреля 2021 г.
8. Серф, Николас Дж.; Гровер, Лов К.; Уильямс, Колин П. (1 мая 2000 г.). «Вложенный квантовый поиск и NP-трудные проблемы». Применимая алгебра в технике, связи и информатике . 10 (4): 311–338. дои : 10.1007/s002000050134. ISSN  1432-0622. S2CID  311132.
9. Амбайнис, Андрис (1 января 2007 г.). «Алгоритм квантового блуждания для различения элементов». SIAM Journal по вычислительной технике . 37 (1): 210–239. arXiv : Quant-ph/0311001 . дои : 10.1137/S0097539705447311. ISSN  0097-5397. S2CID  6581885.
10. Брассар, Жиль; Хойер, Питер; Тапп, Ален (1998). «Квантовый криптоанализ хэш-функций и функций без клешней». В Луккези, Клаудио Л.; Моура, Арнальдо В. (ред.). LATIN '98: Теоретическая информатика, Третий латиноамериканский симпозиум, Кампинас, Бразилия, 20–24 апреля 1998 г., Материалы . Конспекты лекций по информатике. Том. 1380. Спрингер. стр. 163–169. arXiv : Quant-ph/9705002 . дои : 10.1007/BFb0054319.
11. Постквантовая криптография. Дэниел Дж. Бернштейн, Йоханнес Бухманн, Эрик, дипломированный математик Дамен. Берлин: Шпрингер. 2009. ISBN 978-3-540-88702-7. ОСЛК  318545517.{{cite book}}: CS1 maint: others (link)
12. Бернштейн, Дэниел Дж. (21 апреля 2021 г.). «Анализ затрат на коллизии хешей: сделают ли квантовые компьютеры SHARCS устаревшими?» (PDF) . Материалы конференции «Специальное оборудование для атак на криптографические системы» (SHARCS '09) . 09 : 105–117.
13. Виамонтес Г.Ф.; Марков И.Л.; Хейс Дж.П. (2005), «Практичен ли квантовый поиск?» (PDF) , Computing in Science and Engineering , 7 (3): 62–70, arXiv : quant-ph/0405001 , Bibcode : 2005CSE.....7c..62V, doi : 10.1109/mcse.2005.53, S2CID  8929938
14. Синицын Н.А.; Ян Б. (2023). «Топологически защищенный оракул Гровера для проблемы раздела». Физический обзор А. 108 (2): 022412. arXiv : 2304.10488 . doi :10.1103/PhysRevA.108.022412. S2CID  258236417.
15. Бэббуш, Райан; МакКлин, Джаррод Р.; Ньюман, Майкл; Гидни, Крейг; Бойшо, Серхио; Невен, Хартмут (29 марта 2021 г.). «Фокус не только на квадратичном ускорении, но и на квантовом преимуществе с коррекцией ошибок». PRX Квантум . 2 (1): 010103. arXiv : 2011.04149 . дои : 10.1103/PRXQuantum.2.010103 .
16. Ааронсон, Скотт (19 апреля 2021 г.). «Введение в конспекты лекций по квантовой информатике» (PDF) .
17. Нильсен-Чуанг
18. Мишель Бойер; Жиль Брассар; Питер Хойер; Ален Тапп (1998), «Жесткие границы квантового поиска», Fortschr. Физ. , 46 (4–5): 493–506, arXiv : quant-ph/9605034 , Bibcode : 1998ForPh..46..493B, doi : 10.1002/3527603093.ch10, ISBN 9783527603091
19. Андрис Амбайнис (2004), «Алгоритмы квантового поиска», SIGACT News , 35 (2): 22–35, arXiv : quant-ph/0504012 , Bibcode : 2005quant.ph..4012A, doi : 10.1145/992287.992296, S2CID  11326499
20. Л.К. Гровер; Дж. Радхакришнан (7 февраля 2005 г.). «Частичный квантовый поиск в базе данных проще?». arXiv : Quant-ph/0407122v4 .
21. Залка, Кристоф (1 октября 1999 г.). «Алгоритм квантового поиска Гровера оптимален». Физический обзор А. 60 (4): 2746–2751. arXiv : Quant-ph/9711070 . Бибкод : 1999PhRvA..60.2746Z. doi : 10.1103/PhysRevA.60.2746. S2CID  1542077.
22. Ааронсон, Скотт. «Квантовые вычисления и скрытые переменные» (PDF) .

Рекомендации

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

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

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