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

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

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

7.1. Задача и её цена

Дано составное нечётное N (для определённости — произведение двух больших простых, как в RSA); найти нетривиальный делитель. Обозначим n = ⌈log₂N⌉ — длину числа в битах.

Лучший известный классический алгоритм для общих больших целых — общий метод решета числового поля (GNFS) — имеет субэкспоненциальную эвристическую сложность exp(O(n^1/3(log n)^2/3)). Показательный опубликованный результат — факторизация 829-битного RSA-250 в 2020 году примерно за 2700 ядро-лет; это несопоставимо с 2048-битным модулем. Алгоритм Шора использует полиномиальное число логических операций. Важно различать эту асимптотику и физическую выполнимость: коррекция ошибок создаёт огромные, зависящие от архитектуры постоянные множители.

7.2. Сведение к поиску порядка

Выберем случайное a, 1 < a < N. Если gcd(a, N) > 1, НОД уже является нетривиальным делителем. Иначе порядком элемента a по модулю N называется наименьшее r ≥ 1, для которого a^r ≡ 1 (mod N). Последовательность a^k mod N периодична по k с периодом r.

Утверждение. Пусть порядок r чётен и a^r/2 ≢ −1 (mod N). Тогда gcd(a^r/2 − 1, N) и gcd(a^r/2 + 1, N) — нетривиальные делители N.

Доказательство. Обозначим b = a^r/2. Из a^r ≡ 1 следует b² − 1 = (b − 1)(b + 1) ≡ 0 (mod N): произведение делится на N. При этом b ≢ 1 (иначе порядок был бы ≤ r/2, а r минимален) и b ≢ −1 (условие утверждения) — значит, ни один из сомножителей сам по себе на N не делится. Простые делители N вынуждены распределиться между (b−1) и (b+1), и НОД каждого из них с N строго между 1 и N. ∎

А если не повезло — r нечётен или b ≡ −1? Берём другое случайное a и повторяем. Теорема (доказательство — теория чисел, приводим факт): для составного нечётного N, не являющегося степенью простого, случайное a подходит с вероятностью не меньше 1/2. Ожидаемое число попыток — не больше двух. Крайние случаи отсекаются заранее классическими проверками: чётное N делим на 2; степень простого N = p^k распознаётся извлечением корней за полиномиальное время.

Таким образом, рандомизированное классическое сведение превращает факторизацию в повторяемую задачу поиска порядка. Квантовая часть алгоритма решает именно эту задачу за время, полиномиальное по длине N.

7.3. Квантовый поиск порядка

Введём оператор модульного умножения на a:

U_a|y⟩ = |a·y mod N⟩ (для y ≥ N оператор действует тождественно).

Умножение на число, взаимно простое с N, переставляет вычеты 0, …, N−1; тождественное действие на остальных базисных состояниях дополняет эту перестановку до всего регистра. Поэтому U_a унитарен. Управляемое умножение на известную константу по модулю N реализуется обратимой арифметикой с полиномиальным числом вентилей; в учебной оценке со школьной арифметикой это O(n²) элементарных операций на одно умножение, не считая архитектурных накладных расходов.

Собственные векторы U_a. Для каждого s = 0, 1, …, r−1 положим

|u_s⟩ = r^−1/2 ∑_k=0^r−1 e^−2πisk/r |a^k mod N⟩.

Проверим действие оператора: U_a сдвигает |a^k⟩ → |a^k+1⟩, что эквивалентно сдвигу индекса суммирования, вынимающему из суммы множитель:

U_a|u_s⟩ = e^2πis/r|u_s⟩.

Собственные фазы оператора — дроби s/r: искомый порядок сидит в знаменателе собственных значений. Задача превратилась в оценку фазы (глава 6)!

Для оценки определённой фазы потребовался бы собственный вектор |u_s⟩, зависящий от неизвестного r. Однако сумма всех этих векторов имеет простой вид:

r^−1/2 ∑_s=0^r−1 |u_s⟩ = |1⟩

При суммировании по s геометрические суммы равны нулю для k ≠ 0, и остаётся только |a⁰ mod N⟩ = |1⟩. Поэтому легко приготовляемое состояние |1⟩ является равной суперпозицией собственных векторов данного цикла. Оценка фазы выдаёт одну из фаз s/r с равными вероятностями; по одному или нескольким таким результатам порядок восстанавливается классически.

Схема поиска порядка.

1. Счётный регистр из t = 2n кубитов в |0⟩ и рабочий регистр из n кубитов в состоянии |1⟩.
2. H^⊗t на счётном регистре.
3. Управляемые степени U_a^2k — по одной на каждый счётный кубит. Здесь U_a^2k является умножением на классически вычисленную константу a^2k mod N. Повторное квадрирование находит все эти константы за полиномиальное время, а каждая затем реализуется обратимой схемой модульного умножения.
4. Обратное QFT на счётном регистре и измерение. Результат m задаёт дробь m/2^t, распределение которой сосредоточено около одной из фаз s/r. С постоянной вероятностью ошибка ближайшего результата не превосходит половины шага сетки, то есть 1/2^t+1.

7.4. Классическая постобработка: цепные дроби

Пусть измерение дало φ = m/2^t, близкое к неизвестной дроби s/r, где r < N ≤ 2ⁿ. Разложение φ в цепную дробь порождает последовательность наилучших рациональных приближений — подходящих дробей. Теорема утверждает: если |s/r − φ| ≤ 1/(2r²), то несократимая форма s/r встретится среди них. При t = 2n половина шага измерительной сетки равна 2^−(2n+1) ≤ 1/(2N²) < 1/(2r²), поэтому ближайший результат оценки фазы удовлетворяет условию.

Нельзя брать первую подходящую дробь со знаменателем меньше N: ранние приближения вроде 0/1 также проходят это ограничение. Подходящие дроби перебирают по порядку, для каждого знаменателя q < N проверяют a^q ≡ 1 (mod N) и останавливаются только после подтверждения порядка; иногда проверяют и небольшие кратные q. Если gcd(s,r) > 1, цепная дробь возвращает собственный делитель порядка, который такую проверку не пройдёт. Тогда квантовую часть повторяют и объединяют информацию, например берут НОК знаменателей с последующей обязательной проверкой. Вероятность gcd(s,r)=1 равна φ(r)/r, поэтому число повторов зависит от арифметики конкретного r.

7.5. Алгоритм целиком и разбор примера

Алгоритм Шора (факторизация N):

1. Если N чётно — вернуть 2. Если N = p^k — вернуть p (классическая проверка).
2. Выбрать случайное a ∈ (1, N); если gcd(a, N) > 1 — вернуть этот НОД.
3. [Квантовая часть] Найти порядок r элемента a (разделы 7.3–7.4).
4. Если r нечётен или a^r/2 ≡ −1 (mod N) — вернуться к шагу 2.
5. Вернуть gcd(a^r/2 ± 1, N).

Пример: N = 15, a = 7. В 2001 году на семи ядерных спинах в ЯМР-системе была продемонстрирована специально скомпилированная версия алгоритма для 15. Это важный ранний эксперимент, но не масштабируемая реализация общей модульной арифметики.

• Порядок: 7¹ = 7, 7² = 49 ≡ 4, 7³ ≡ 28 ≡ 13, 7⁴ ≡ 91 ≡ 1 (mod 15). Итак, r = 4 — чётный, шаг 4 пройден: 7² ≡ 4 ≢ −1 ≡ 14.
• Делители: gcd(4 − 1, 15) = 3, gcd(4 + 1, 15) = 5. Действительно, 15 = 3 × 5.
• При t = 2n = 8 счётных кубитах измерение выдаёт с равными вероятностями m ∈ {0, 64, 128, 192}, соответствующие фазам s/4 = 0, 1/4, 1/2, 3/4. Здесь результат точен, поскольку 4 делит 2⁸. Для m = 64 и 192 несократимый знаменатель равен 4; для m = 128 кандидат 2 не проходит проверку 7² ≡ 1 (mod 15), а m = 0 не несёт информации о порядке. Вероятность получить полный порядок за одно измерение равна 1/2, а ожидаемое число независимых измерений до такого результата — два.

7.6. Стоимость: от учебного примера к RSA-2048

Логический уровень. Учебная схема использует O(n) логических кубитов и O(n³) элементарных вентилей со школьной обратимой арифметикой. Конкретные оптимизированные схемы меняют число анцилл, типы дорогих операций и постоянные множители; поэтому оценка «несколько тысяч логических кубитов и миллиарды логических операций» для RSA-2048 задаёт порядок, а не единственную спецификацию.

Физический уровень. Здесь результат резко зависит от кода, физической ошибки, связности, времени цикла, допустимого времени работы и числа фабрик вспомогательных состояний. Для одной и той же модели двумерного поверхностного кода оценка Гидни–Экеро составляла 20 миллионов шумных кубитов и восемь часов, а оценка Гидни 2025 года — менее миллиона и менее недели при ошибке 10⁻³, микросекундном цикле кода и других явно заданных допущениях. В препринте 2026 года для иной архитектуры — перенастраиваемых нейтральных атомов и высокоскоростных кодов — заявлена возможность криптографически значимого алгоритма Шора примерно с 10 тысячами физических кубитов, но с более длительным выполнением RSA-2048 и существенными нерешёнными инженерными задачами. Эти числа нельзя сравнивать как прогнозы даты появления машины: они показывают чувствительность ресурса к архитектуре и алгоритмическим улучшениям.

7.7. Дискретный логарифм: под ударом и эллиптика

Тот же аппарат решает задачу дискретного логарифма: по g и h = g^x в конечной группе найти x. Шор сводит её к скрытой периодичности функции двух переменных f(α, β) = g^αh^−β. Поэтому уязвимы широко применяемые семейства на факторизации и дискретном логарифме: RSA, классические Diffie–Hellman, DSA и Эль-Гамаль, а также ECDH и ECDSA. Оценки для P-256 могут быть ниже, чем для RSA-2048, но это определяется всей схемой групповой арифметики, кодом коррекции и архитектурой, а не одним сравнением длины ключей. Алгоритм Шора не ломает автоматически всю асимметричную криптографию: решёточные, кодовые, хешевые и другие постквантовые конструкции основаны на иных задачах.

Итоги главы

• Факторизация сводится (классически, элементарной теорией чисел) к поиску порядка: чётный порядок r с a^r/2 ≢ −1 даёт делители через НОД; случайное a подходит с вероятностью ≥ 1/2.
• Порядок — знаменатель собственных фаз s/r оператора умножения U_a; состояние |1⟩ — равная суперпозиция всех его собственных векторов, что позволяет запустить оценку фазы, не зная r.
• Управляемые степени U_a^2k реализуются умножением на заранее вычисленные константы; цепные дроби дают кандидатов на порядок, которые обязательно проверяются модульным возведением в степень.
• Учебная логическая оценка составляет O(n³) вентилей и O(n) кубитов; физические оценки для RSA-2048 различаются на порядки в зависимости от архитектуры и допущений.
• Дискретный логарифм, включая эллиптический, решается родственным алгоритмом; уязвимы развёрнутые системы на факторизации и дискретном логарифме, но не все асимметричные конструкции.

Упражнения

1. Найдите вручную порядки элементов a = 2, 4, 8, 11, 13, 14 по модулю 15. Какие из них приводят к успешной факторизации (шаги 4–5 алгоритма), а какие — к повтору?
2. Проведите полный прогон классической части для N = 21, a = 2: порядок, проверки, делители.
3. Докажите равенство r^−1/2∑_s|u_s⟩ = |1⟩, аккуратно просуммировав геометрические прогрессии.
4. Разложите 192/256 и 128/256 в цепные дроби и выпишите подходящие дроби. Для каждого знаменателя меньше 15 проверьте условие 7^q ≡ 1 (mod 15); объясните, почему одного ограничения q < 15 недостаточно.
5. Почему нельзя удешевить схему, взяв t = n счётных кубитов? Укажите, какое условие раздела 7.4 нарушится, и приведите пример двух дробей s/r с r < N, неразличимых при такой точности.
6. Мощность мультипликативной группы вычетов по модулю 15 равна φ(15) = 8. Проверьте на результатах упражнения 1 теорему Лагранжа: порядок каждого элемента делит 8. Как знание того, что r делит φ(N), могло бы помочь классическому алгоритму — и почему не помогает (что нужно знать, чтобы вычислить φ(N))?

Ответы и указания. 1: порядки 4, 2, 4, 2, 4, 2 соответственно; a = 14 ≡ −1 даёт a^r/2 ≡ −1 и требует повтора, остальные пять значений успешны. 2: r = 6, 2³ = 8 ≢ −1 (mod 21), gcd(7,21)=7, gcd(9,21)=3. 3: после подстановки определения коэффициент при |a^k⟩ пропорционален ∑_s=0^r−1e^−2πisk/r; сумма равна r при k=0 и нулю иначе. 4: 192/256 = 3/4 = [0;1,3] с подходящими дробями 0/1, 1/1, 3/4; 128/256 = 1/2 = [0;2]. Это также показывает, почему нельзя выбирать первую дробь только по ограничению знаменателя. 5: при t=n шаг сетки имеет порядок 1/N, тогда как соседние дроби со знаменателями меньше N могут отличаться на порядок 1/N²; например, 1/(N−1) и 1/(N−2). 6: для N=pq знание φ(N)=(p−1)(q−1) даёт p+q=N+1−φ(N), после чего p и q находятся как корни квадратного уравнения; поэтому вычисление φ для такого N эквивалентно факторизации.

Лабораторная работа 3. Алгоритм Шора для N = 15

Цель — собрать схему поиска порядка для a = 7, N = 15 и восстановить r из измерений. Рабочий регистр — 4 кубита (числа 0–15); умножение на 7 по модулю 15 — перестановка, которую можно собрать вручную из SWAP и X (проверьте её действие на базисных состояниях — задание 1):

from qiskit import QuantumCircuit

def c_amod15(a, power):
    """Управляемое умножение на a^power mod 15 (a = 2, 4, 7, 8, 11, 13)."""
    U = QuantumCircuit(4)
    for _ in range(power):
        if a in [2, 13]:
            U.swap(2, 3); U.swap(1, 2); U.swap(0, 1)
        if a in [7, 8]:
            U.swap(0, 1); U.swap(1, 2); U.swap(2, 3)
        if a in [4, 11]:
            U.swap(1, 3); U.swap(0, 2)
        if a in [7, 11, 13]:
            for q in range(4):
                U.x(q)
    gate = U.to_gate()
    gate.name = f"{a}^{power} mod 15"
    return gate.control()

Задание 1. Убедитесь (на бумаге или симулятором без измерений), что схема для a = 7, power = 1 переводит |1⟩ → |7⟩ → |4⟩ → |13⟩ → |1⟩ при последовательном применении. Кодировка чисел — двоичная, кубит 0 — младший бит.

Задание 2. Соберите полную схему поиска порядка: счётный регистр из t = 8 кубитов (H на каждом), рабочий регистр из 4 кубитов, инициализированный в |1⟩ (X на младшем кубите), и управляемые c_amod15(7, 2**k) от k-го счётного кубита. Добавьте актуальный вентиль обратного QFT: from qiskit.circuit.library import QFTGate, затем qc.append(QFTGate(8).inverse(), range(8)). Измерьте счётный регистр. Импортируйте from qiskit import transpile, перед запуском на AerSimulator разложите составные вентили командой compiled = transpile(qc, sim) и передайте compiled в sim.run(..., shots=1024).

Задание 3. Постройте гистограмму исходов. Вы должны увидеть четыре пика: 0, 64, 128, 192. Объясните каждый через фазы s/4 из раздела 7.5.

Задание 4. Классическая постобработка: для каждого измеренного m восстановите знаменатель

from fractions import Fraction
from math import gcd

N, a = 15, 7
r = Fraction(m, 256).limit_denominator(N - 1).denominator
factors = None
if r % 2 == 0 and pow(a, r, N) == 1:
    b = pow(a, r // 2, N)
    if b not in (1, N - 1):
        p = gcd(b - 1, N)
        q = gcd(b + 1, N)
        if 1 < p < N and 1 < q < N and p * q == N:
            factors = tuple(sorted((p, q)))

Результат считается успешным, только если factors не равен None; иначе измерение не дало истинного периода и алгоритм нужно запустить заново. Подсчитайте по всей статистике запусков долю измерений, приводящих к успешной факторизации с первого раза, и сравните с теоретической 1/2 из раздела 7.5.

Задание 5*. Повторите всё для a = 11 (порядок 2). Почему здесь пиков только два и какова доля успеха? Согласуется ли результат с упражнением 1?

Задание 6* (обсуждение). Наша схема опирается на вручную скомпилированную перестановку «×7 mod 15». Опишите, какие обратимые сумматоры, сравнения, условные вычитания и очистка анцилл потребуются для общего N. Объясните, почему моделирование этого частного случая не демонстрирует возможность взлома RSA: при росте n быстро растут регистры, схема модульной арифметики и стоимость классического моделирования состояния.

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

1. P. Shor, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer," SIAM J. Comput. 26, 1997. arxiv.org/abs/quant-ph/9508027
2. L. Vandersypen et al., "Experimental Realization of Shor's Quantum Factoring Algorithm Using Nuclear Magnetic Resonance," Nature 414, 2001. doi.org/10.1038/414883a
3. F. Boudot et al., "Comparing the Difficulty of Factorization and Discrete Logarithm: A 240-digit Experiment," CRYPTO 2020. arxiv.org/abs/2006.06197
4. M. Nielsen, I. Chuang, "Quantum Computation and Quantum Information," гл. 5.3–5.4, прил. 4. Cambridge University Press, 2010.
5. C. Gidney, M. Ekerå, "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits," Quantum 5, 2021. arxiv.org/abs/1905.09749
6. C. Gidney, "How to factor 2048 bit RSA integers with less than a million noisy qubits," 2025. arxiv.org/abs/2505.15917
7. M. Cain et al., "Shor's algorithm is possible with as few as 10,000 reconfigurable atomic qubits," препринт, 2026. arxiv.org/abs/2603.28627
8. IBM Quantum Documentation: QFTGate.

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