Алгоритм Шора

Алгоритм Шора — это квантовый алгоритм факторизации целых чисел (разложения на простые множители), разработанный американским математиком Питером Шором в 1994 году. Алгоритм позволяет за полиномиальное время (относительно количества цифр в числе) находить простые делители большого числа, что экспоненциально быстрее лучших известных классических алгоритмов. Принципиальное значение алгоритма Шора заключается в том, что он демонстрирует потенциальную возможность квантовых компьютеров решать задачи, считающиеся практически неразрешимыми для классических вычислительных систем, в частности — взламывать широко распространённые криптографические системы с открытым ключом, такие как RSA.

История

Идея использования квантовых вычислений для решения задач факторизации восходит к работам Ричарда Фейнмана (1982) и Дэвида Дойча (1985), которые предположили, что квантовые компьютеры могут быть эффективнее классических для определённых классов задач. В 1994 году Питер Шор, работавший в Bell Labs, опубликовал статью «Algorithms for quantum computation: discrete logarithms and factoring», в которой представил два алгоритма: один для факторизации целых чисел, другой для вычисления дискретных логарифмов. Оба алгоритма используют квантовое преобразование Фурье (QFT) и дают экспоненциальное ускорение по сравнению с лучшими классическими алгоритмами. До работы Шора квантовые алгоритмы существовали лишь для узких задач (например, алгоритм Дойча — Йожи), не имевших практического применения. Публикация алгоритма Шора стала катализатором развития квантовых вычислений, привлекла значительное финансирование и стимулировала создание первых квантовых процессоров.

Математические основы

Факторизация как задача

Факторизация целого числа N состоит в нахождении его нетривиальных делителей (простых множителей). Для чисел длиной n бит (где n ≈ log₂N) лучшие классические алгоритмы — общее решето числового поля (GNFS) — имеют субэкспоненциальную сложность порядка O(exp((64/9 n)^(1/3) (log n)^(2/3))). Для числа с 2048 битами (типичный размер модуля RSA) это практически невыполнимо на современных компьютерах. Алгоритм Шора решает ту же задачу за O((log N)³) квантовых операций (полиномиальная сложность).

Сведение к задаче о порядке

Алгоритм Шора использует сведение задачи факторизации к задаче нахождения порядка (периода) функции. Пусть N — составное число, которое требуется факторизовать. Выбирается случайное число a, взаимно простое с N (т.е. gcd(a, N) = 1). Рассматривается функция f(x) = aˣ mod N. Эта функция является периодической: существует наименьшее положительное r (называемое порядком a по модулю N) такое, что aʳ ≡ 1 (mod N). Если r найден, то с высокой вероятностью можно получить делители N: если r чётно, то (a^(r/2) − 1) и (a^(r/2) + 1) имеют общие делители с N (хотя иногда они тривиальны). Ключевой шаг — эффективное нахождение r с помощью квантового компьютера.

Описание алгоритма

Алгоритм Шора состоит из двух частей: классической (предварительные вычисления и постобработка) и квантовой (нахождение периода).

Классическая часть

1. Если N чётно, вернуть 2 как делитель.
2. Если N = pᵏ для простого p и целого k > 1, то p — делитель (проверяется за полиномиальное время).
3. Выбрать случайное a из интервала [2, N−1]. Вычислить gcd(a, N). Если gcd > 1, то найден нетривиальный делитель.
4. Иначе применить квантовую подпрограмму для нахождения порядка r числа a по модулю N.
5. Если r нечётно или a^(r/2) ≡ −1 (mod N), то вернуться к шагу 3 (выбрать другое a). Иначе делители: gcd(a^(r/2) − 1, N) и gcd(a^(r/2) + 1, N).

Квантовая подпрограмма

Квантовая часть алгоритма использует два регистра: первый (счётчик) из q кубитов, второй (функция) — из n кубитов (где n ≈ log₂N). Количество кубитов q выбирается так, чтобы 2^q > N².

1. Инициализация: Все кубиты первого регистра переводятся в состояние суперпозиции (равномерная суперпозиция всех состояний от 0 до 2^q−1). Второй регистр инициализируется в состояние |0⟩.
2. Вычисление функции: Применяется квантовое преобразование, реализующее операцию U_f: |x⟩|0⟩ → |x⟩|aˣ mod N⟩. Это выполняется с помощью квантовых схем модульного возведения в степень (экспоненцирование). В результате получается состояние:

(1/√(2^q)) Σ_{x=0}^{2^q−1} |x⟩ |aˣ mod N⟩.

1. Квантовое преобразование Фурье (QFT): К первому регистру применяется квантовое преобразование Фурье. Это преобразование переводит состояние в суперпозицию, в которой амплитуды сосредоточены около значений, кратных 2^q / r.
2. Измерение: Измеряется первый регистр. Результат y с высокой вероятностью близок к целому кратному 2^q / r.
3. Классическая обработка: По измеренному y с помощью цепной дроби восстанавливается r (знаменатель дроби y / 2^q даёт r или его делитель). Процедура повторяется несколько раз для проверки.

Сложность и ресурсы

Квантовые ресурсы

Для факторизации числа N длиной n бит алгоритм Шора требует:

• Количество кубитов: O(n) (типично 2n + O(1) для первого регистра и n для второго).
• Количество квантовых вентилей: O(n³) (в основном за счёт модульного возведения в степень).
• Глубина схемы: O(n³) при использовании оптимизированных методов (например, рекурсивное возведение в степень).

Классические ресурсы

Классическая часть (выбор a, проверка gcd, цепные дроби) требует O(n²) операций, что пренебрежимо мало по сравнению с квантовой частью.

Практические реализации

Экспериментальные демонстрации

Первая экспериментальная реализация алгоритма Шора была выполнена в 2001 году группой из IBM Research (Айзек Чуанг и др.) на 7-кубитном квантовом процессоре на основе ядерного магнитного резонанса (ЯМР). Было разложено число 15 на множители 3 и 5. С тех пор алгоритм был реализован на различных платформах:

• 2007: Факторизация 15 на оптическом квантовом компьютере (University of Queensland).
• 2012: Факторизация 21 на ЯМР-компьютере (University of Waterloo).
• 2014: Факторизация 143 на квантовом компьютере с использованием метода адиабатических вычислений (D-Wave).
• 2019: Факторизация 35 на сверхпроводниковом процессоре Google Sycamore.

Все демонстрации ограничивались числами до нескольких десятков (максимум 21–35) из-за малого числа кубитов и высокого уровня ошибок.

Текущие ограничения

Для факторизации 2048-битного числа (типичный размер RSA) потребуется около 4000–6000 логических кубитов (с учётом коррекции ошибок — до 10⁷ физических кубитов). Современные квантовые процессоры (2024 год) имеют 50–1000 физических кубитов с высокой частотой ошибок, что недостаточно для практического применения алгоритма.

Криптографические последствия

Алгоритм Шора представляет прямую угрозу для криптосистем с открытым ключом, основанных на сложности факторизации (RSA) или дискретного логарифмирования (DSA, ECDSA, Diffie-Hellman). Если будет построен достаточно мощный квантовый компьютер, эти системы станут небезопасными. В ответ разрабатываются постквантовые криптографические алгоритмы (например, на основе решёток, кодов, хэшей), устойчивые к квантовым атакам. Национальный институт стандартов и технологий США (NIST) в 2024 году завершил отбор первых постквантовых стандартов.

Альтернативные подходы

Существуют варианты алгоритма Шора:

• Алгоритм Шора для дискретного логарифма — решает задачу нахождения x такого, что gˣ ≡ y (mod p), с той же сложностью.
• Алгоритм Шора для эллиптических кривых — адаптация для нахождения порядка точки на эллиптической кривой.
• Алгоритм Регева (2004) — квантовый алгоритм для факторизации с меньшим числом кубитов (O(n), но с большей глубиной схемы).

Критика и обсуждения

Некоторые исследователи отмечают, что алгоритм Шора не решает задачу факторизации в общем виде — он требует, чтобы N было нечётным и не являлось степенью простого числа. Однако эти ограничения легко обходятся предварительной классической проверкой. Основная критика связана с практической реализацией: квантовая коррекция ошибок требует огромного числа физических кубитов, а время выполнения (даже при идеальных условиях) может составлять часы для 2048-битного числа из-за накладных расходов на коррекцию.

Источники

• Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring. Proceedings 35th Annual Symposium on Foundations of Computer Science.
• Nielsen, M. A., & Chuang, I. L. (2010). Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press.
• Vandersypen, L. M. K., et al. (2001). Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance. Nature, 414(6866), 883–887.
• NIST (2024). Post-Quantum Cryptography: Selected Algorithms.
• Bernstein, D. J., & Lange, T. (2017). Post-quantum cryptography. Nature, 549(7671), 188–194.