Quantum Algorithms: Grover, Shor, and the Quantum Advantage

A classical computer searches an unsorted list of N items in O(N) time. Grover's quantum algorithm does it in O(√N). Shor's algorithm factors a number with exponential classical difficulty in polynomial time. These are not improvements — they are fundamentally different computational capabilities enabled by quantum superposition and interference.

1. The Quantum Circuit Model

A quantum computer operates on qubits — two-level quantum systems. Unlike classical bits (0 or 1), qubits can exist in arbitrary superpositions:

Qubit state: |ψ⟩ = α|0⟩ + β|1⟩ α, β ∈ ℂ (complex amplitudes) Normalisation: |α|² + |β|² = 1 Measurement: P(0) = |α|², P(1) = |β|² → collapses to |0⟩ or |1⟩ n-qubit system: State lives in ℂ^(2ⁿ) Hilbert space (2ⁿ amplitudes) Example: 3 qubits → 8 amplitudes: α₀₀₀|000⟩ + α₀₀₁|001⟩ + ... + α₁₁₁|111⟩ Key quantum gates: Hadamard: H = (1/√2) [[1,1],[1,−1]] (creates equal superposition) Pauli-X: X = [[0,1],[1,0]] (NOT gate) Phase: S = [[1,0],[0,i]] (π/2 phase shift) CNOT: flip target qubit iff control = |1⟩ (entanglement) Universality: {H, T, CNOT} is universal — any unitary can be approximated to arbitrary precision with these three gates.

2. Quantum Fourier Transform

The Quantum Fourier Transform (QFT) is the quantum analogue of the Discrete Fourier Transform — the workhorse underlying both Shor's algorithm and quantum phase estimation:

QFT on n qubits: |j⟩ → (1/√N) Σ_{k=0}^{N-1} e^{2πijk/N} |k⟩ N = 2ⁿ Classical DFT of N points: O(N log N) with FFT Quantum QFT of N = 2ⁿ amplitudes: O(n²) = O((log N)²) gates Circuit structure: Apply Hadamard to qubit 1 (highest order) Apply controlled phase rotation R_k = diag(1, e^{iπ/2^{k-1}}) gates Repeat for each qubit Reverse qubit order (SWAP gates) Total: n(n+1)/2 single-qubit gates + n/2 SWAP gates Why it's faster: QFT acts on 2ⁿ amplitudes simultaneously via quantum superposition. Classical FFT must explicitly compute all N outputs. QFT: O(n²) vs FFT: O(n·2ⁿ) — but QFT output cannot be directly read → must use QFT as subroutine, not standalone transformer.

3. Grover's Search Algorithm

Lov Grover (1996) devised an algorithm to find a marked item in an unsorted database of N items. Classically this requires O(N) queries on average. Grover achieves O(√N):

Grover's Algorithm: 1. Initialise: |ψ⟩ = H^\otimesn |0⟩ᵑ (equal superposition of all N states) 2. Repeat O(\sqrtN) times: a. Oracle: O|x⟩ = -|x⟩ if x matches, +|x⟩ otherwise (phase-flips the marked item's amplitude) b. Diffusion: 2|ψ⟩⟨ψ| - I ("inversion about the mean") (amplifies marked amplitude, reduces others) 3. Measure \to obtains marked item with probability \geq 1 - ε Geometric picture: State rotates by angle 2θ per iteration toward marked state, where sin θ = 1/\sqrtN. Optimal iterations: t = (π/4) \cdot \sqrtN N = 2²⁰ \approx 10⁶: classical avg 500,000 queries vs Grover ~785 queries N = 2⁵⁶ \approx 7\times10¹⁶: classical avg 10¹⁷ queries vs Grover ~2\times10⁸ queries Security implication: 128-bit symmetric key (AES-128): classical brute-force 2¹²⁸ queries Grover: 2⁶⁴ queries \to AES-128 security reduced to 64-bit with quantum NIST recommendation: use AES-256 to maintain 128-bit quantum security

4. Shor's Factoring Algorithm

Peter Shor (1994) showed that quantum computers can factor an n-digit integer N in O(n² log n log log n) gates — exponentially faster than the best known classical algorithm (general number field sieve, sub-exponential but super-polynomial):

Shor's Algorithm Overview: Problem: Factor N (RSA-2048 uses N with 617 decimal digits) Classical reduction (not quantum): 1. If N even → factor is 2. 2. Check if N = a^b for integers a, b. 3. Choose random a < N with gcd(a, N) = 1. 4. Find r = period of f(x) = aˣ mod N ← QUANTUM SUBROUTINE 5. If r is even and a^(r/2) ≢ −1 (mod N): Factors: gcd(a^(r/2) ± 1, N) Quantum period-finding subroutine: a. Create superposition of {|x⟩|f(x)⟩} for x = 0..2ⁿ−1 b. Measure second register → collapses to one value of f(x₀) = y c. First register: sum over all x with f(x) = y → periodic state d. Apply QFT → peaks at multiples of 2ⁿ/r e. Read r from measurement RSA implications: RSA-2048 security relies on classical hardness of factoring. A fault-tolerant quantum computer with ~4,000 "logical" qubits (requiring millions of physical qubits for error correction) could break RSA-2048 in hours. Post-quantum cryptography (NIST PQC, 2024 standards): CRYSTALS-Kyber (ML-KEM): lattice key encapsulation CRYSTALS-Dilithium (ML-DSA): lattice digital signatures FALCON: smaller signature size

Current status (2024-2025): IBM's Heron r2 processor has 156 qubits with improved connectivity. Google's Willow chip demonstrated exponential error reduction with surface code scaling. However, breaking RSA-2048 would require millions of error-corrected physical qubits — a goal that remains ~10-15 years out by current projections. The Q-Day concern is real but not imminent.

5. Variational Algorithms: VQE and QAOA

Variational quantum algorithms are hybrid quantum-classical approaches designed for near-term NISQ hardware — they tolerate moderate noise and require fewer qubits than fault-tolerant algorithms:

Variational Quantum Eigensolver (VQE): Goal: Find ground state energy E₀ of a molecular Hamiltonian H. Classical: exact diagonalisation scales as O(2^{2N}) for N orbitals. VQE: 1. Parameterised quantum circuit |ψ(θ)⟩ = U(θ)|0⟩ 2. Measure E(θ) = ⟨ψ(θ)|H|ψ(θ)⟩ on quantum hardware 3. Classical optimiser (gradient descent, COBYLA) → update θ 4. Repeat until converged → E₀ ≈ E(θ*) Variational principle: E(θ) ≥ E₀ for all θ Application: drug discovery (molecular energies), battery materials, nitrogen fixation catalyst design QAOA (Quantum Approximate Optimisation Algorithm): Goal: Approximate combinatorial optimisation (MaxCut, TSP, protein folding) p-layer QAOA: alternating problem Hamiltonian H_C and mixer H_B: |γ,β⟩ = e^{-iβ_p H_B} e^{-iγ_p H_C} ··· e^{-iβ₁H_B} e^{-iγ₁H_C} |+⟩^⊗n Classical optimise γ, β → maximise ⟨H_C⟩ MaxCut approximation ratio: p→∞ → exact; p=1 → proven > 0.6924 (Goemans-Williamson classical SDP achieves 0.878)

6. Quantum Complexity Classes

Complexity landscape: P = problems solvable classically in polynomial time NP = problems verifiable classically in polynomial time BPP = classical randomised polynomial time (practical classical limit) BQP = quantum polynomial time (with bounded error < 1/3) QMA = quantum NP (quantum analogue of NP) Known separations and containments: P \subseteq BPP \subseteq BQP \subseteq PSPACE P \subseteq NP; BPP \subseteq BQP NP and BQP: likely incomparable (neither is subset of the other) Factoring: Definitely in BQP (polynomial quantum). Likely not in P (no known polynomial classical algorithm). Not NP-complete (factoring is in NP \cap co-NP; NP-complete would imply collapse). Grover: Unstructured search: classically Ω(N) \to quantumly Θ(\sqrtN) Quadratic speedup. Cannot solve NP-complete problems in polynomial time. (Would require polynomial iterations \times polynomial circuit depth)

7. NISQ Era: Noise, Limits, and Near-Term Reality

Today's quantum computers are "Noisy Intermediate-Scale Quantum" (NISQ) devices — John Preskill's term for systems with 50-1000 qubits operating without full fault tolerance. Understanding their limits is essential for realistic expectations:

Decoherence: Qubits lose quantum information by interacting with the environment. T₁ (energy relaxation): 100-500 μs for IBM superconducting qubits. T₂ (dephasing): 50-300 μs. Circuit depth limited to ~100-1000 gates within coherence time.
Gate fidelities: Single-qubit: 99.9–99.99%. Two-qubit (CNOT): 99.0–99.9%. A 100-CNOT circuit has error amplification ~1−(0.99)¹⁰⁰ ≈ 63% — most outputs wrong.
Quantum error correction (QEC): Surface code requires ~1000 physical qubits per logical qubit at current error rates. A 1000-logical-qubit fault-tolerant computer likely needs 1-10M physical qubits. No current machine is fault-tolerant.
Quantum advantage timeline: Google's 2019 Sycamore "quantum supremacy" experiment (random circuit sampling) was disputed and the problem was later solved classically. Willow (2024) repeated with improved parameters. No unambiguous quantum advantage on practically useful problems has been demonstrated yet.
Near-term best bets: Quantum simulation of chemistry and materials science (Feynman's original vision) remains the most credible near-term application where classical methods genuinely struggle.

Post-quantum cryptography transition: The mathematical speedups from Shor are certain in principle, even if hardware realisation is distant. The NIST post-quantum cryptography standardisation (2024) produced the first quantum-resistant encryption standards based on lattice problems (ML-KEM, ML-DSA), hash-based signatures (SPHINCS+). Internet infrastructure migration is already underway for long-lived secrets that must remain secure for 25+ years — a "harvest now, decrypt later" threat exists even before quantum hardware matures.