Введение
В квантовых вычислениях алгоритм Гровера, также известный как алгоритм квантового поиска, является квантовым алгоритмом для неструктурированного поиска, который с высокой вероятностью находит единственный вход для функции-черного ящика, выдающей заданное значение, используя всего лишь оценок функции, где – размер области определения функции. Он был разработан Ловом Гровером в 1996 году. Аналогичная задача в классических вычислениях не может быть решена менее чем за оценок (поскольку, в среднем, необходимо проверить половину области определения, чтобы получить 50%-ную вероятность найти правильный вход). Чарльз Беннетт, Итан Бернштейн, Жиль Брассард и Умеш Вазирани доказали, что любое квантовое решение этой задачи требует оценок функции, следовательно, алгоритм Гровера асимптотически оптимален. Поскольку классические алгоритмы для NP-полных задач требуют экспоненциального числа шагов, а алгоритм Гровера обеспечивает максимум квадратичное ускорение по сравнению с классическим решением для неструктурированного поиска, это указывает на то, что сам по себе алгоритм Гровера не позволит найти решения за полиномиальное время для NP-полных задач (так как квадратный корень из экспоненциальной функции является экспоненциальной, а не полиномиальной функцией). В отличие от других квантовых алгоритмов, которые могут обеспечивать экспоненциальное ускорение по сравнению с классическими аналогами, алгоритм Гровера предоставляет лишь квадратичное ускорение. Однако даже квадратичное ускорение существенно, когда велико, и алгоритм Гровера может быть применен для ускорения широкого класса алгоритмов.
In quantum computing, Grover's algorithm, also known as the quantum search algorithm, is a quantum algorithm for unstructured search that finds with high probability the unique input to a black box function that produces a particular output value, using just evaluations of the function, where is the size of the function's domain. It was devised by Lov Grover in 1996. The analogous problem in classical computation cannot be solved in fewer than evaluations (because, on average, one has to check half of the domain to get a 50% chance of finding the right input). Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani proved that any quantum solution to the problem needs to evaluate the function times, so Grover's algorithm is asymptotically optimal. Since classical algorithms for NP complete problems require exponentially many steps, and Grover's algorithm provides at most a quadratic speedup over the classical solution for unstructured search, this suggests that Grover's algorithm by itself will not provide polynomial time solutions for NP complete problems (as the square root of an exponential function is an exponential, not polynomial, function). Unlike other quantum algorithms, which may provide exponential speedup over their classical counterparts, Grover's algorithm provides only a quadratic speedup. However, even quadratic speedup is considerable when is large, and Grover's algorithm can be applied to speed up broad classes of algorithms.
Применение и ограничения
Алгоритм Гровера, вместе с вариантами, такими как амплитудное усиление, может быть использован для ускорения широкого спектра алгоритмов. В частности, алгоритмы для NP-полных задач, содержащие полный перебор в качестве подпрограммы, могут быть ускорены алгоритмом Гровера. Эти алгоритмы не требуют, чтобы входные данные были представлены в виде оракула, поскольку алгоритм Гровера применяется с использованием явной функции, например, функции, проверяющей, удовлетворяет ли набор битов заданному экземпляру 3SAT. Алгоритм Гровера также обеспечивает доказуемое ускорение для задач типа "черный ящик" в квантовой сложности запросов, включая проверку уникальности элементов и задачу поиска коллизий (решаемую алгоритмом Brassard–Høyer–Tapp). В таких задачах функция оракула f рассматривается как база данных, и цель состоит в том, чтобы минимизировать количество квантовых запросов к этой функции.
Криптография
Алгоритм Гровера по сути решает задачу инверсии функции. Если говорить упрощенно, если у нас есть функция, которую можно вычислить на квантовом компьютере, алгоритм Гровера позволяет нам найти входные данные, при которых функция возвращает заданное значение. Следовательно, алгоритм Гровера обеспечивает значительное асимптотическое ускорение для многих видов атак полным перебором на симметричную криптографию, включая атаки нахождения коллизий и атаки прообраза. Однако это не обязательно самый эффективный алгоритм, поскольку, например, параллельный ρ-алгоритм способен находить коллизии в SHA2 эффективнее, чем алгоритм Гровера.
Ограничения
В оригинальной статье Гровера алгоритм описывался как алгоритм поиска в базе данных, и это описание до сих пор широко распространено. В этой аналогии база данных представляет собой таблицу всех результатов работы функции, индексированную соответствующим входным значением. Однако эта база данных не представляется явно. Вместо этого вызывается оракул для вычисления значения по его индексу. Полный перебор базы данных и преобразование её в такое представление может занять значительно больше времени, чем поиск Гровера. Чтобы учесть подобные эффекты, алгоритм Гровера можно рассматривать как решение уравнения или удовлетворение некоторого условия. В таких случаях оракул служит для проверки этого условия и не связан непосредственно с алгоритмом поиска. Такое разделение обычно препятствует алгоритмическим оптимизациям, в то время как традиционные алгоритмы поиска часто используют их для избежания полного перебора. К счастью, быстрая реализация оракула Гровера возможна для многих задач оптимизации и поиска решений, удовлетворяющих заданным ограничениям. Главным препятствием для получения выигрыша в скорости от алгоритма Гровера является то, что достигнутое квадратичное ускорение недостаточно велико, чтобы компенсировать значительные накладные расходы современных квантовых компьютеров. Однако более поздние поколения отказоустойчивых квантовых компьютеров с улучшенными характеристиками могут реализовать это ускорение для практических задач обработки данных.
Частичный квантовый поиск
Модификация алгоритма Гровера, называемая квантовым частичным поиском, была описана Гровером и Радхакришнаном в 2004 году. При частичном поиске не интересует точный адрес целевого элемента, а только первые несколько цифр адреса. Эквивалентно, можно представить, что пространство поиска разбивается на блоки, и затем задается вопрос: «в каком блоке находится целевой элемент?». Во многих приложениях такой поиск дает достаточно информации, если целевой адрес содержит искомую информацию. Например, используя пример, приведенный Л. К. Гровером, если у нас есть список студентов, упорядоченный по успеваемости, нас может интересовать только то, находится ли студент в нижнем 25%, диапазоне 25–50%, 50–75% или 75–100% процентилях. Для описания частичного поиска рассмотрим базу данных, разделенную на блоки, каждый из которых имеет размер . Задача частичного поиска упрощается. Рассмотрим подход, который мы бы использовали классически: мы выбираем один блок случайным образом, а затем выполняем обычный поиск по остальным блокам (в терминах теории множеств – по дополнению). Если мы не находим целевой элемент, то знаем, что он находится в блоке, который мы не искали. Среднее количество итераций уменьшается с до . Алгоритм Гровера требует итераций. Частичный поиск будет быстрее на числовой фактор, зависящий от количества блоков. Частичный поиск использует глобальных итераций и локальных итераций. Глобальный оператор Гровера обозначается , а локальный оператор Гровера обозначается .
Grover's algorithm requires iterations. Partial search will be faster by a numerical factor that depends on the number of blocks Partial search uses global iterations and local iterations. The global Grover operator is designated and the local Grover operator is designated
The global Grover operator acts on the blocks. Essentially, it is given as follows:
Perform standard Grover iterations on the entire database. Perform local Grover iterations. A local Grover iteration is a direct sum of Grover iterations over each block. Perform one standard Grover iteration. The optimal values of and are discussed in the paper by Grover and Radhakrishnan. One might also wonder what happens if one applies successive partial searches at different levels of "resolution". This idea was studied in detail by Vladimir Korepin and Xu, who called it binary quantum search. They proved that it is not in fact any faster than performing a single partial search.
Глобальный оператор Гровера действует на блоки. По сути, он определяется следующим образом:
Выполните стандартных итераций Гровера по всей базе данных. Выполните локальных итераций Гровера. Локальная итерация Гровера – это прямая сумма итераций Гровера по каждому блоку. Выполните одну стандартную итерацию Гровера. Оптимальные значения и обсуждаются в статье Гровера и Радхакришнана. Также можно задаться вопросом, что произойдет, если применить последовательные частичные поиски на разных уровнях «разрешения». Эта идея была подробно изучена Владимиром Корепиным и Сюй, которые назвали ее бинарным квантовым поиском. Они доказали, что она на самом деле не быстрее, чем выполнение одного частичного поиска.
Grover's algorithm requires iterations. Partial search will be faster by a numerical factor that depends on the number of blocks Partial search uses global iterations and local iterations. The global Grover operator is designated and the local Grover operator is designated
The global Grover operator acts on the blocks. Essentially, it is given as follows:
Perform standard Grover iterations on the entire database. Perform local Grover iterations. A local Grover iteration is a direct sum of Grover iterations over each block. Perform one standard Grover iteration. The optimal values of and are discussed in the paper by Grover and Radhakrishnan. One might also wonder what happens if one applies successive partial searches at different levels of "resolution". This idea was studied in detail by Vladimir Korepin and Xu, who called it binary quantum search. They proved that it is not in fact any faster than performing a single partial search.
Оптимальность
Алгоритм Гровера оптимален с точностью до субконстантных факторов. То есть, любой алгоритм, обращающийся к базе данных только посредством оператора Uω, должен применять Uω не менее чем в долю раз, чем алгоритм Гровера. Расширение алгоритма Гровера для k совпадающих элементов, (N/k)¹/² / 4, также является оптимальным.