Shor's Algorithm

Overview

Shor's algorithm (1994) factors an integer in time, compared to the best-known classical algorithm (general number field sieve) which runs in sub-exponential time .

The algorithm combines classical number theory with the quantum Fourier transform to find the period of a modular exponential function.

Reduction to Period Finding

Shor's insight is that factoring reduces to period finding. Choose a random with . Define:

This function is periodic with some period (the order of modulo ). If is even, then:

With probability , gives a non-trivial factor of .

Quantum Period Finding

The quantum circuit for period finding:

1. Prepare two registers: with and
2. Apply Hadamard to the first register:
3. Compute into the second register
4. Apply the Quantum Fourier Transform to the first register
5. Measure the first register to obtain a value close to for some integer
6. Use the continued fractions algorithm classically to extract

Modular Exponentiation

The quantum circuit for computing uses gates via repeated squaring:

Each modular multiplication can be implemented using gates with quantum arithmetic circuits.

This is the bottleneck of Shor's algorithm — it requires quantum gates, which is why factoring large numbers requires fault-tolerant quantum computers.

Complexity Analysis

The overall complexity of Shor's algorithm:

Total quantum gates: .

For a 2048-bit RSA key, this requires approximately quantum gates — well beyond current hardware but feasible with future fault-tolerant devices.

Python: Classical Order Finding

import numpy as np
from math import gcd

def find_order(a, N):
    # Classical order finding: find smallest r such that a^r = 1 (mod N).
    if gcd(a, N) != 1:
        return None
    r = 1
    current = a % N
    while current != 1:
        current = (current * a) % N
        r += 1
        if r > N:
            return None
    return r

def shor_factor(N):
    # Attempt to factor N using Shor's algorithm (classical simulation).
    from random import randint
    a = randint(2, N - 1)
    if gcd(a, N) != 1:
        return gcd(a, N), N // gcd(a, N)
    r = find_order(a, N)
    if r is None or r % 2 == 1:
        return None
    x = pow(a, r // 2, N)
    if x == N - 1:
        return None
    p = gcd(x + 1, N)
    q = gcd(x - 1, N)
    if p * q == N and p != 1 and q != 1:
        return p, q
    return None

result = shor_factor(21)
print(f"Factors of 21: {result}")

This demonstrates the classical post-processing of Shor's algorithm.

Quantum Fourier Transform in Shor's

The QFT on qubits maps:

For Shor's algorithm, the QFT extracts the period from the superposition created by modular exponentiation. The QFT circuit uses gates: Hadamard gates and controlled phase rotations.

The inverse QFT (used in QPE) has the conjugate transformation and is used to decode the phase information.

Practical Considerations

For real-world factoring with Shor's algorithm:

1. RSA-2048: requires ~4000 logical qubits, ~10^{10} T-gates
2. Error correction overhead: ~1000 physical qubits per logical qubit
3. Total: ~4 million physical qubits
4. Timeline: estimated 10-20 years for fault-tolerant hardware

Post-quantum migration should begin now to protect data with long-term sensitivity.