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

Если ты выполнишь шаг Гровера на векторе амплитуд, назовёшь нужное число шагов, объяснишь, что будет при лишних шагах, и скажешь, почему квадратичный выигрыш не решает NP-полных задач, - листай до «Теперь сам».

Как думаешь, что даёт квантовый компьютер перебору

Задача выполнимости: 2ⁿ наборов, один из них годится, проверить набор легко. Обычный перебор смотрит наборы по одному. Квантовый компьютер умеет подать на проверку все наборы сразу, в равной суперпозиции.

Ответь себе до чтения: за сколько обращений к проверке он найдёт годный набор - за одно? за n? За корень из числа наборов: 2 в степени n / 2. Если пользоваться только проверкой наборов, это доказанный предел, а не недостаток известного алгоритма. Для ста переменных - 2⁵⁰ обращений вместо 2¹⁰⁰: несравнимо лучше, и всё равно недостижимо. Квантовый компьютер ускоряет перебор, но оставляет его перебором.

На что это похоже

Раскачивание качелей. Одним толчком до верха не достать, но каждый толчок, сделанный в такт, добавляет немного высоты. Нужное число толчков известно заранее.

Шаг Гровера - один толчок. Амплитуда правильного варианта каждый раз подрастает на небольшую величину, и толчков нужно порядка корня из N. В одном аналогия подводит: на качелях лишний толчок в такт не вредит, а у Гровера шаг после вершины убавляет амплитуду.

Механизм: два отражения

Задача. Есть N вариантов, пронумерованных от 0, и функция-оракул, которая равна единице ровно на одном из них - отмеченном. Найти его, обращаясь к оракулу как можно реже.

Начало. Равная суперпозиция: у каждого варианта амплитуда 1 / √N. Измерение сейчас дало бы отмеченный вариант с вероятностью 1 / N.

Шаг Гровера состоит из двух действий.

1. оракул:                   сменить знак амплитуды отмеченного варианта
2. отражение от среднего:    вычислить среднее всех амплитуд m
                             и каждую амплитуду a заменить на 2m − a

Оба действия - отражения: смена знака - отражение относительно нуля, а 2m − a - точка на том же расстоянии от m по другую сторону. Проследим на числах при N = 4. Вначале все амплитуды равны 0,5.

начало:            0,5    0,5    0,5    0,5     отмечен вариант 2
после оракула:     0,5    0,5   −0,5    0,5     среднее  m = 0,25
после отражения:   0      0      1      0       2 · 0,25 − 0,5 = 0;
                                                2 · 0,25 + 0,5 = 1

Для четырёх вариантов хватает одного шага: отмеченный получается наверняка. Механика такая. Оракул делает одну амплитуду отрицательной, и среднее становится чуть меньше остальных амплитуд. Отражение от среднего остальные амплитуды слегка уменьшает, а отрицательную перекидывает далеко вверх: она отстояла от среднего дальше всех.

При большом N на первых шагах амплитуда отмеченного варианта растёт примерно на 2 / √N: среднее m почти равно 1 / √N, а отмеченная амплитуда −a переходит в 2m + a. Чтобы дорасти от 1 / √N до единицы, нужно порядка √N шагов; точнее - (π/4) · √N, около 0,8 · √N. Рост не линейный: каждый шаг поворачивает состояние на один и тот же малый угол, около 2 / √N, а амплитуда отмеченного варианта - синус набранного угла. До вершины нужно набрать четверть оборота, π/2, отсюда π/4. У вершины синус растёт всё медленнее, а после неё убывает, и лишние шаги портят результат.

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

Следствие для NP-полных задач. Перебор 2ⁿ сертификатов ускоряется до 2 в степени n / 2. Чтобы получить больше, нужно использовать устройство задачи, а не только проверку. Известно ли квантовое решение NP-полных задач за полиномиальное время? Нет, и большинство исследователей считает, что его не существует; доказательства, как и для P ≠ NP, нет.

Правило

Шаг Гровера: оракул меняет знак амплитуды отмеченного варианта, затем каждая амплитуда a заменяется на 2m − a, где m - среднее. После примерно (π/4) · √N шагов измерение даёт отмеченный вариант с вероятностью, близкой к единице; лишние шаги её уменьшают. Быстрее чем за порядка √N обращений поиск без структуры невозможен.

Разбор: шестьдесят четыре варианта, шаг за шагом

Функция shag_grovera выполняет оба отражения на векторе амплитуд. Отмечен вариант номер 37 из 64; номер нужен моделированию только затем, чтобы изобразить оракул, - сам алгоритм узнаёт о нём лишь через смену знака. В выводе - вероятность получить его при измерении до первого шага и после каждого из двенадцати; вторая строка вывода продолжает первую.

import math

def shag_grovera(s, otmechennyj):
    s[otmechennyj] = -s[otmechennyj]
    srednee = 0
    for a in s:
        srednee = srednee + a
    srednee = srednee / len(s)
    for i in range(len(s)):
        s[i] = 2 * srednee - s[i]

n = 64
otmechennyj = 37
s = [1 / math.sqrt(n)] * n
veroyatnosti = [round(s[otmechennyj] * s[otmechennyj], 4)]
for shag in range(12):
    shag_grovera(s, otmechennyj)
    veroyatnosti.append(round(s[otmechennyj] * s[otmechennyj], 4))
print(veroyatnosti[:7])
print(veroyatnosti[7:])

[0.0156, 0.1348, 0.3439, 0.5914, 0.8164, 0.9635, 0.9966]
[0.9074, 0.718, 0.475, 0.2381, 0.0656, 0.0001]

Вначале вероятность - 0,0156, одна шестьдесят четвёртая. После одного шага - 0,13, после трёх - 0,59, после шести - 0,9966. Шесть обращений к оракулу вместо тридцати двух в среднем при переборе.

Дальше вероятность падает: 0,91 после седьмого шага, 0,48 после девятого и 0,0001 после двенадцатого - меньше, чем была до начала. Алгоритм нельзя «крутить до результата»: проверить, найден ли ответ, значит измерить, а измерение разрушает состояние. Число шагов нужно знать заранее, для этого нужно знать N и то, что отмеченный вариант один.

Моделирование здесь хранит все 64 амплитуды и на каждом шаге проходит по ним: на обычном компьютере это дороже простого перебора. Выигрыш существует только на квантовом устройстве, где отражение от среднего - операция над кубитами, а не цикл по вектору: вентили Адамара на всех кубитах, смена знака у всех строк, кроме нулевой, и снова вентили Адамара - порядка n операций для n кубитов (шести, а не 64, как у переменной n в программе). Что эта тройка даёт именно 2m − a, здесь принято без вывода.

Разбор: корень против половины

Для четырёх размеров сравним среднее число обращений при переборе, примерно N / 2, с числом шагов Гровера, взятым как целая часть (π/4) · √N, и посмотрим на вероятность успеха.

import math

def shag_grovera(s, otmechennyj):
    s[otmechennyj] = -s[otmechennyj]
    srednee = 0
    for a in s:
        srednee = srednee + a
    srednee = srednee / len(s)
    for i in range(len(s)):
        s[i] = 2 * srednee - s[i]

for n in [16, 64, 256, 1024]:
    shagov = math.floor(math.pi / 4 * math.sqrt(n))
    s = [1 / math.sqrt(n)] * n
    for povtor in range(shagov):
        shag_grovera(s, 5)
    print(n, n // 2, shagov, round(s[5] * s[5], 4))

16 8 3 0.9613
64 32 6 0.9966
256 128 12 0.9999
1024 512 25 0.9995

Столбцы: N, обращений при переборе в среднем, шагов Гровера, вероятность успеха. Число вариантов растёт вчетверо - число шагов Гровера вдвое: 3, 6, 12, 25. Вероятность успеха - от 0,96 до 0,9999; редкую неудачу обнаруживают одной обычной проверкой и повторяют алгоритм.

Теперь продолжим таблицу в уме.

вариантов            перебор            Гровер
2²⁰ (миллион)        полмиллиона        около 800
2⁴⁰                  5 · 10¹¹           около 800 тысяч
2⁶⁴                  10¹⁹               3 · 10⁹
2¹²⁸                 10³⁸               10¹⁹

Для ключа шифра из 128 бит перебор безнадёжен, а 10¹⁹ квантовых шагов - это века при миллиарде шагов в секунду, срок, о котором уже можно спорить. Поэтому симметричные шифры на случай квантовых компьютеров берут с ключом вдвое длиннее: у ключа из 256 бит и после извлечения корня остаётся 2¹²⁸.

Для выполнимости формулы из ста переменных Гровер даёт 2⁵⁰ шагов, каждый из которых - вычисление формулы на квантовом устройстве. Экспонента осталась экспонентой, уменьшился только показатель.

Что ломается без этого

«Квантовый компьютер перебирает всё сразу». Он перебирает за корень, и это доказанный предел для поиска вслепую.

Шагов делают «с запасом». Лишние шаги уменьшают вероятность успеха вплоть до нуля. Число шагов - часть алгоритма.

Не учитывают число отмеченных вариантов. Если их M, шагов нужно порядка √(N / M). С неверным M алгоритм проскакивает вершину.

«NP-полные задачи решены». Из 2ⁿ получается 2 в степени n / 2. Для задач такого рода квадратичное ускорение меняет границу применимости, а не класс.

Зачем это в работе

Длина ключей. Практический вывод из алгоритма Гровера уже сделан: для симметричного шифрования и хеш-функций достаточно запаса длины: ключа вдвое длиннее, выхода хеш-функции подлиннее. Это намного мягче, чем то, что алгоритм следующего урока делает с шифрами с открытым ключом.

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

Понимание цены. Шаг Гровера включает вычисление проверяющей функции на суперпозиции - целую квантовую схему. Шаги нельзя раздать тысяче машин с тем же выигрышем: каждой из k машин достаётся N / k вариантов и √(N / k) шагов - в √k раз меньше, а не в k, как у обычного перебора.

Теперь сам

1. Вариантов 10 000, отмечен один. Сколько примерно шагов Гровера нужно?
2. Проведи шаг Гровера для N = 4, если амплитуды сейчас 0,5; 0,5; 0,5; 0,5 и отмечен первый вариант.
3. После шести шагов при N = 64 вероятность 0,9966. Почему не сделать ещё шесть для надёжности?
4. Сколько шагов Гровера нужно для перебора ключей длиной 80 бит?
5. Почему алгоритм Гровера не означает, что NP-полные задачи решаются за полиномиальное время?