Безопасность в современном интернет-обществе защищена системами криптографии с открытым ключом, такими как шифрование RSA. Эти криптографические методы основаны на математической трудности: «факторизация огромных чисел занимает астрономическое время на современных (классических) компьютерах».

Однако квантовые компьютеры обладают потенциалом в корне изменить эту предпосылку. В частности, алгоритм Шора (Shor’s Algorithm), открытый Питером Шором в 1994 году, математически доказал, что если квантовые компьютеры будут реализованы на практике, шифрование RSA можно будет взломать за разумное время.

В этой статье мы подробно, в объеме около 20 000 символов, рассмотрим базовые механизмы вычислений на квантовых компьютерах, почему алгоритм Шора может быстро выполнять факторизацию, стоящую за ним математику и примеры реализации с использованием программирования (Python/Qiskit).

1. Что такое квантовый компьютер? Отличия от классического компьютера

ПК и смартфоны, которыми мы пользуемся каждый день, называются классическими компьютерами. Классические компьютеры обрабатывают информацию как биты (bit), которые принимают значения «0» или «1».

С другой стороны, квантовые компьютеры используют квантовые биты (кубиты) в качестве наименьшей единицы информации. Используя странные свойства квантовой механики, они выполняют вычисления с совершенно иным подходом, нежели традиционные компьютеры. В основе этого лежат «Суперпозиция», «Квантовая запутанность» (Entanglement) и «Квантовая интерференция» (Interference).

1.1 Суперпозиция (Superposition)

В то время как классический бит может находиться только в одном из состояний, «0» или «1», квантовый бит может принимать оба состояния «0» и «1» одновременно. Это называется суперпозицией.

Математически квантовое состояние \(|\psi\rangle\) выражается как линейная комбинация базисных состояний \(|0\rangle\) и \(|1\rangle\) следующим образом:

Здесь \(\alpha\) и \(\beta\) — комплексные числа, называемые амплитудами вероятности. Когда квантовый бит наблюдается (измеряется), его состояние коллапсирует (редукция волнового пакета) в \(|0\rangle\) или \(|1\rangle\), и вероятности получения каждого из них составляют \(|\alpha|^2\) и \(|\beta|^2\) соответственно. Поскольку сумма вероятностей должна равняться 1, выполняется следующее условие нормировки:

Благодаря этому свойству, \(n\) квантовых битов могут одновременно представлять суперпозицию из \(2^n\) состояний. Это является основой квантовых параллельных вычислений.

1.2 Квантовая запутанность (Entanglement)

Явление, при котором несколько квантовых битов сильно связаны друг с другом, и определение состояния одного мгновенно определяет состояние другого, независимо от пространственного расстояния между ними, называется квантовой запутанностью (энтанглментом).

Например, рассмотрим следующее состояние Белла (Bell state):

В этом состоянии, если первый кубит измерен и получено «0», то второй кубит обязательно будет «0». И наоборот, если получено «1», то второй также будет «1». Используя эту сильную корреляцию, квантовые компьютеры могут эффективно выполнять сложные вычисления.

1.3 Квантовая интерференция (Interference)

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

2. Квантовые вентили и квантовые цепи

То, что соответствует логическим вентилям (AND, OR, NOT и т.д.) в классических компьютерах, в квантовых компьютерах называется квантовыми вентилями. Квантовые вентили математически представляются как операции унитарных матриц над вектором квантового состояния.

2.1 Основные однокубитные вентили

Вентиль X (Вентиль Паули-X)

Соответствует классическому вентилю NOT. Он инвертирует \(|0\rangle\) в \(|1\rangle\), а \(|1\rangle\) в \(|0\rangle\).

Вентиль Z (Вентиль Паули-Z)

Инвертирует только фазу \(|1\rangle\) (умножает на \(-1\)). Инверсия фазы крайне важна для квантовой интерференции.

Вентиль H (Вентиль Адамара)

Один из самых важных вентилей, создающий состояние суперпозиции из базисного состояния.

Получается \(H|0\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)\), и при измерении вероятности получить 0 или 1 составляют по 50%.

2.2 Многокубитные вентили

Вентиль CNOT (Контролируемое НЕ)

Вентиль для двух кубитов, который применяет вентиль X (инверсию) к целевому кубиту только тогда, когда управляющий кубит равен «1». Незаменим для создания квантовой запутанности.

  graph LR
    q0["q0 (Управляющий)"] --- C(("●"))
    C --- q0_out["q0_out"]
    q1["q1 (Целевой)"] --- T(("⊕"))
    T --- q1_out["q1_out"]
    C -.- T

3. Основы криптографии и шифрование RSA

Чтобы понять влияние алгоритма Шора, необходимо знать, как работает шифрование RSA, которое в настоящее время является основным методом криптографии с открытым ключом.

3.1 Как работает шифрование RSA

Шифрование RSA использует сложность разложения на простые множители (факторизации). Берутся два огромных простых числа \(p\) и \(q\), и вычисляется их произведение \(N = p \times q\).

1. Умножить \(p\) и \(q\), чтобы получить \(N\), легко.
2. Однако найти исходные \(p\) и \(q\) из \(N\) (факторизовать) очень сложно.

Эта асимметрия является ключом к шифрованию. \(N\) широко публикуется как открытый ключ и используется для шифрования. С другой стороны, информация о \(p\) и \(q\) строго хранится как закрытый ключ и используется для расшифровки.

3.2 Насколько это сложно?

Даже при использовании современных суперкомпьютеров факторизация \(N\) длиной в несколько тысяч бит (например, RSA-2048) займет больше времени, чем возраст Вселенной. Даже при использовании наиболее эффективного классического алгоритма, «Общего метода решета числового поля» (GNFS), вычислительная сложность возрастает экспоненциально (точнее, субэкспоненциально).

※ \(b\) — количество цифр (количество бит)

Здесь на сцену выходит алгоритм Шора. Алгоритм Шора кардинально сокращает эту вычислительную сложность до полиномиального времени \(O(b^3)\).

4. Обзор алгоритма Шора

Алгоритм Шора решает проблему факторизации путем её преобразования в другую математическую задачу — «Задачу нахождения периода (Period Finding Problem)».

Алгоритм в общих чертах делится на две части.

1. Часть, выполняемая на классическом компьютере (сведение, предварительная и постобработка)
2. Часть, выполняемая на квантовом компьютере (нахождение периода)

4.1 Классическая часть: Сведение факторизации к нахождению периода

Предположим, дано составное число \(N\), которое нужно факторизовать. (Например: \(N = 15\))

Шаг 1: Выберем случайное целое число \(a\), взаимно простое с \(N\) (наибольший общий делитель равен 1) (\(1 < a < N\)). Если наибольший общий делитель \(\gcd(a, N) > 1\), то множитель уже найден, и процесс завершается. (Легко находится с помощью алгоритма Евклида).

Шаг 2: Рассмотрим следующую функцию модульной арифметики \(f(x)\):

Математически известно, что если подставлять \(x = 0, 1, 2, 3, \dots\) в эту функцию \(f(x)\), значения будут повторяться с определенным периодом \(r\) (Теорема Эйлера). То есть, существует минимальное положительное целое число \(r\) (период), при котором \(f(x) = f(x + r)\).

Например, для \(N = 15, a = 7\):

• \(7^0 \pmod{15} = 1\)
• \(7^1 \pmod{15} = 7\)
• \(7^2 \pmod{15} = 4\)
• \(7^3 \pmod{15} = 13\)
• \(7^4 \pmod{15} = 1\) (Отсюда начинается цикл)

Мы видим, что период \(r = 4\).

Шаг 3: Если найденный период \(r\) является четным и \(a^{r/2} \not\equiv -1 \pmod N\), то множители можно найти следующим образом:

В предыдущем примере (\(N=15, a=7, r=4\)): \(a^{r/2} = 7^{4/2} = 7^2 = 49\) \(49 + 1 = 50\), \(\gcd(50, 15) = 5\) \(49 - 1 = 48\), \(\gcd(48, 15) = 3\)

Великолепно, мы нашли множители числа \(15\): \(5\) и \(3\)!

4.2 Проблема: Сложность классического нахождения периода \(r\)

Мы поняли, что если известен период \(r\), можно провести факторизацию. Однако, если \(N\) очень велико, последовательное вычисление \(f(x)\) на классическом компьютере для поиска периода \(r\) всё равно займет экспоненциальное время.

Поэтому только эта часть — «поиск периода \(r\)» — делегируется квантовому компьютеру. Используя квантовые параллельные вычисления, \(f(x)\) для всех \(x\) вычисляется одновременно, и из этого периода \(r\) извлекается мгновенно (за полиномиальное время).

5. Квантовая часть: Квантовое преобразование Фурье и извлечение периода

Квантовая вычислительная часть алгоритма Шора проходит по следующим шагам.

  sequenceDiagram
    participant Q_Reg1 as "Регистр 1 (x)"
    participant Q_Reg2 as "Регистр 2 (f("x"))"
    
    Note over Q_Reg1,Q_Reg2: "1. Инициализация: Все биты в |0>"
    Q_Reg1->>Q_Reg1: "2. Преобразование Адамара (H⊗n) <br/>Создание суперпозиции всех состояний"
    Q_Reg1->>Q_Reg2: "3. Квантовое модульное возведение в степень <br/> |x>|0> → |x>|a^x mod N>"
    Note over Q_Reg2: "4. (Концептуально) Наблюдение 2-го регистра<br/>Коллапс 1-го регистра в периодическую суперпозицию"
    Q_Reg1->>Q_Reg1: "5. Квантовое преобразование Фурье (QFT)<br/>Извлечение периода через интерференцию"
    Note over Q_Reg1: "6. Измерение<br/>Получение информации о периоде (фаза)"

5.1 Оценка функции с помощью квантовых параллельных вычислений

Сначала подготавливаются два регистра с достаточным количеством кубитов (регистр 1 и регистр 2), и все они инициализируются в \(|0\rangle\). К первому регистру применяется вентиль Адамара, создавая равномерную суперпозицию всех возможных значений \(x\) (от \(0\) до \(Q-1\)).

Затем, используя квантовую цепь модульного возведения в степень, вычисляется \(f(x) = a^x \pmod N\), и результат записывается во второй регистр.

На этом этапе результаты \(f(x)\) для всех \(x\) вычислены одновременно как квантовая суперпозиция. Однако, если выполнить измерение прямо сейчас, мы получим только один случайный \(x\) и соответствующий ему \(f(x)\), а период \(r\) останется неизвестным.

5.2 Извлечение периодического состояния и квантовая интерференция

Чтобы выявить период \(r\), к первому регистру применяется чрезвычайно важная операция — Квантовое преобразование Фурье (Quantum Fourier Transform: QFT).

QFT — это квантовая версия классического дискретного преобразования Фурье (DFT). Оно преобразует периодичность данных в пики в частотной области. Для вектора состояния \(|\psi\rangle = \sum_{j} x_j |j\rangle\), QFT действует следующим образом:

Состояние первого регистра связано с состоянием второго регистра (например, \(f(x_0)\)), поэтому оно представляет собой суперпозицию с дискретными значениями с определенным периодом. При применении QFT к этому состоянию происходит квантовая интерференция.

• Состояния (амплитуды вероятности), связанные с правильным периодом \(r\), усиливаются
• Для остальных состояний фазы разбросаны, и они гасят друг друга (компенсируются).

В результате при измерении с высокой вероятностью получается значение \(k\), для которого выполняется \(k \approx Q \cdot \frac{c}{r}\) (где \(c\) — целое число).

5.3 Классическая постобработка: Разложение в непрерывную дробь

Как только результат измерения \(k\) получен от квантового компьютера, снова наступает очередь классического компьютера. У нас есть соотношение \(k / Q \approx c / r\). \(c\) и \(r\) — взаимно простые целые числа.

Используя известную десятичную дробь \(k / Q\) и классический алгоритм, называемый разложением в цепную (непрерывную) дробь (Continued Fraction Expansion), мы преобразуем ее в приближенную дробь \(c / r\), наконец, определяя знаменатель как период \(r\).

После этого, следуя процедуре, описанной в разделе 4.1, вычисляется наибольший общий делитель, и мы блестяще получаем простые множители числа \(N\).

6. Пример реализации алгоритма Шора с использованием Qiskit

Здесь представлен пример реализации алгоритма Шора для факторизации очень маленького числа \(N = 15\), используя Qiskit, фреймворк квантового программирования с открытым исходным кодом от IBM.

(※ Практическая факторизация гигантских чисел требует огромного количества кубитов и исправления ошибок, поэтому на текущих симуляторах и мелкомасштабном квантовом оборудовании мы ограничены демонстрациями с числами вроде \(15\) или \(21\))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

import numpy as np
from qiskit import QuantumCircuit, transpile
from qiskit.visualization import plot_histogram
from qiskit_aer import AerSimulator
import math
from math import gcd

# --- 1. Определение квантовой цепи модульного возведения в степень (a=7, N=15) ---
def c_amod15(a, power):
    """Цепь a^power mod 15, функционирующая как контролируемый вентиль U"""
    U = QuantumCircuit(4)        
    for _iteration 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)
    U = U.to_gate()
    U.name = f"{a}^{power} mod 15"
    c_U = U.control()
    return c_U

# --- 2. Определение обратного квантового преобразования Фурье (QFT_dagger) ---
def qft_dagger(n):
    """Цепь, выполняющая обратное квантовое преобразование Фурье для n кубитов"""
    qc = QuantumCircuit(n)
    for qubit in range(n//2):
        qc.swap(qubit, n-qubit-1)
    for j in range(n):
        for m in range(j):
            qc.cp(-np.pi/float(2**(j-m)), m, j)
        qc.h(j)
    qc.name = "QFT_dagger"
    return qc

# --- 3. Построение основной части алгоритма Шора ---
n_count = 8  # Количество кубитов измерительного регистра (Регистр 1)
a = 7        # Число, взаимно простое с N=15

# Регистр 1 (8qubit) + Регистр 2 (4qubit) + Классический регистр (8bit)
qc = QuantumCircuit(n_count + 4, n_count)

# Перевод 1-го регистра в состояние суперпозиции с помощью вентилей H
for q in range(n_count):
    qc.h(q)

# Установка начального состояния 2-го регистра в |1> (применение вентиля x к младшему биту)
qc.x(n_count)

# Применение контролируемых вентилей модульного возведения в степень
for q in range(n_count):
    qc.append(c_amod15(a, 2**q), 
             [q] + [i+n_count for i in range(4)])

# Применение обратного QFT к 1-му регистру
qc.append(qft_dagger(n_count).to_instruction(), range(n_count))

# Измерение 1-го регистра
qc.measure(range(n_count), range(n_count))

# --- 4. Запуск на симуляторе ---
simulator = AerSimulator()
compiled_circuit = transpile(qc, simulator)
job = simulator.run(compiled_circuit, shots=1024)
results = job.result()
counts = results.get_counts()

print("Результаты измерений (бинарный вид: количество наблюдений):")
print(counts)

# --- 5. Классическая постобработка (Определение периода r и вычисление простых множителей) ---
# Логика анализа наиболее вероятных результатов измерений (упрощенная версия)
measured_phases = []
for output in counts:
    decimal = int(output, 2)
    phase = decimal / (2**n_count)
    measured_phases.append(phase)

print(f"\nПредполагаемые фазы (phase): {measured_phases[:4]} ...")
# Далее следует процесс нахождения знаменателя r (периода) из фазы с помощью разложения в цепную дробь...

При выполнении вышеуказанного кода квантовый симулятор с высокой вероятностью выведет состояния, такие как 00000000, 01000000, 10000000, 11000000 (0, 64, 128, 192 в десятичной системе). Если разделить их на \(2^8 = 256\), то фазы составят \(0\), \(0.25\), \(0.5\), \(0.75\). Выраженные в виде дробей, они будут равны \(0/4\), \(1/4\), \(2/4\), \(3/4\), и мы видим, что знаменатель 4 был выведен квантовыми вычислениями как период \(r\). Как только известен период \(r=4\), из \(\gcd(7^{4/2} \pm 1, 15)\), как описано ранее, извлекаются простые множители \(3\) и \(5\).

7. Почему шифрование RSA находится под угрозой?

Вычислительная сложность факторизации на классическом компьютере возрастает экспоненциально с увеличением количества цифр. Например, факторизация числа из 100 цифр занимает несколько секунд, 200 цифр — несколько лет, а для RSA-2048 (около 617 цифр) оценивается в время, превышающее возраст Вселенной.

Однако при использовании алгоритма Шора количество необходимых шагов вычислений (количество вентилей) возрастает лишь в полиномиальном порядке \(O(b^3)\) от количества цифр \(b\). Это означает, что даже RSA-2048 можно будет взломать за время от нескольких часов до нескольких дней, если будет идеальный квантовый компьютер.

Угроза “Store Now, Decrypt Later”

Опасно думать, что “мы в безопасности, потому что высокопроизводительные квантовые компьютеры еще не созданы”. Существует реалистичный сценарий атаки, при котором злонамеренные третьи стороны или государственные органы прямо сейчас записывают и сохраняют зашифрованные конфиденциальные данные (финансовую информацию, государственные секреты и т.д.) (“Store Now”), чтобы расшифровать их через 10–20 лет (“Decrypt Later”), в тот момент, когда высокопроизводительные квантовые компьютеры будут завершены. Поэтому необходимо обновить методы криптографии, не дожидаясь появления квантовых компьютеров.

8. Барьеры на пути реализации квантовых компьютеров: Шум и исправление ошибок

Алгоритм Шора математически идеален, но на пути к его физической реализации стоят высокие барьеры. Текущее квантовое оборудование называется устройствами NISQ (Noisy Intermediate-Scale Quantum: шумные квантовые устройства промежуточного масштаба), и их слабость заключается в высокой уязвимости к шуму (возмущениям из внешней среды и ошибкам в операциях вентилей).

Квантовые состояния чрезвычайно чувствительны и могут подвергаться декогеренции (разрушению квантового состояния) из-за незначительного тепла или электромагнитных волн. Чтобы взломать RSA-2048, необходимо выполнить сотни миллионов операций с вентилями без ошибок на тысячах “логических кубитов”.

Для решения этой проблемы исследуется квантовое исправление ошибок (Quantum Error Correction). Это технология связывания нескольких “физических кубитов” для формирования одного “логического кубита” с целью обнаружения и исправления ошибок, возникающих во время вычислений. Однако считается, что для создания одного логического кубита требуется от 1000 до 10 000 физических кубитов, и ожидается, что для создания крупномасштабного отказоустойчивого квантового компьютера (FTQC: Fault-Tolerant Quantum Computer) класса десятков миллионов физических кубитов потребуется еще от 10 лет до нескольких десятилетий прорывов.

9. Криптографические технологии следующего поколения: Постквантовая криптография (PQC)

Чтобы противостоять угрозе алгоритма Шора, Национальный институт стандартов и технологий США (NIST) и другие организации по всему миру продвигают стандартизацию Постквантовой криптографии (Post-Quantum Cryptography: PQC), новых методов шифрования, которые невозможно взломать даже с помощью квантовых компьютеров.

PQC не использует квантовые технологии; она может быть выполнена на классических компьютерах, но основана на новых математических проблемах, которые невозможно эффективно решить с помощью квантовых алгоритмов (к которым алгоритм Шора неприменим).

Основные подходы к PQC:

• Криптография на решетках (Lattice-based cryptography): Использует сложность таких проблем, как задача о кратчайшем векторе (SVP) в многомерных пространствах. (Например: Kyber, Dilithium)
• Криптография на основе кодов (Code-based cryptography): Использует сложность проблемы декодирования кодов с исправлением ошибок.
• Многомерная криптография (Multivariate cryptography): Использует сложность решения систем полиномиальных уравнений второй степени со многими переменными.
• Сигнатуры на основе хешей (Hash-based signatures): Методы цифровой подписи, зависящие только от безопасности криптографических хеш-функций.

В настоящее время мировая ИТ-инфраструктура переживает исторический переходный период (миграцию) от существующей криптографии RSA и криптографии на эллиптических кривых к этим стандартам PQC.

10. Заключение

В этой статье мы подробно рассмотрели основы квантовых компьютеров, механизм факторизации с помощью алгоритма Шора и перспективы будущих криптографических технологий.

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

Прекрасный механизм, искусно управляющий квантовой интерференцией и выделяющий только “правильный ответ” из экспоненциального пространства поиска, будет служить важным ориентиром при проектировании квантовых алгоритмов, которые в будущем будут применяться в различных областях (разработка лекарств, расчеты материалов, задачи оптимизации и т.д.). Готовясь к грядущей квантовой эре, мы являемся свидетелями фундаментальных технологических изменений.