Курс «Квантовые вычисления». Глава 8. Алгоритм Гровера

Курс «Квантовые вычисления»

Цели главы. Разобрать алгоритм Гровера: геометрическую картину двух отражений, выбор числа итераций и нижнюю оценку, доказывающую оптимальность в модели запросов. Затем отделить асимптотическое квадратичное ускорение перебора от полной физической стоимости криптоаналитической атаки.

8.1. Задача

Дана функция f: {0,1}ⁿ → {0,1} в виде оракула (глава 5), причём она равна 1 на M входах из N = 2ⁿ. Требуется найти хотя бы один такой вход. Модель не предполагает структуры, которую можно использовать помимо проверки кандидата. Она описывает абстрактный перебор; для базы данных или криптографической задачи в полную стоимость необходимо включать реализацию доступа к данным или обратимого проверяющего оракула.

Рандомизированному классическому алгоритму требуется Θ(N/M) запросов для постоянной вероятности успеха. Алгоритм Гровера использует O(√(N/M)) запросов. Это универсальное квадратичное, но не экспоненциальное ускорение неструктурированного поиска; время и число физических операций могут быть значительно больше числа запросов.

8.2. Два отражения

Начальное состояние — равномерная суперпозиция |ψ⟩ = H^⊗n|0…0⟩ = N^−1/2∑_x|x⟩. Одна итерация Гровера G состоит из двух операторов:

1. Оракул-фаза O: |x⟩ → (−1)^f(x)|x⟩ — переворот знака амплитуд помеченных состояний. Реализуется одним запросом к U_f через фазовый откат (глава 5).
2. Диффузор D = 2|ψ⟩⟨ψ| − I: «инверсия относительно среднего» — каждая амплитуда α_x заменяется на 2ᾱ − α_x, где ᾱ — среднее всех амплитуд. Схемно: H^⊗n, затем переворот фазы всех состояний, кроме |0…0⟩, затем снова H^⊗n.

В начале алгоритма все помеченные амплитуды одинаковы, как и все непомеченные. Оракул меняет знак первых, после чего отражение относительно среднего увеличивает их модуль и уменьшает модуль остальных. Это описание верно до приближения к оптимальному числу итераций; дальнейшие шаги снова уменьшают вероятность успеха.

8.3. Геометрия: вращение в плоскости

Точный анализ неожиданно умещается в двумерную картинку. Введём два нормированных вектора: |β⟩ — равномерная суперпозиция помеченных состояний, |α⟩ — равномерная суперпозиция непомеченных. Начальное состояние лежит в их плоскости:

|ψ⟩ = cos(θ/2)·|α⟩ + sin(θ/2)·|β⟩, где sin(θ/2) = √(M/N).

Ключевое наблюдение: оба оператора не выводят из этой плоскости. O — отражение относительно |α⟩ (меняет знак компоненты |β⟩); D — отражение относительно |ψ⟩. А композиция двух отражений плоскости — это поворот на удвоенный угол между осями: каждая итерация G поворачивает вектор состояния на угол θ в сторону |β⟩. После k итераций состояние образует с |α⟩ угол (2k+1)θ/2, и вероятность измерить помеченный элемент равна sin²((2k+1)θ/2).

Число итераций. Требуется приблизить (2k+1)θ/2 к π/2. Оптимальное целое k выбирают ближайшим к π/(2θ) − 1/2; при M ≪ N

k ≈ (π/4)·√(N/M), поскольку θ ≈ 2√(M/N).

Например, для N = 2²⁰ = 1 048 576 и одного помеченного входа требуется около 804 итераций вместо примерно половины пространства при последовательном классическом поиске. При известном M и правильном округлении вероятность успеха не меньше 1 − M/N; найденный кандидат проверяют одним дополнительным запросом.

Перелёт. Поворот не останавливается у |β⟩: после оптимума вероятность убывает, затем снова растёт. Поэтому фиксированное число итераций требует знания M. Если оно неизвестно, можно оценить угол методом квантового подсчёта либо выбирать число итераций по рандомизированной стратегии Бойера–Брассара–Хойера–Таппа; ожидаемая сложность остаётся O(√(N/M)).

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

Теорема BBBV. Любой квантовый алгоритм, который находит единственный помеченный элемент с постоянной вероятностью успеха, должен сделать Ω(√N) запросов к неструктурированному оракулу. Алгоритм Гровера оптимален в этой модели с точностью до постоянного множителя.

Нижняя оценка не доказывает, что NP-полные задачи вообще не имеют полиномиальных квантовых алгоритмов: такой алгоритм мог бы использовать структуру конкретной задачи, отсутствующую у чёрного ящика. Она доказывает более узкое и важное утверждение: заменить полный перебор универсальным квантовым поиском и получить полиномиальное время нельзя.

8.5. Усиление амплитуды

Гровер — частный случай общего приёма. Пусть унитарная схема A готовит состояние, измерение которого даёт хороший результат с вероятностью p, и мы умеем обратимо отмечать хорошие исходы. Усиление амплитуды использует A, A⁻¹ и два отражения, повышая успех за O(1/√p) итераций вместо O(1/p) независимых классических повторов. Рандомизированную классическую процедуру для этого нужно сначала реализовать когерентно. Родственные методы дают, например, квантовый алгоритм поиска коллизий с O(N^1/3) запросов и памяти вместо классической границы порядка N^1/2 в соответствующей модели.

8.6. Следствия для криптографии: трезвый взгляд

В модели последовательных запросов полный перебор ключа длины k сокращается с порядка 2^k до порядка 2^k/2 итераций. Поэтому AES-128 часто описывают как 64-битный уровень против идеализированного поиска Гровера, а AES-256 — как 128-битный. Это полезная консервативная шкала, но не готовая оценка времени атаки: она не учитывает стоимость оракула, коррекцию ошибок, параллелизм и ограничения данных. Для новых долгоживущих систем AES-256 даёт больший запас, тогда как развёрнутые схемы RSA и дискретного логарифма требуют замены, а не простого удвоения ключа.

Для перехода от запросов к инженерной оценке нужны дополнительные факторы:

• Ограниченное распараллеливание. Если разделить пространство между P независимыми квантовыми машинами, время уменьшается лишь до порядка √(N/P), то есть ускоряется в √P, а не в P. Глубина остаётся огромной; в отказоустойчивой машине это означает длительное выполнение и дополнительные ресурсы для подавления логических ошибок.
• Дорогой оракул. Каждая итерация должна обратимо вычислить шифр, сравнить результат и очистить рабочие регистры. Число запросов умножается на стоимость этой схемы и её отказоустойчивой реализации.
• Модель атаки. Известная открытая пара «текст — шифртекст», число целей, доступная квантовая память и возможность построить когерентный оракул меняют ресурсы. Поэтому «половина битов» — верхнеуровневая асимптотика, а не универсальный бюджет атаки.

Итоги главы

• Гровер находит помеченный элемент среди N за O(√(N/M)) запросов: оракул-фаза + диффузор = поворот на угол θ ≈ 2√(M/N) за итерацию.
• Оптимальное число итераций (π/4)√(N/M); перебор итераций «с запасом» вреден — вероятность синусоидальна.
• Теорема BBBV: √N — доказанный предел в модели неструктурированного оракула; универсального полиномиального ускорения полного перебора она не допускает.
• Усиление амплитуды сокращает число вызовов когерентно реализуемого генератора кандидатов с O(1/p) до O(1/√p).
• Для криптографии «половина битовой стойкости» — оценка последовательной сложности запросов; физическая атака дополнительно оплачивает обратимый оракул, коррекцию ошибок и ограниченный параллелизм.

Упражнения

1. N = 4, M = 1. Вычислите θ и покажите, что ровно одна итерация Гровера находит помеченный элемент с вероятностью 1. Проверьте прямым подсчётом амплитуд «инверсией относительно среднего»: начальные амплитуды (1/2, 1/2, 1/2, 1/2), после оракула у помеченного знак минус — что даст диффузор?
2. N = 8, M = 1: найдите оптимальное число итераций и вероятность успеха после него. Что произойдёт после четырёх итераций?
3. Проверьте, что диффузор D = 2|ψ⟩⟨ψ| − I унитарен, и убедитесь, что приведённая в 8.2 схемная реализация (H-слой, фазовый переворот всех состояний кроме нуля, H-слой) действительно равна D. Указание: средний блок равен 2|0⟩⟨0| − I.
4. Покажите, что при M = N/4 достаточно ровно одной итерации. Какая практическая мораль для задач, где кандидатов «не так уж мало»?
5. Пусть M = N/2. Сколько итераций нужно и что вообще происходит с алгоритмом? Сравните с тривиальным классическим решением.
6. Оцените число гроверовских итераций для перебора ключа AES-128 и, приняв (грубо) 10⁻⁶ секунды на итерацию, время атаки на одной квантовой машине. Сравните с возрастом Вселенной и сделайте вывод раздела 8.6 самостоятельно.

Ответы и указания. 1: sin(θ/2)=1/2, поэтому θ=π/3; после одной итерации угол равен π/2 и успех имеет вероятность 1. Среднее после оракула равно 1/4, непомеченные амплитуды переходят в 0, помеченная — в 1. 2: k=2, P=sin²(5·arcsin(1/√8))≈0,945; после четырёх итераций P=sin²(9·arcsin(1/√8))≈0,012. 3: D²=I, поскольку |ψ⟩⟨ψ| — проектор; сопряжение 2|0⟩⟨0|−I слоем H даёт 2|ψ⟩⟨ψ|−I. 4: θ/2=π/6, и после одной итерации угол равен π/2, поэтому успех достоверен; когда решений много, асимптотический выигрыш мал и проверка случайных кандидатов может быть проще. 5: при M=N/2 успех равен 1/2 после любого числа итераций; оптимально выполнить ноль итераций, измерить и проверить ответ, повторяя при неудаче. 6: (π/4)·2⁶⁴≈1,45·10¹⁹ итераций; по микросекунде на итерацию это около 4,6·10⁵ лет, причём такая длительность одной отказоустойчивой итерации сама по себе нереалистично мала.

Лабораторная работа 4. Алгоритм Гровера в Qiskit

Задание 1. Оракул. Соберите оракул-фазу на 3 кубитах, помечающий строку |101⟩ в порядке Qiskit |q₂q₁q₀⟩: обрамите CCZ вентилями X на кубите 1. CCZ можно получить последовательностью qc.h(2); qc.ccx(0, 1, 2); qc.h(2). Для проверки сначала приготовьте H^⊗3|000⟩ и сравните Statevector до и после оракула: только амплитуда |101⟩ должна изменить знак. Проверка на одном базисном |101⟩ не подходит, потому что его знак был бы глобальной фазой.

Задание 2. Диффузор. Реализуйте последовательность H на всех кубитах, X на всех, CCZ, X на всех, H на всех. Она равна −D: отличается от принятого в тексте диффузора только глобальным знаком и потому даёт тот же алгоритм.

Задание 3. Полный алгоритм. Начальный слой H, затем k итераций (оракул + диффузор), измерение. Для N = 8, M = 1 оптимально k = 2 (упражнение 2). Выполните 1024 запуска и убедитесь, что |101⟩ выпадает с частотой ≈ 94–95%.

Задание 4. Перелёт. Постройте график частоты правильного ответа от числа итераций k = 0…8. Сравните с теоретической кривой sin²((2k+1)θ/2) — вы увидите синусоиду из раздела 8.3 экспериментально.

Задание 5*. Два помеченных элемента. Модифицируйте оракул, чтобы он помечал |101⟩ и |110⟩. Здесь M/N=1/4, поэтому одна итерация должна дать один из двух ответов с суммарной вероятностью 1; проверьте, что каждый появляется примерно в половине запусков.

Литература к главе

1. L. Grover, "A fast quantum mechanical algorithm for database search," STOC 1996. arxiv.org/abs/quant-ph/9605043
2. C. Bennett, E. Bernstein, G. Brassard, U. Vazirani, "Strengths and Weaknesses of Quantum Computing," SIAM J. Comput. 26, 1997. arxiv.org/abs/quant-ph/9701001
3. G. Brassard, P. Høyer, M. Mosca, A. Tapp, "Quantum Amplitude Amplification and Estimation," 2000. arxiv.org/abs/quant-ph/0005055
4. M. Nielsen, I. Chuang, "Quantum Computation and Quantum Information," гл. 6. Cambridge University Press, 2010.

Предыдущая глава || Содержание курса || Следующая глава