Quantum algorithms and error correction: Deutsch–Jozsa, Grover, Shor and the surface code

Lesson 10 built the language of quantum circuits. This lesson asks what the language is good for. A quantum computer is not a faster classical computer: it does not try all answers at once and report the best, since measuring a superposition gives only one random result. Its power comes from interference. A well-designed algorithm arranges for the amplitudes of wrong answers to cancel and those of right answers to add. Three algorithms show how this works and how much it can gain: the Deutsch–Jozsa algorithm, Grover's search and Shor's factoring algorithm. The second half of the lesson turns to the problem that every algorithm faces in practice, errors, and to the quantum error-correcting codes that are expected to make large computations possible.

Quantum parallelism and the phase oracle

Many algorithms query a function \(f\) given as a black box, an oracle. For a function from \(n\) bits to one bit, the oracle can be implemented as the unitary \(U_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle\). With the second register prepared in \(|{-}\rangle\), the oracle simply multiplies each basis state by a sign, \(U_f|x\rangle|{-}\rangle = (-1)^{f(x)}|x\rangle|{-}\rangle\), a trick called phase kickback. Applying \(H^{\otimes n}\) to \(|0\cdots0\rangle\) first gives the uniform superposition \(2^{-n/2}\sum_x|x\rangle\), and one query then writes all \(2^n\) values of \(f\) into the phases. The values are not directly readable, but interference can extract global properties of \(f\) from them.

The Deutsch–Jozsa algorithm

David Deutsch and Richard Jozsa posed the problem in 1992. A function \(f\) on \(n\) bits is promised to be either constant (the same value for every input) or balanced (0 for exactly half the inputs). Decide which. A classical deterministic algorithm may need \(2^{n-1} + 1\) queries in the worst case. The quantum algorithm needs one. Apply \(H^{\otimes n}\), the phase oracle and \(H^{\otimes n}\) again. The amplitude of \(|0\cdots0\rangle\) at the end is

so measuring all zeros means constant and anything else means balanced, with certainty. The problem is artificial, and a randomized classical algorithm solves it with high probability in a few queries, but it was the first clear demonstration that quantum interference can outperform deterministic classical computation by an exponential factor.

Grover's search

Lov Grover found in 1996 a quantum algorithm for unstructured search: given an oracle that marks one item among \(N\), find it. Classically this needs about \(N/2\) queries on average. Grover's algorithm needs about \((\pi/4)\sqrt N\). Start in the uniform superposition \(|s\rangle\). Each iteration applies the oracle, which flips the sign of the marked state \(|w\rangle\), and then the diffusion operator \(2|s\rangle\langle s| - 1\), which reflects every amplitude about the mean. The two reflections together rotate the state by an angle \(2\theta\) in the plane spanned by \(|w\rangle\) and \(|s\rangle\), where \(\sin\theta = 1/\sqrt N\). After \(k\) iterations

The success probability rises, peaks near 1 at the optimal number of iterations and then falls again as the rotation overshoots. The quadratic speedup is the best possible for unstructured search: Bennett, Bernstein, Brassard and Vazirani proved in 1997 that any quantum algorithm needs at least of order \(\sqrt N\) queries. Grover's method generalizes to amplitude amplification, which squares the speed of any algorithm that succeeds with small probability.

Shor's algorithm

Peter Shor's algorithm of 1994 factors an integer \(N\) in a time that grows only as a polynomial in the number of digits, while the best known classical algorithm, the number field sieve, is subexponential. Factoring reduces to finding the period \(r\) of the function \(f(x) = a^x \bmod N\) for a random \(a\): if \(r\) is even and \(a^{r/2} \not\equiv -1\), then \(\gcd(a^{r/2} \pm 1, N)\) gives factors, as in MATH-351. The quantum part prepares a superposition over \(x\), computes \(f(x)\) into a second register, and applies the quantum Fourier transform to the first. The periodic structure makes the amplitudes interfere constructively only at multiples of \(2^n/r\), so a measurement gives a number from which \(r\) follows by continued fractions. The quantum Fourier transform on \(n\) qubits needs only about \(n^2\) gates, against \(n2^n\) operations for the classical fast Fourier transform on the same \(2^n\) numbers.

Because the security of RSA and of elliptic-curve cryptography rests on factoring and discrete logarithms, Shor's algorithm would break most public-key cryptography in use today. Estimates in 2025 put the cost of factoring a 2,048-bit RSA key at around a million noisy physical qubits running for about a week, far beyond current machines but not beyond plausible engineering. NIST published its first post-quantum cryptography standards, ML-KEM (FIPS 203), ML-DSA (FIPS 204) and SLH-DSA (FIPS 205), in August 2024, and selected the code-based algorithm HQC as a further key-encapsulation standard in March 2025. Governments, including Canada's, have set timelines for migrating to them.

Why error correction is hard, and why it works

Classical error correction protects bits with redundancy: send 000 for 0, and a single flipped bit can be outvoted. Quantum information seems to resist this. Qubits cannot be cloned; measuring them to look for errors destroys superpositions; and errors are continuous, since a small unwanted rotation can take any state to any nearby one. Shor overcame all three objections in 1995 with a nine-qubit code, and Andrew Steane found a seven-qubit code in 1996. The key ideas appear already in the three-qubit bit-flip code.

Encode \(\alpha|0\rangle + \beta|1\rangle\) as \(\alpha|000\rangle + \beta|111\rangle\), which requires no copying: two CNOTs entangle two fresh qubits with the original. Suppose one qubit may have been flipped by \(X\). Measure the two parities \(Z_1Z_2\) and \(Z_2Z_3\), using ancilla qubits. These operators have the same value on \(|000\rangle\) and \(|111\rangle\), so measuring them reveals nothing about \(\alpha\) and \(\beta\); they reveal only which qubit, if any, was flipped. The outcome, the syndrome, determines the correction:

Continuous errors are handled automatically. A small rotation \(\cos\epsilon\,1 - i\sin\epsilon\,X_1\) on qubit 1 produces a superposition of no error and an \(X_1\) error; measuring the syndrome collapses it into one or the other, and the correction removes it. Errors are digitized by the measurement. If each qubit flips independently with probability \(p\), the code fails only when two or more flip, with probability \(3p^2 - 2p^3\), which is smaller than \(p\) whenever \(p < 1/2\). Phase flips \(Z\) are corrected by the same code in the Hadamard basis, and Shor's nine-qubit code combines both to correct any single-qubit error.

The surface code and the threshold

The leading practical scheme is the surface code, developed from Alexei Kitaev's toric code of 1997. Data qubits sit on a square grid and ancillas between them repeatedly measure products of \(X\) on the four qubits around each face and of \(Z\) around each vertex. Only nearest-neighbour interactions are needed, and a code of distance \(d\) uses \(d^2\) data qubits and \(d^2 - 1\) measurement qubits, \(2d^2 - 1\) in all, correcting any pattern of fewer than \(d/2\) errors. The threshold theorem says that if the physical error rate per operation is below a threshold \(p_{\text{th}}\), about 1 in 100 for the surface code, the logical error rate falls exponentially with distance:

where \(\Lambda\) is the factor gained each time \(d\) increases by 2. In December 2024 Google Quantum AI reported in Nature that its 105-qubit Willow processor operated a surface-code memory below threshold. Growing the code from a 3-by-3 to a 5-by-5 to a 7-by-7 grid of data qubits halved the logical error each time, \(\Lambda \approx 2\), reaching about \(1.4 \times 10^{-3}\) per cycle at distance 7, below the error of the best physical qubit on the chip. IBM's roadmap, updated in 2025, aims for a fault-tolerant machine called Starling by 2029, using a different family of codes, and in November 2025 IBM introduced Loon, an experimental processor with the long-range couplers those codes require.

import math, random

# Statevector helpers on n qubits (amplitudes are real here)
def hadamard_all(psi, n):
    for q in range(n):
        step = 1 << q; out = psi[:]
        for i in range(len(psi)):
            if not i & step:
                a, b = psi[i], psi[i | step]
                out[i], out[i | step] = (a + b) / math.sqrt(2), (a - b) / math.sqrt(2)
        psi = out
    return psi

# 1. Deutsch-Jozsa with a phase oracle: one query decides constant vs balanced
n = 3; N = 2 ** n
oracles = {"constant 0": lambda x: 0, "constant 1": lambda x: 1,
           "balanced: parity": lambda x: bin(x).count("1") % 2, "balanced: top bit": lambda x: x >> (n - 1)}
print(f"Deutsch-Jozsa on {n} qubits (one oracle query):")
for name, f in oracles.items():
    psi = hadamard_all([1.0] + [0.0] * (N - 1), n)
    psi = [(-1) ** f(x) * a for x, a in enumerate(psi)]
    psi = hadamard_all(psi, n)
    p0 = psi[0] ** 2
    print(f"  {name:18s} P(measure 000) = {p0:.3f}  ->  {'constant' if p0 > 0.5 else 'balanced'}")
print()

# 2. Grover search for one marked item among N
def grover(n, marked, iters):
    N = 2 ** n; psi = [1 / math.sqrt(N)] * N
    for _ in range(iters):
        psi[marked] = -psi[marked]                      # oracle
        m = sum(psi) / N; psi = [2 * m - a for a in psi]  # inversion about the mean
    return psi[marked] ** 2
for n in (4, 6, 10):
    N = 2 ** n; k = round(math.pi / 4 * math.sqrt(N) - 0.5)
    row = " ".join(f"{grover(n, 5, it):.3f}" for it in range(0, k + 2))
    print(f"Grover N = {N:5d}: optimal {k} iterations (vs about {N // 2} classical tries); P(marked) by iteration: {row}")
print()

# 3. Three-qubit bit-flip code: Monte Carlo with independent flips of probability p
rnd = random.Random(1995)
def trial(p):
    word = [0, 0, 0]                                   # logical 0 encoded as 000
    for i in range(3):
        if rnd.random() < p: word[i] ^= 1
    s1, s2 = word[0] ^ word[1], word[1] ^ word[2]      # syndrome from two parity checks
    fix = {(1, 0): 0, (1, 1): 1, (0, 1): 2}.get((s1, s2))
    if fix is not None: word[fix] ^= 1
    return word != [0, 0, 0]
print("Bit-flip code: logical error rate vs physical rate p")
print("    p       unencoded   encoded (simulated)   3p^2 - 2p^3")
for p in (0.01, 0.05, 0.1, 0.3, 0.5):
    M = 200000; fails = sum(trial(p) for _ in range(M))
    print(f"  {p:5.2f}       {p:.4f}        {fails / M:.4f}             {3 * p * p - 2 * p ** 3:.4f}")
print()

# 4. Surface code scaling: logical error per cycle falls by a factor Lambda each time d grows by 2
Lam, eps3 = 2.0, 5.6e-3          # Lambda about 2; eps3 chosen so that d = 7 gives 1.4e-3, close to the 2024 Willow result
print("Surface code (Lambda = 2):  d   physical qubits 2d^2 - 1   logical error per cycle")
for d in (3, 5, 7, 11, 15, 25):
    print(f"                           {d:2d}        {2 * d * d - 1:5d}                  {eps3 / Lam ** ((d - 3) / 2):.1e}")

Deutsch-Jozsa on 3 qubits (one oracle query):
  constant 0         P(measure 000) = 1.000  ->  constant
  constant 1         P(measure 000) = 1.000  ->  constant
  balanced: parity   P(measure 000) = 0.000  ->  balanced
  balanced: top bit  P(measure 000) = 0.000  ->  balanced

Grover N =    16: optimal 3 iterations (vs about 8 classical tries); P(marked) by iteration: 0.062 0.473 0.908 0.961 0.582
Grover N =    64: optimal 6 iterations (vs about 32 classical tries); P(marked) by iteration: 0.016 0.135 0.344 0.591 0.816 0.964 0.997 0.907
Grover N =  1024: optimal 25 iterations (vs about 512 classical tries); P(marked) by iteration: 0.001 0.009 0.024 0.047 0.077 0.114 0.156 0.204 0.257 0.313 0.372 0.434 0.496 0.558 0.620 0.679 0.736 0.789 0.838 0.881 0.919 0.949 0.973 0.990 0.998 0.999 0.993

Bit-flip code: logical error rate vs physical rate p
    p       unencoded   encoded (simulated)   3p^2 - 2p^3
   0.01       0.0100        0.0003             0.0003
   0.05       0.0500        0.0072             0.0073
   0.10       0.1000        0.0282             0.0280
   0.30       0.3000        0.2171             0.2160
   0.50       0.5000        0.4991             0.5000

Surface code (Lambda = 2):  d   physical qubits 2d^2 - 1   logical error per cycle
                            3           17                  5.6e-03
                            5           49                  2.8e-03
                            7           97                  1.4e-03
                           11          241                  3.5e-04
                           15          449                  8.7e-05
                           25         1249                  2.7e-06

The Deutsch–Jozsa runs distinguish all four oracles with a single query, with probabilities exactly 1 or 0. The Grover tables show the rise and fall of the success probability; for \(N = 1024\) the optimal 25 iterations give 0.999, where a classical search would need about 512 tries on average. The bit-flip Monte Carlo matches \(3p^2 - 2p^3\) and shows the code helping for small \(p\) and becoming useless at \(p = 1/2\). The last table extrapolates the Willow scaling: with \(\Lambda = 2\), reaching \(10^{-6}\) per cycle would take a distance of about 25 and over a thousand physical qubits per logical qubit. Larger \(\Lambda\), from better physical qubits, reduces that overhead dramatically, which is why hardware improvements still matter after the threshold has been passed.