Exponential Speedup

Shor's Algorithm

Factoring & Cryptography

Shor's algorithm factors integers in polynomial time, offering an exponential speedup over the best known classical algorithms. It poses a fundamental threat to RSA encryption and remains the most celebrated example of quantum computational advantage.

The Factoring Problem

Given a large integer N that is the product of two primes, finding those prime factors is believed to be intractable for classical computers. The best known classical algorithm, the General Number Field Sieve, has a sub-exponential complexity that grows rapidly with the number of digits.

This hardness assumption underpins modern public-key cryptography. RSA, Diffie-Hellman, and elliptic-curve cryptography all rely on the difficulty of factoring or related problems. Shor's algorithm breaks this assumption by solving factoring efficiently on a quantum computer.

•Classical Complexity: Sub-exponential: O(exp((64/9)^(1/3) · (ln N)^(1/3) · (ln ln N)^(2/3))).
•Quantum Complexity: Polynomial: O((log N)^3) using Shor's algorithm on a fault-tolerant quantum computer.
•Impact: A sufficiently large fault-tolerant quantum computer could break 2048-bit RSA keys in hours instead of billions of years.

Period Finding

Shor's algorithm reduces factoring to an order-finding (period-finding) problem. For a random integer a coprime to N, the function f(x) = a^x mod N is periodic. If we can find the period r, we can factor N using classical number theory.

The quantum speedup comes from Quantum Phase Estimation (QPE) applied to a modular exponentiation circuit. QPE extracts the period from a superposition of states in polynomial time — something no classical algorithm can do efficiently.

f(x) = a^x \bmod N

Modular Exponentiation

a^r \equiv 1 \pmod{N}

Period Relation

U|y\rangle = |a \cdot y \bmod N\rangle

QPE Unitary

U|u_s\rangle = e^{2\pi i s / r} |u_s\rangle

Eigenvalue Structure

\gcd(a^{r/2} \pm 1, N)

Factor Recovery

•Step 1: Classical Reduction: Pick random a < N, check gcd(a, N). If not coprime, you already found a factor.
•Step 2: Quantum Period Finding: Use QPE on the unitary U|y⟩ = |a·y mod N⟩ to find the period r of a^x mod N.
•Step 3: Classical Post-Processing: If r is even and a^(r/2) ≠ -1 mod N, compute gcd(a^(r/2) ± 1, N) to get factors.

Current Limitations

Shor's algorithm requires a fully fault-tolerant quantum computer with thousands of logical qubits and deep circuits. Current NISQ devices can only factor trivially small numbers (e.g., 15 = 3 × 5), which are easily handled by classical computers.

Researchers are actively working on optimizing the algorithm for smaller qubit counts and developing post-quantum cryptographic standards (like lattice-based cryptography) to prepare for the post-Shor era.

•Qubit Requirements: Approximately 2n logical qubits to factor an n-bit integer, plus significant overhead for error correction.
•Circuit Depth: Modular exponentiation requires millions of Toffoli gates for cryptographically relevant key sizes.
•Error Correction: Physical error rates must be below ~10^-4 with efficient surface code implementations.

Code in Action

Runnable implementations you can copy and experiment with.

Quantum Phase Estimation Setup

A simplified QPE circuit that forms the core of Shor's period-finding subroutine. This example uses 3 counting qubits to estimate a phase.

shor_qpe.py

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator
import numpy as np

# QPE with 3 counting qubits for a toy unitary
n_count = 3
qc = QuantumCircuit(n_count + 1, n_count)

# Initialize eigenstate |1> on auxiliary qubit
qc.x(n_count)

# Create superposition on counting register
qc.h(range(n_count))

# Controlled-U operations (toy: rotation by pi/4)
angle = np.pi / 4
for i in range(n_count):
    qc.cp(angle * (2 ** i), i, n_count)

# Inverse QFT on counting register
for j in range(n_count // 2):
    qc.swap(j, n_count - j - 1)
for j in range(n_count):
    for m in range(j):
        qc.cp(-np.pi / (2 ** (j - m)), m, j)
    qc.h(j)

# Measure
qc.measure(range(n_count), range(n_count))

simulator = AerSimulator()
job = simulator.run(qc, shots=2048)
print(job.result().get_counts())

Toy QPE with PennyLane

A PennyLane QPE circuit that estimates the phase of a toy unitary, forming the core of Shor's period-finding subroutine.

shor_qpe_pennylane.py

import pennylane as qml
import numpy as np

n_count = 3
dev = qml.device('default.qubit', wires=n_count + 1)

def c_u_power(k):
    angle = np.pi / 4 * (2 ** k)
    qml.ControlledPhaseShift(angle, wires=[k, n_count])

@qml.qnode(dev)
def qpe_circuit():
    qml.PauliX(wires=n_count)
    for i in range(n_count):
        qml.Hadamard(wires=i)
    for i in range(n_count):
        c_u_power(i)
    qml.adjoint(qml.QFT)(wires=range(n_count))
    return qml.sample(wires=range(n_count))

samples = qpe_circuit()
print("QPE samples:", samples)

Explore next

Quantum Simulation

Explore next

Error-Correcting Algorithms

from qiskit import QuantumCircuit from qiskit_aer import AerSimulator import numpy as np # QPE with 3 counting qubits for a toy unitary n_count = 3 qc = QuantumCircuit(n_count + 1, n_count) # Initialize eigenstate |1> on auxiliary qubit qc.x(n_count) # Create superposition on counting register qc.h(range(n_count)) # Controlled-U operations (toy: rotation by pi/4) angle = np.pi / 4 for i in range(n_count): qc.cp(angle * (2 ** i), i, n_count) # Inverse QFT on counting register for j in range(n_count // 2): qc.swap(j, n_count - j - 1) for j in range(n_count): for m in range(j): qc.cp(-np.pi / (2 ** (j - m)), m, j) qc.h(j) # Measure qc.measure(range(n_count), range(n_count)) simulator = AerSimulator() job = simulator.run(qc, shots=2048) print(job.result().get_counts())

import pennylane as qml import numpy as np n_count = 3 dev = qml.device('default.qubit', wires=n_count + 1) def c_u_power(k): angle = np.pi / 4 * (2 ** k) qml.ControlledPhaseShift(angle, wires=[k, n_count]) @qml.qnode(dev) def qpe_circuit(): qml.PauliX(wires=n_count) for i in range(n_count): qml.Hadamard(wires=i) for i in range(n_count): c_u_power(i) qml.adjoint(qml.QFT)(wires=range(n_count)) return qml.sample(wires=range(n_count)) samples = qpe_circuit() print("QPE samples:", samples)