Алгоритм Гровера: как квантовый поиск ускоряет перебор

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

Постановка задачи и классическая граница

Пусть есть функция $f:\{0,1\}^n \to \{0,1\}$, заданная как «чёрный ящик»: про неё известно лишь, что ровно для одного входа $x_0$ выполнено $f(x_0)=1$, а для остальных $f(x)=0$. Размер пространства поиска $N = 2^n$. Цель - найти $x_0$. У нас нет никакой структуры (сортировки, индекса, эвристики) - только право спрашивать оракул «является ли $x$ ответом?».

Классически в среднем придётся сделать $N/2$ запросов, а в худшем - $N-1$. Это нижняя граница: без структуры данных перебор не обойти. Алгоритм Гровера снижает число обращений до примерно $\frac{\pi}{4}\sqrt{N}$ - квадратичное ускорение. Для базы из миллиона элементов это около 785 итераций вместо полумиллиона ожидаемых классических проверок.

После того как мы поймём механику на одном отмеченном элементе, имеет смысл сразу прогнать конкретные числа: сколько итераций нужно для вашего $N$, какова вероятность успеха и какое ускорение это даёт. Для этого ниже есть интерактивный калькулятор.

Геометрия амплитудного усиления

Состояние $n$ кубитов живёт в пространстве размерности $N=2^n$. Стартуем из равномерной суперпозиции всех базисных состояний, которую даёт каскад адамаровых вентилей $H^{\otimes n}$:

$|s\rangle = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x\rangle.$

Здесь амплитуда каждого состояния равна $\frac{1}{\sqrt N}$, и вероятность сразу измерить правильный ответ равна $1/N$ - ничтожно мала. Идея алгоритма Гровера: не угадывать, а итеративно перекачивать амплитуду в отмеченное состояние $|x_0\rangle$.

Удобно работать в двумерной плоскости, натянутой на два ортогональных вектора: само решение $|x_0\rangle$ и равномерную суперпозицию всех «неправильных» состояний $|\omega\rangle = \frac{1}{\sqrt{N-1}}\sum_{x\neq x_0}|x\rangle$. Начальное состояние $|s\rangle$ лежит в этой плоскости и образует с осью «ошибок» $|\omega\rangle$ малый угол $\theta$, для которого $\sin\theta = \frac{1}{\sqrt N}$. Вся динамика - это вращение вектора состояния в данной плоскости к оси $|x_0\rangle$.

Оракул: фазовая пометка решения

Первый кирпич итерации - фазовый оракул $U_f$. Он не «выдаёт» ответ, а помечает его знаком: переворачивает фазу амплитуды у искомого состояния и не трогает остальные:

$U_f|x\rangle = (-1)^{f(x)}|x\rangle, \qquad U_f = I - 2|x_0\rangle\langle x_0|.$

Геометрически $U_f$ - это отражение вектора состояния относительно оси $|\omega\rangle$. Амплитуда правильного ответа становится отрицательной, амплитуды ошибок остаются прежними. Сами по себе вероятности (квадраты модулей) при этом не меняются - пометка «невидима» для измерения. Полезной её делает второй шаг.

Диффузор: инверсия относительно среднего

Второй кирпич - оператор диффузии Гровера, он же инверсия относительно среднего:

$U_s = 2|s\rangle\langle s| - I.$

Это отражение относительно начального вектора $|s\rangle$. Если расписать его действие на амплитуды, получится наглядная операция: каждую амплитуду $a_k$ заменяем на $2\bar a - a_k$, где $\bar a$ - среднее по всем амплитудам. Отрицательная (помеченная оракулом) амплитуда решения оказывается далеко ниже среднего, поэтому после инверсии она подскакивает вверх сильнее всех, а близкие к среднему амплитуды ошибок слегка проседают.

Композиция двух отражений - это поворот. Произведение $G = U_s U_f$, оператор Гровера, поворачивает вектор состояния в нашей плоскости на угол $2\theta$ в сторону $|x_0\rangle$ за одну итерацию. Каждый прогон «грейферного цикла» оракул–диффузор приближает состояние к ответу на фиксированный угол.

Сколько итераций нужно

После $k$ итераций вектор состояния отклонён от оси ошибок на угол $(2k+1)\theta$, и вероятность измерить правильный ответ равна

$P(k) = \sin^2\big((2k+1)\theta\big), \qquad \sin\theta=\tfrac{1}{\sqrt N}.$

Чтобы $P(k)$ была близка к единице, нужно довернуть вектор до $\approx 90^\circ$, то есть $(2k+1)\theta \approx \frac{\pi}{2}$. Отсюда оптимальное число итераций

$k_{\text{opt}} = \left\lfloor \frac{\pi}{4}\sqrt N \right\rceil.$

При больших $N$ угол $\theta\approx 1/\sqrt N$, и число итераций растёт как корень из размера базы - отсюда сложность $O(\sqrt N)$ по обращениям к оракулу. Это и есть квантовое ускорение Гровера.

Обобщения и пределы

Если отмеченных элементов не один, а $M$, угол стартового состояния задаётся как $\sin\theta=\sqrt{M/N}$, и оптимум сдвигается к $k\approx \frac{\pi}{4}\sqrt{N/M}$. Когда $M$ заранее неизвестно, применяют квантовый счёт (quantum counting) на основе оценки фазы либо рандомизированную схему со случайным числом итераций. Амплитудное усиление - обобщение метода Гровера на произвольное стартовое распределение и произвольную проверку, оно лежит в основе многих квантовых подпрограмм.

Важно понимать границу преимущества. Квадратичное ускорение - это потолок: теорема об оптимальности (BBBV) доказывает, что никакой квантовый алгоритм не решает неструктурированный поиск быстрее, чем за $\Omega(\sqrt N)$ запросов. Поэтому Гровер не «ломает» NP-полные задачи и не даёт экспоненциального выигрыша, как Шор для факторизации; он лишь вдвое сокращает эффективную длину ключа при переборе, из-за чего симметричные шифры рекомендуют брать с удвоенным запасом по биту - это одна из отправных точек квантово-устойчивой криптографии.

Практическая реализация

В терминах схемы итерация Гровера собирается из стандартных вентилей. Оракул реализуют через многокубитный управляемый-NOT с фазовым трюком (вспомогательный кубит в состоянии $|-\rangle$ превращает bit-flip в phase-flip). Диффузор раскладывается как $H^{\otimes n}$, затем условный сдвиг фазы у состояния $|0\rangle^{\otimes n}$, затем снова $H^{\otimes n}$. На NISQ-устройствах глубина схемы и накопление шума ограничивают достижимое $N$, поэтому реальные демонстрации пока работают с малым числом кубитов, но принцип масштабируется без изменений.

Стоит отметить и тонкость с числом итераций: $k_{\text{opt}}$ обычно не целое, поэтому его округляют, и итоговая вероятность успеха чуть меньше единицы. Для одного решения промах не превышает $1/N$, то есть при больших базах потеря пренебрежимо мала; при необходимости детерминированного результата применяют точные варианты Гровера с подстройкой фаз отражений вместо $-1$. Ещё одна практическая деталь - оракул должен быть обратимым унитарным оператором, поэтому любую классическую проверку $f(x)$ предварительно превращают в обратимую схему, добавляя вспомогательные кубиты и «раскапывая» их в конце (uncompute), чтобы не оставить запутанности с рабочим регистром.

Частые ошибки

• Считают, что Гровер даёт экспоненциальное ускорение. Нет - только квадратичное, $O(\sqrt N)$ против $O(N)$; экспоненту даёт Шор, и для другой задачи.
• Думают, что оракул «знает» ответ и просто его сообщает. Оракул лишь переворачивает фазу решения; найти $x_0$ позволяет связка с диффузором и измерением.
• Запускают слишком много итераций «для надёжности». После $k_{\text{opt}}$ вероятность успеха падает - динамика синусоидальная, а не накопительная.
• Путают фазовую пометку с изменением вероятностей. После одного оракула вероятности не меняются; работает именно последующая инверсия относительно среднего.
• Игнорируют случай нескольких решений: при $M>1$ оптимум сдвигается к $\frac{\pi}{4}\sqrt{N/M}$, и формула для одного элемента переоценивает число шагов.

FAQ

Почему ускорение именно квадратичное, а не больше? Каждая итерация поворачивает состояние на фиксированный угол $\approx 2/\sqrt N$, и до цели нужно $\approx \frac{\pi}{4}\sqrt N$ поворотов. Теорема BBBV доказывает, что быстрее неструктурированный поиск невозможен ни на каком квантовом устройстве.

Можно ли с помощью Гровера взломать AES или RSA? RSA ломает Шор, а не Гровер. Для симметричных шифров вроде AES Гровер сокращает перебор ключа с $2^n$ до $2^{n/2}$ - это решается удвоением длины ключа (AES-256 остаётся стойким).

Что произойдёт, если измерить состояние слишком рано или слишком поздно? Слишком рано - вектор ещё близок к равномерному, вероятность успеха мала. Слишком поздно (после оптимума) - вектор проскочил ось решения, и вероятность снова снижается по закону $\sin^2((2k+1)\theta)$.

Коротко

Алгоритм Гровера квантовый решает задачу неструктурированного поиска среди $N$ вариантов за $O(\sqrt N)$ обращений к оракулу вместо классических $O(N)$. Из равномерной суперпозиции итерация «оракул + диффузор» поворачивает вектор состояния к решению на угол $2\theta$; после $k_{\text{opt}}\approx\frac{\pi}{4}\sqrt N$ шагов амплитуда отмеченного элемента максимальна, и измерение почти наверняка даёт ответ. Ускорение квадратичное и доказуемо оптимальное: больше итераций или ожидание экспоненциального выигрыша - типичные заблуждения.