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

1996 год. Белл Лабс. Лов Гровер доказывает: квантовый компьютер найдёт имя в телефонной книге на миллиард записей за 31 623 шага. Классический алгоритм - 500 миллионов. Это не магия и не экспоненциальный прорыв. Это тихая математическая теорема о вращении векторов в гильбертовом пространстве - и она навсегда изменила статус симметричной криптографии.

• **Постквантовая криптография:** Гровер сокращает эффективную длину AES-ключа вдвое. AES-128 на квантовом компьютере эквивалентен AES-64 по стойкости. NIST включил это в требования к Post-Quantum стандартам 2024 года - отсюда рекомендация AES-256 для долгосрочной безопасности.
• **Ускорение NP-задач:** задачи, требующие перебора (SAT, TSP, оптимизация), получают квадратичное ускорение через oracle Гровера. Не экспоненциальное, но реальное - особенно для задач с пространством поиска $2^{50}$ и выше.
• **Поиск коллизий хешей:** birthday attack с использованием Гровера требует $O(N^{1/3})$ квантовых запросов вместо $O(N^{1/2})$ классических. SHA-256 остаётся стойким, SHA-1 и MD5 - нет.

Задача поиска и квантовый подход

1996 год. Bell Labs. Лов Гровер берёт задачу, которую каждый программист считает нерешаемой быстрее линейного, и доказывает: квантовый компьютер найдёт нужный элемент в неупорядоченной базе данных за $O(\sqrt{N})$ шагов вместо $O(N)$. Телефонная книга на 1 миллиард записей - 31 623 запроса вместо 500 миллионов. Это не экспоненциальное чудо Шора. Это тихое, доказанное, квадратичное ускорение - и оно применимо к любой задаче, которую можно сформулировать как поиск.

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

**Формальная постановка:** дана функция $f: \{0, 1, \ldots, N-1\} \to \{0, 1\}$, где ровно один элемент $x^*$ удовлетворяет $f(x^*) = 1$. Найти $x^*$. Классический оптимум - $\Theta(N)$ вычислений $f$. Гровер даёт $\Theta(\sqrt{N})$ вычислений $f$ - и это тоже оптимально для квантовых алгоритмов (нижняя граница Беннета-Бернштейна-Бруссара).

Ключевое слово в постановке - "функция $f$". Алгоритм не читает базу данных напрямую. Он вызывает **oracle** - чёрный ящик, который умеет проверить: является ли данный $x$ ответом? Oracle запускается $O(\sqrt{N})$ раз. Если один вызов oracle стоит одну секунду, классика тратит 500 миллионов секунд, квантовый алгоритм - 31 623. Это и есть квадратичное ускорение в чистом виде.

Почему именно $\sqrt{N}$? Геометрическая интуиция появится в следующей концепции. Пока важно одно: алгоритм Гровера - **общий**. Oracle может проверять удовлетворение SAT-формулы, коллизию хеша, соответствие пароля - что угодно. Каждая задача, сводящаяся к поиску в пространстве из $N$ элементов, автоматически получает квадратичное ускорение.

Oracle и фазовый удар

Oracle в алгоритме Гровера - не функция, возвращающая 0 или 1. Это **унитарный оператор**, действующий на суперпозицию состояний. Классический oracle ставит метку: нашёл/не нашёл. Квантовый oracle делает нечто тоньше: он **инвертирует фазу** целевого состояния, не разрушая суперпозицию.

Формально: начинают с равномерной суперпозиции $|s\rangle = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle$. Все $N$ состояний имеют одинаковую амплитуду $\frac{1}{\sqrt{N}}$. Oracle $U_f$ действует так: $U_f|x\rangle = (-1)^{f(x)}|x\rangle$. Для обычных $x$ (где $f(x) = 0$) - ничего не меняется. Для целевого $x^*$ (где $f(x^*) = 1$) - знак амплитуды инвертируется. Амплитуда была $+\frac{1}{\sqrt{N}}$, стала $-\frac{1}{\sqrt{N}}$.

После применения oracle вероятности измерить каждый элемент остаются **одинаковыми** - по 1/N. Измерение сейчас даст случайный результат. Oracle только пометил целевой элемент невидимым для измерений знаком минус. Без второго шага - diffusion operator - алгоритм бесполезен.

Как реализовать oracle физически? Это проблема проектировщика квантовой схемы, не теоретика. Oracle - вычислительная схема, реализующая $f(x)$. Для поиска пароля - схема проверки хеша. Для SAT - схема проверки условий. Oracle не знает ответа заранее - он проверяет предположение. Этот принцип называется **phase kickback**: ancilla-кубит через CNOT-подобные операции переносит фазу обратно на регистр данных.

**Phase kickback:** ancilla-кубит готовится в состоянии $\frac{|0\rangle - |1\rangle}{\sqrt{2}}$. При применении контролируемого oracle: если $f(x) = 1$, фаза $-1$ выбрасывается в управляющий регистр. Ancilla возвращается в исходное состояние. Это позволяет реализовать квантовый oracle без необратимого измерения.

Amplitude amplification и геометрия вращения

Oracle пометил целевое состояние минусом. Теперь нужно это различие превратить в измеримое. Инструмент - **diffusion operator** (оператор инверсии относительно среднего), придуманный Гровером. Вместе oracle + diffusion = один шаг алгоритма. Повторяя $\approx \frac{\pi}{4}\sqrt{N}$ раз, система концентрирует амплитуду на целевом состоянии с вероятностью, близкой к 1.

Геометрическая картина делает весь процесс прозрачным. Представим двумерное пространство: ось $|s\rangle$ (равномерная суперпозиция всех состояний) и ось $|x^*\rangle$ (целевое состояние). Текущее квантовое состояние - вектор в этом пространстве. Начальный угол между $|s\rangle$ и $|x^*\rangle$: $\cos\theta = \langle x^* | s \rangle = \frac{1}{\sqrt{N}}$, то есть $\theta \approx \frac{1}{\sqrt{N}}$ для больших $N$.

Каждая итерация Гровера - это **поворот вектора состояния на угол $2\theta$** в сторону $|x^*\rangle$. Oracle отражает состояние относительно гиперплоскости, ортогональной $|x^*\rangle$. Diffusion отражает относительно $|s\rangle$. Два последовательных отражения = одно вращение. После $k \approx \frac{\pi}{4\theta} \approx \frac{\pi}{4}\sqrt{N}$ итераций вектор почти совпадает с $|x^*\rangle$, и измерение даёт правильный ответ с вероятностью $\geq 1 - \frac{1}{N}$.

**Diffusion operator:** $D = 2|s\rangle\langle s| - I$. Он инвертирует амплитуды относительно их среднего значения $\bar{a}$: каждая амплитуда $a_x$ становится $2\bar{a} - a_x$. Если целевая амплитуда после oracle стала отрицательной (ниже среднего), инверсия относительно среднего поднимает её выше остальных. Это и есть усиление амплитуды.

Почему нельзя итерировать бесконечно? Потому что алгоритм переусиливает: после оптимального числа шагов вектор начинает поворачиваться в обратную сторону, удаляясь от $|x^*\rangle$. Это фундаментальное ограничение, а не баг реализации. На практике число итераций вычисляется заранее по формуле, и алгоритм останавливается точно. Это отличает Гровера от многих эвристических поисков - здесь точное математическое расписание.

**Когда применяется в реальности.** Квантовое преимущество Гровера активируется при поиске в структурированных криптографических задачах: перебор AES-ключей (128 бит) сводится к $2^{64}$ итерациям вместо $2^{128}$ - отсюда рекомендация переходить на AES-256 в постквантовую эру. Поиск коллизий хешей ускоряется схожим образом. NIST Post-Quantum Cryptography стандарты 2024 года учитывают именно квадратичное ускорение Гровера как угрозу симметричной криптографии.

Ключевые идеи

• **Oracle - фазовый удар:** квантовый oracle инвертирует знак амплитуды целевого состояния ($(-1)^{f(x)}$), не меняя вероятностей измерения - видимый эффект появляется только после diffusion operator.
• **Геометрия вращения:** алгоритм - это повторяющийся поворот вектора состояния на угол $2\theta \approx \frac{2}{\sqrt{N}}$ в сторону целевого состояния. После $\frac{\pi}{4}\sqrt{N}$ итераций - измерение с вероятностью близкой к 1.
• **Оптимальность и ограничения:** $O(\sqrt{N})$ - доказанный квантовый оптимум для неструктурированного поиска (BBBV theorem). Переитерирование разрушает результат. Ускорение квадратичное, не экспоненциальное - это честная цена за общность алгоритма.

Связанные темы

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

• Линейный поиск — Классический аналог с O(N) - прямой контраст
• Бинарный поиск — Тоже сублинейный, но требует отсортированности - иная модель
• Алгоритм Шора — Второй квантовый алгоритм с практическим значением, использует QFT
• O-нотация и сложность — Нотация O(N) и O(sqrt(N)) - основа для понимания ускорения

Вопросы для размышления

• Алгоритм Гровера оптимален для квантового поиска - никакой квантовый алгоритм не сделает лучше. Что это говорит о природе квантового вычисления: это радикально новая парадигма или 'просто быстрее' там, где классика ограничена?
• Oracle предполагает, что проверка ответа дешевле, чем его нахождение. В каких реальных задачах это условие выполняется, а в каких - нет?
• Если квантовые компьютеры с миллионами кубитов станут доступны, как изменится текущий ландшафт шифрования - и что нужно сделать уже сейчас?

Связанные уроки

• qc-05 — Deutsch-Jozsa - первый шаг к oracle-based ускорению
• qc-07 — Шор строится поверх QFT, Гровер - независимый подход
• alg-09-linear-search — O(N) против O(sqrt(N)) - наглядный контраст
• alg-10-binary-search — Тоже сублинейный поиск, но требует отсортированность
• alg-01-big-o — Без понимания O-нотации квадратичное ускорение не читается