Алгоритм Гровера: квантовый поиск
Урок 11 из 23 курса «Квантум: курс с нуля». Бесплатно, с анимациями и тестом.
Задача про коробки
Перед тобой N закрытых коробок, подарок лежит в одной. Подсказок нет: открыл, посмотрел, закрыл. В среднем придётся открыть половину коробок, в худшем случае все. Квантовая версия: у нас есть «оракул», схема, которая отвечает, та ли это коробка. В 1996 году Лов Гровер из Bell Labs показал, как найти подарок примерно за √N вопросов. Для миллиона коробок это около 800 вопросов вместо полумиллиона.
Как это работает: метка и отражение
Сначала гейты H дают всем коробкам одинаковую амплитуду. Шаг 1: оракул ставит минус амплитуде нужной коробки, вот наш рецепт с меткой. Шаг 2: «отражение относительно среднего». Среднее чуть опустилось из-за минуса, и каждую амплитуду переворачивают вокруг него. Обычные коробки становятся чуть ниже, а отрицательная прыгает высоко вверх. Повторяем пару «метка + отражение», и с каждым разом нужная коробка растёт.
Главное — вовремя остановиться
Неочевидная деталь: Гровер — не «чем дольше, тем лучше». Амплитуда нужной коробки растёт как вращение стрелки. Для 64 коробок примерно после 6 шагов шанс почти 100%, а если продолжать, стрелка проскочит мимо и шанс начнёт падать. Поэтому число шагов считают заранее: примерно π/4 · √N. Если не знаешь, сколько подарков в коробках, есть хитрые варианты алгоритма, но это уже детали.
Гровер и шифрование
Подбор ключа шифра — это и есть поиск одной коробки среди огромного числа. У AES-128 вариантов 2 в степени 128. Гровер берёт корень, и остаётся 2 в степени 64 шагов, то есть защита «128 бит» превращается в «64 бита». На практике даже это очень много: шаги Гровера идут строго друг за другом, и их не раскидаешь на тысячи машин так же легко, как обычный перебор. Но лекарство простое и уже применяется: AES-256 после Гровера всё ещё держит 128 бит.
Предел скорости
Может, кто-то придумает поиск ещё быстрее? Нет: в 1997 году четверо исследователей, Беннет, Бернштейн, Брассар и Вазирани, доказали, что для «слепого» поиска √N — это предел для любого квантового компьютера. Отсюда важный вывод. Многие трудные задачи, например оптимальный маршрут доставки, по сути сводятся к перебору. Квантовый компьютер ускорит их максимум до корня, а не сделает мгновенными. Экспоненциального ускорения для таких задач никто не нашёл.
Где Гровер реально полезен
Звучит как «квантовый Google», но для поиска по обычной базе данных Гровер почти бесполезен. Чтобы спросить оракула, данные сначала надо загрузить в квантовую память, а это уже займёт порядка N шагов и съест весь выигрыш. Реальная польза — там, где «коробки» не хранятся, а вычисляются формулой: подбор ключей, проверка решений, подпрограмма внутри более сложных алгоритмов. И всё это потребует больших компьютеров с коррекцией ошибок.
Проверь себя
- Сколько примерно шагов Гровера нужно для 10 000 вариантов?
Правильный ответ: Около 80. √10 000 = 100, а π/4 · 100 ≈ 79. Квадратичное ускорение, а не мгновенное. - Друг повторил шаги Гровера втрое больше нужного, «для надёжности». Что будет?
Правильный ответ: Шанс упадёт: стрелка проскочит мимо ответа. Гровер — это вращение. После оптимума амплитуда нужной коробки снова уменьшается. - Нужно ли из-за Гровера срочно менять AES-256?
Правильный ответ: Нет: после Гровера у него остаётся 128 бит защиты. Гровер вдвое уменьшает «битность», а 128 бит считаются надёжными. Поэтому AES-256 и советуют на долгий срок.