Алгоритм Гровера: поиск за корень из N

Поиск иголки в стоге сена за ~корень из N шагов вместо N — за счёт амплитудного усиления.

Алгоритм Гровера находит выделенный элемент в неструктурированном наборе из N вариантов примерно за корень из N запросов вместо N в классическом переборе.

Задача и обещание

Есть N вариантов и оракул, умеющий сказать «да/нет» для каждого: это искомый элемент или нет. Структуры никакой — отсортировать или схитрить нельзя. Классически в среднем нужно проверить N/2 вариантов. Гровер находит ответ за порядка корня из N обращений. Для N = миллион это разница между ~500 000 и ~1000 шагами. Ускорение квадратичное (не экспоненциальное!), но универсальное: применимо к любому перебору, включая взлом симметричных шифров.

Амплитудное усиление по шагам

Идея: начать с равной суперпозиции всех N вариантов, затем повторять два действия — оракул помечает нужный вариант сменой знака амплитуды, а «диффузор» отражает все амплитуды относительно среднего. Каждый такой раунд чуть увеличивает амплитуду нужного варианта. Промоделируем это прямо на массиве амплитуд.

import math

N = 16
target = 11
amp = [1/math.sqrt(N)] * N        # равная суперпозиция

def oracle(a):
    a[target] = -a[target]        # пометить нужный сменой знака

def diffuse(a):
    avg = sum(a) / len(a)
    for i in range(len(a)):
        a[i] = 2*avg - a[i]       # отражение относительно среднего

steps = round(math.pi/4 * math.sqrt(N))   # оптимальное число итераций
for _ in range(steps):
    oracle(amp)
    diffuse(amp)

probs = [round(x*x, 3) for x in amp]
print('итераций:', steps)
print('p(target=%d) = %.3f' % (target, amp[target]**2))
print('макс. p у элемента:', probs.index(max(probs)))

Вывод:

итераций: 3
p(target=11) = 0.961
макс. p у элемента: 11

За 3 итерации вероятность найти нужный элемент при измерении выросла с 1/16 (0.0625) до ~0.96.

Как работает под капотом

Геометрически каждая пара «оракул + диффузор» поворачивает вектор состояния на маленький угол в сторону искомого. Через ~ (пи/4)·корень из N поворотов вектор почти совпадёт с целевым — тогда и надо измерять. Важная тонкость: итераций должно быть именно столько, не больше. Если перестараться, вектор «проскочит» цель, и вероятность снова упадёт. Это контринтуитивно: лишние шаги вредят. Поэтому число итераций считают заранее по формуле.

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

Ждать экспоненциального ускорения. У Гровера оно квадратичное (корень из N).
Делать слишком много итераций — вероятность успеха падает после оптимума.
Думать, что Гровер «взломает» AES мгновенно. Он лишь вдвое уменьшает эффективную длину ключа — лечится удлинением ключа.

Итог

Гровер ищет среди N вариантов за ~корень из N шагов (квадратичное ускорение).
Механизм — амплитудное усиление: оракул помечает, диффузор отражает относительно среднего.
Число итераций строго оптимально; перебор шагов вредит.