Алгоритм Шора и границы: что квантовый компьютер ускоряет, а что нет

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

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

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

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

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

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

Квантовая часть алгоритма - такой взгляд издалека. Она не идёт вдоль последовательности, а устраивает интерференцию, в которой выживают только направления, согласованные с периодом.

Механизм: от множителей к периоду

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

1. выбрать число a от 2 до N − 1;
   если у a и N есть общий делитель больше 1 - он найден
2. найти период r:  наименьшее r > 0, при котором
   a в степени r  даёт остаток 1 при делении на N
3. если r нечётный - вернуться к шагу 1 с другим a
4. вычислить  h = a в степени r/2  по модулю N;
   если h = N − 1 - вернуться к шагу 1
   иначе  НОД(h − 1, N)  и  НОД(h + 1, N)  - делители N

Почему это работает. По определению периода a в степени r при делении на N даёт остаток 1, то есть h² − 1 делится на N. Но h² − 1 = (h − 1)(h + 1). Произведение делится на N, а ни один сомножитель сам по себе - нет: h − 1 не делится, потому что иначе период был бы вдвое короче; h + 1 не делится, потому что случай h = N − 1 исключён. Значит, множители N разошлись по двум скобкам, и наибольший общий делитель каждой скобки с N - его настоящий делитель.

Для случайного a шаги 3 и 4 срабатывают удачно не реже чем в половине случаев, так что попыток нужно немного.

Где трудность. Шаги 1, 3 и 4 дёшевы: алгоритм Евклида и возведение в степень по модулю полиномиальны по числу цифр - если возводить быстрым способом, удвоениями, как в разделе о числах; в программе ниже ради простоты стоит обычный цикл. Шаг 2 - нет. Период может быть порядка N, и перебор степеней подряд требует порядка N умножений - экспоненту от длины записи. Лучшие известные классические алгоритмы разложения работают быстрее перебора, но всё равно не за полиномиальное время.

Что делает квантовая часть. Готовит в одной группе кубитов равную суперпозицию показателей x, вычисляет в другой группе остатки a в степени x и применяет к первой квантовое преобразование Фурье - ту самую решётку: оно усиливает амплитуды, согласованные с периодом. Здесь и нужны комплексные амплитуды из первого урока главы: преобразование приписывает слагаемым не знаки + и −, как вентили прошлых уроков, а комплексные множители с модулем 1. Такое число - точка на окружности, «поворот» на свой угол, и разных поворотов столько, сколько слагаемых в суперпозиции. У слагаемых, согласованных с периодом, повороты смотрят в одну сторону и складываются, у остальных - в разные и гасят друг друга. После него измерение с большой вероятностью даёт число, связанное с периодом; измеренное число близко к кратному M / r, где M - число слагаемых в суперпозиции, и период r находят как знаменатель несократимой дроби с небольшим знаменателем, ближайшей к отношению измеренного числа к M. В настоящем алгоритме M - степень двойки не меньше N²; период не обязан делить M, отсюда «близко», а не «равно». Пример упрощён: N = 15, a = 7, M = 16. Измерение даёт одно из чисел 0, 4, 8, 12. При 12 дробь 12/16 = 3/4, знаменатель 4 - период. При 8 дробь 1/2: знаменатель 2 - лишь делитель периода, а ноль не сообщает ничего. Поэтому измерений нужно несколько. Операций нужно порядка куба числа цифр N.

Класс BQP - задачи, которые квантовый компьютер решает за полиномиальное время с малой вероятностью ошибки. Известно: P ⊆ BQP ⊆ PSPACE. Разложение на множители в форме вопроса «есть ли у N делитель меньше k» лежит в BQP. NP-полные задачи, насколько известно, - нет: у разложения есть период, у выполнимости такой структуры не нашли, и для поиска вслепую предел - корень.

Правило

Разложение N сводится к поиску периода r остатков степеней a по модулю N: при чётном r и h = a в степени r / 2, не равном N − 1, делители - НОД(h − 1, N) и НОД(h + 1, N). Квантовый компьютер находит период за полиномиальное число операций; всё остальное делает обычная программа. P ⊆ BQP ⊆ PSPACE; NP-полные задачи в BQP, по общему ожиданию, не лежат.

Разбор: классическая часть целиком

Функция period ищет период перебором - это тот самый шаг, который на больших числах невозможен. Функция razlozhit делает остальное; первой строкой она проверяет общий делитель - без этого поиск периода для такого a не закончился бы; в этой ветке на месте периода стоит ноль, например razlozhit(15, 6) вернёт [6, 0, 3, 5]. Ветку нечётного периода даёт razlozhit(21, 4): период 3. Первая строка вывода - остатки степеней семёрки по модулю 15.

def nod(a, b):
    while b > 0:
        ostatok = a % b
        a = b
        b = ostatok
    return a

def period(a, n):
    x = a % n
    r = 1
    while x != 1:
        x = x * a % n
        r = r + 1
    return r

def stepen(a, k, n):
    itog = 1
    for povtor in range(k):
        itog = itog * a % n
    return itog

def razlozhit(n, a):
    if nod(a, n) > 1:
        return [a, 0, nod(a, n), n // nod(a, n)]
    r = period(a, n)
    if r % 2 == 1:
        return [a, r, "период нечётный"]
    polovina = stepen(a, r // 2, n)
    if polovina == n - 1:
        return [a, r, "половина даёт -1"]
    return [a, r, nod(polovina - 1, n), nod(polovina + 1, n)]

ostatki = []
x = 1
for i in range(9):
    ostatki.append(x)
    x = x * 7 % 15
print(ostatki)
for para in [[15, 7], [15, 2], [15, 14], [21, 2],
             [21, 5], [35, 2], [77, 2], [221, 2]]:
    print(para[0], razlozhit(para[0], para[1]))

[1, 7, 4, 13, 1, 7, 4, 13, 1]
15 [7, 4, 3, 5]
15 [2, 4, 3, 5]
15 [14, 2, 'половина даёт -1']
21 [2, 6, 7, 3]
21 [5, 6, 'половина даёт -1']
35 [2, 12, 7, 5]
77 [2, 30, 7, 11]
221 [2, 24, 13, 17]

Остатки 1, 7, 4, 13 повторяются: период 4. Половина периода - 2; 7² = 49 даёт остаток 4. Тогда НОД(3, 15) = 3 и НОД(5, 15) = 5. Число 15 разложено.

В строках вывода - число N, выбранное a, период и делители. Для a = 14 при N = 15 период равен 2, а 14 - это −1 по модулю 15: попытка неудачна, нужно другое a. То же с a = 5 при N = 21. Остальные попытки дают разложение: 21 = 7 · 3, 35 = 7 · 5, 77 = 7 · 11, 221 = 13 · 17.

Ничего квантового в программе нет. Если бы функция period работала быстро, RSA был бы сломан этой программой на обычном ноутбуке.

Разбор: сколько стоит период

Посмотрим, как растёт период - и с ним работа перебора - для произведений двух простых чисел всё большей длины. В выводе: длина числа в битах, само число и период остатков степеней двойки.

def period(a, n):
    x = a % n
    r = 1
    while x != 1:
        x = x * a % n
        r = r + 1
    return r

for chislo in [15, 221, 1007, 3127, 14017, 47897]:
    bit = 0
    m = chislo
    while m > 0:
        bit = bit + 1
        m = m // 2
    print(bit, chislo, period(2, chislo))

4 15 4
8 221 24
10 1007 468
12 3127 1508
14 14017 6890
16 47897 23730

Числа - произведения двух простых: 3 · 5, 13 · 17, 19 · 53, 53 · 59, 107 · 131, 211 · 227. Период растёт примерно вместе с самим числом: 468, 1508, 6890, 23 730. В последних четырёх строках каждые два бита в записи - это в три-пять раз больше умножений.

Ключ RSA - число из 2048 бит. Период для него при случайном a - как правило, число сравнимой длины, и перебор степеней требует порядка 2²⁰⁰⁰ умножений. Квантовой части нужно порядка 2048³, несколько миллиардов элементарных операций, - если есть машина, способная выполнить их без ошибок.

Такой машины нет. Алгоритмом Шора на квантовых устройствах раскладывали только числа 15 и 21, и то по упрощённым схемам, в которые заложено знание о самом числе. Для ключа из 2048 бит по оценкам 2025 года нужно порядка миллиона физических кубитов, работающих несколько суток с исправлением ошибок; у существующих устройств их сотни и тысячи, и исправление ошибок только начинает работать. Оценки при этом быстро снижаются: за шесть лет до того называли двадцать миллионов.

Поэтому переход начат заранее. В 2024 году приняты первые стандарты шифров с открытым ключом, которые не опираются ни на разложение, ни на дискретный логарифм; по плану американского института стандартов прежние алгоритмы выводятся из употребления к 2035 году. Спешка объяснима: переписку, перехваченную сегодня, можно сохранить и расшифровать, когда машина появится.

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

«Алгоритм Шора - это квантовая магия». Три четверти его - арифметика остатков. Квантовый шаг один: найти период.

«Раз разложение ускорено экспоненциально, ускорено всё». Ускорение держится на периодичности. У NP-полных задач такой структуры не нашли; для них известен только корень Гровера.

«Разложение на множители NP-полно». Не известно, и вряд ли: вопрос «есть ли у числа делитель меньше k» лежит одновременно в NP и в co-NP. Квантовый компьютер ломает шифры, а не теорию сложности.

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

«Симметричные шифры тоже сломаны». Для них известна только атака Гровера, и от неё защищает удвоение длины ключа.

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

Криптография в проектах. Всё, что стоит на RSA, обмене ключами Диффи-Хеллмана и эллиптических кривых, подлежит замене (стойкость двух последних - тоже задача о скрытом периоде, и её решает тот же приём); симметричным шифрам достаточно ключей подлиннее, хеш-функциям - выхода подлиннее. При проектировании системы со сроком жизни в десять лет это уже требование, а не прогноз.

Трезвая карта возможностей. По сравнению с лучшими известными обычными алгоритмами квантовый компьютер ускоряет сильнее любого многочлена задачи с особой структурой - периоды, моделирование квантовых систем (для краткости говорят «экспоненциально», хотя лучшие обычные алгоритмы разложения немного быстрее экспоненты); квадратично - поиск вслепую; и не ускоряет заметно почти всё остальное: сортировку, запросы к базам данных с индексами, обычную арифметику.

Границы этого раздела. Тезис Чёрча-Тьюринга квантовая модель не задевает: вычислимое остаётся тем же. Под вопросом его усиленная версия - о том, что любая физическая машина моделируется обычной с полиномиальным замедлением. Алгоритм Шора - главный довод против неё.

Теперь сам

1. Найди период остатков степеней двойки по модулю 15 и разложи 15 с его помощью.
2. Для N = 21 и a = 2 период равен 6. Вычисли делители.
3. Период оказался нечётным. Что делать?
4. Какой шаг алгоритма Шора выполняет квантовый компьютер и почему обычный не справляется?
5. Почему из алгоритма Шора не следует, что квантовый компьютер быстро решает задачу выполнимости?