Предполагается, что функция задана в виде чёрного ящика, или оракула, то есть в ходе решения можно задавать оракулу только вопрос типа: «чему равна на данном ?», и использовать ответ в дальнейших вычислениях. То есть, задача решения уравнения (1) является общей формой задачи перебора: здесь требуется отыскать «пароль к устройству », что классически требует полного перебора всех вариантов.
Алгоритм Гровера находит какой-нибудь корень уравнения, используя обращений к функции , с использованием кубитов.[2]
Смысл алгоритма Гровера состоит в «усилении амплитуды» целевого состояния за счёт убывания амплитуды всех других состояний. Геометрически алгоритм Гровера заключается во вращении текущего вектора состояния квантового компьютера по направлению точно к целевому состоянию (движение по наикратчайшему пути обеспечивает оптимальность алгоритма Гровера). Каждый шаг дает вращение на угол , где угол между и составляет .
Дальнейшее продолжение итераций оператора G даст продолжение обхода окружности в вещественной плоскости, порождённой данными векторами.
Гроверовское «усиление амплитуды» является, по-видимому, фундаментальным физическим феноменом в квантовой теории многих тел. Например, его учёт необходим для оценки вероятностей событий, которые кажутся «редкими». Процесс, реализующий схему алгоритма Гровера, приводит к взрывному росту первоначально пренебрежимо малой амплитуды, что способно быстро довести её до реально наблюдаемых величин.
Алгоритм Гровера также может быть использован для нахождения медианы и среднего арифметического числового ряда. Кроме того, он может применяться для решения NP-полных задач путём исчерпывающего поиска среди множества возможных решений. Это может повлечь значительный прирост скорости по сравнению с классическими алгоритмами, хотя и не предоставляя «полиномиального решения» в общем виде.
Пусть есть унитарный оператор, зеркально отражающий гильбертово пространство относительно гиперплоскости, перпендикулярной вектору , — состояние, соответствующее корню уравнения (1), — равномерная суперпозиция всех состояний.
Алгоритм Гровера состоит в применении оператора к состоянию число раз, равное целой части . Результат будет почти совпадать с состоянием .
Измерив полученное состояние, получаем ответ с вероятностью, близкой к единице.
Предположим, уравнение (1) имеет корней.
Классический алгоритм решения такой задачи (линейный поиск), очевидно, требует обращений к для того, чтобы решить задачу с вероятностью .
Алгоритм Гровера позволяет решить задачу поиска за время , то есть порядка квадратного корня из классического, что является огромным ускорением.
Доказано, что Алгоритм Гровера является оптимальным в следующих отношениях:
Большего квантового ускорения, чем квадратичное, нельзя получить[4].
Алгоритм Гровера есть пример массовой задачи, зависящей от оракула. Для более частных задач удаётся получить большее квантовое ускорение. Например, алгоритм факторизации Шора даёт экспоненциальный выигрыш по сравнению с соответствующими классическими алгоритмами.
То, что f задана в виде чёрного ящика, никак не влияет в общем случае на сложность как квантовых, так и классических алгоритмов. Знание «устройства» функции f (например, знание задающей её схемы из функциональных элементов) в общем случае никак не может помочь в решении уравнения (1). Поиск в базе данных соотносится с обращением функции, которая принимает определённое значение, если аргумент x соответствует искомой записи в базе данных.
Алгоритм поиска экстремума целочисленной функции (P. Hoyer и др.). Ищется наибольшее значение функции . Квантовый алгоритм находит максимум за обращений к f.
Алгоритм структурного поиска (Farhi, Gutman). Ищется решение уравнения (1) при дополнительном условии , где разбиение строки на две строки одинаковой длины. Алгоритм имеет сложность порядка квадратного корня из классического времени.
Алгоритм поиска совпадающих строк в базе данных (Амбайнис). Ищется пара разных аргументов , на которых функция принимает одно и то же значение. Алгоритм требует обращений к f.
Пусть гамильтониан квантовой системы имеет вид , где и представляют собой операторы и соответственно. Тогда непрерывная унитарная эволюция с гамильтонианом , стартуя с , естественно приводит к . Сложность такого непрерывного аналога алгоритма Гровера точно та же, что и для дискретного случая.
Адиабатический вариант алгоритма Гровера. Медленная эволюция основного состояния типа под действием гамильтониана, зависящего от f, согласно адиабатической теореме, за время порядка ведет к состоянию .