University Physics V · Introduction to Quantum Information · 20.9
Algorithms, Decoherence & Error Correction
Three questions close the course. What can a quantum register do faster, and by how much? Why does the hardware lose the interference the answer depends on? And how can a code fix errors it is forbidden to look at? Grover, Shor, T₁ and T₂, the three-qubit code and the threshold theorem answer them in that order.
Build the model
Connect the measurement to the mechanism.
An n-qubit register is a unit vector in C(2ⁿ) with 2ⁿ amplitudes, but one measurement returns one n-bit string, so a quantum algorithm is not a parallel evaluation but a unitary sequence that piles amplitude onto the strings worth reading. Grover's search works in the real plane spanned by the marked state |w⟩ and the uniform superposition |s⟩. The oracle O = I − 2|w⟩⟨w| reflects across |w⊥⟩, the diffusion D = 2|s⟩⟨s| − I reflects across |s⟩, and two reflections compose to a rotation by 2θ with sin θ = 1/√N, so after k calls the amplitude on |w⟩ is sin((2k+1)θ): it peaks near k = (π/4)√N and then falls.
The BBBV bound, Ω(√N) calls for any oracle algorithm, makes that quadratic gain final. Shor's factoring is a different kind of gain: order finding through the QFT costs O(n³) gates against a classical best growing sub-exponentially in n = log₂ M. Both are paid for in coherence.
Idling damps the off-diagonal elements of ρ as e(−t/T₂), each gate misfires with probability p, and a 10⁶-gate circuit on 10⁻³ hardware ends maximally mixed. Error correction restores the algebra by encoding a logical qubit in several physical ones and measuring stabilisers that reveal the error without reading the logical state: a distance-3 code turns p into cp², and concatenation drives the logical rate to zero once p sits below the threshold 1/c. Above it, correcting only adds errors.
- Simple definition
- A quantum algorithm arranges interference so that one readout of a 2ⁿ-amplitude register returns a useful n-bit string with high probability; error correction keeps that interference alive by measuring stabilisers that reveal the error but not the logical state.
- Example
- Searching N = 1024 = 2¹⁰ strings, θ = asin(1/32) = 1.79° and each Grover iterate rotates the state by 3.58°, so k = 25 oracle calls lift the marked string to sin²(51 × 1.79°) = 0.999, where 25 classical probes would find it with probability 25/1024 = 0.024.
Two reflections about lines θ apart compose to a rotation by 2θ, so the whole algorithm reduces to 2 × 2 trigonometry in span(|w⟩, |s⟩).
|w⟩ the marked basis state, |s⟩ = N(−1/2) Σₓ |x⟩ the uniform superposition; both are dimensionless unitaries on CN
Gives the success probability at every k, including the fall past the peak: the state keeps rotating, so more calls can mean less.
N = 2ⁿ for n qubits; θ in radians; P(w) = sin²((2k+1)θ) is a dimensionless probability
√N against N/2 is a quadratic gain, and the lower bound proves that unstructured search can never be sped up exponentially.
one oracle call per iterate; a classical search needs N/2 calls on average; with M marked items sin θ = √(M/N)
Modular exponentiation dominates at O(n³): polynomial, against the number field sieve's exp(O(n¹⁄³(ln n)²⁄³)) on the best classical hardware.
n = ⌈log₂ M⌉ for the number M being factored; the order r of a mod M gives factors gcd(a(r/2) ± 1, M) when r is even
Interference lives in ρ₀₁, so T₂ ≤ 2T₁ caps every algorithm: a gate of duration τ carries an error of order τ/T₂ before control imperfections are counted.
T₁ relaxation, Tφ pure dephasing and T₂ total dephasing times in seconds; ρ₀₁ is the coherence, ρ₁₁ the excited population
Below pₜₕ each level squares the suppression while the qubit count grows only polynomially; above it the correction circuitry adds more errors than it removes.
p physical error per gate and pL logical error, both dimensionless; c counts the uncorrectable fault pairs; threshold pₜₕ = 1/c
The register holds 2ⁿ amplitudes and returns n bits
Ten qubits live in C² ⊗ … ⊗ C² = C¹⁰²⁴, and H^⊗10 on |0…0⟩ gives |s⟩ = 2(−5) Σₓ |x⟩, a vector with 1024 equal amplitudes. A reversible oracle Uf|x⟩|0⟩ = |x⟩|f(x)⟩ then evaluates f on every x in one pass — and that is the sentence that misleads. The Born rule returns one string x with probability |⟨x|ψ⟩|², after which the register sits on |x⟩|f(x)⟩ and the other 1023 evaluations are gone; you have learnt f at one random point, which a classical machine does in one call. The Holevo bound makes it a theorem: n qubits deliver at most n classical bits to a reader. So an algorithm is a unitary sequence arranged so that amplitudes on wrong strings cancel and amplitudes on right strings add before the readout. In NumPy the register is ψ = np.zeros(2**n, dtype=complex) with ψ[0] = 1, H^⊗n is reduce(np.kron, [H]*n), and a shot is rng.choice(2**n, p=abs(ψ)**2) — one integer. At n = 20 that vector is 16 MB; at n = 30 it is 16 GB, and the classical cost of simulating the interference is exactly why the speed-ups matter.
Grover: two reflections make a rotation
Write |s⟩ = sin θ|w⟩ + cos θ|w⊥⟩, where |w⊥⟩ is the normalised sum of the N − 1 unmarked strings and sin θ = ⟨w|s⟩ = 1/√N. The oracle O = I − 2|w⟩⟨w| flips the sign of the |w⟩ component, a reflection across |w⊥⟩; on hardware it is the phase kickback of a function oracle acting on an ancilla in |−⟩, so f is queried but never read. The diffusion D = 2|s⟩⟨s| − I = H^⊗n(2|0⟩⟨0| − I)H^⊗n reflects across |s⟩ and needs no oracle at all. Two reflections about lines θ apart compose to a rotation by 2θ, so G = DO turns the state through 2θ per call and Gk|s⟩ sits at angle (2k+1)θ from |w⊥⟩. Take N = 8: θ = asin(1/√8) = 20.70°. One call: 3θ = 62.11°, P(w) = sin² = 0.781. Two: 5θ = 103.5°, P = 0.945. Three: 7θ = 144.9°, P = 0.330 — the state has swung past |w⟩ and is heading back. In code, D = 2*np.outer(s, s) - np.eye(N) and O = np.eye(N) - 2*np.outer(w, w), and np.linalg.matrixpower(D @ O, k) @ s reproduces every number above.
Count the calls, then name the gain honestly
The peak sits where (2k+1)θ is closest to π/2, so kₒₚₜ = round(π/(4θ) − ½), and for large N, θ ≈ 1/√N gives kₒₚₜ ≈ (π/4)√N. For N = 2²⁰ = 1 048 576, θ = 1/1024 rad and kₒₚₜ = 804: the state angle is 1609/1024 = 1.5713 rad and P(w) = sin²(1.5713) = 1.000 to six figures. A classical search needs N/2 = 524 288 probes on average, so the ratio is about 650. Keep going and the rotation continues: at k = 1608 the angle is 3217/1024 = 3.1416 rad ≈ π and P(w) ≈ 0. Two honest qualifiers belong next to the 650. Bennett, Bernstein, Brassard and Vazirani proved in 1997 that any quantum oracle algorithm needs Ω(√N) queries to find w with bounded error, so Grover is optimal and unstructured search can never be exponentially faster. And the count assumes one marked item: with M of them sin θ = √(M/N) and kₒₚₜ ≈ (π/4)√(N/M), so an unknown M has to be estimated first by quantum counting, or the algorithm overshoots.
Shor: turn a period into a Fourier peak
To factor M, pick a coprime a and find the order r, the least r with aʳ ≡ 1 (mod M). For M = 15 and a = 7: 7, 49 ≡ 4, 28 ≡ 13, 91 ≡ 1, so r = 4; r is even and 7² ≡ 4 ≢ −1, so the factors are gcd(4 − 1, 15) = 3 and gcd(4 + 1, 15) = 5. Every step there is classical and cheap except finding r, which is what the register does. Put m = 2n qubits in |s⟩, compute aˣ mod M into a second register, and measure it: the first register collapses to the x sharing one value of aˣ, a comb with period r. The QFT on m qubits, |j⟩ → Q(−1/2) Σₖ e(2πi jk/Q)|k⟩ with Q = 2m, needs m(m+1)/2 Hadamards and controlled phases and turns a comb of period r into peaks at k ≈ jQ/r; one measured k gives r by continued fractions. The modular exponentiation costs O(n³) gates and dominates, so the run is polynomial in n = log₂ M, while the number field sieve takes exp(O(n¹⁄³(ln n)²⁄³)). Two cautions: the comparison is against the best known classical algorithm, not a proven lower bound; and the 2048-bit moduli behind RSA need thousands of logical qubits, which is why the rest of this lesson exists.
Decoherence: where the off-diagonal terms go
Couple one qubit to an environment and trace the environment out; what remains is a map on ρ. Amplitude damping with Kraus operators E₀ = diag(1, √(1 − γ)) and E₁ = √γ |0⟩⟨1|, γ = 1 − e(−t/T₁), sends the excited population ρ₁₁ to ρ₁₁e(−t/T₁) and the coherence ρ₀₁ to ρ₀₁e(−t/2T₁). Pure dephasing multiplies ρ₀₁ by e(−t/T_φ) and leaves the populations alone. Together 1/T₂ = 1/(2T₁) + 1/Tφ, so T₂ ≤ 2T₁ and the coherence is always the first casualty — and interference is nothing but ρ₀₁. Numbers: a transmon with T₁ = 100 μs and T₂ = 80 μs running a 40 ns two-qubit gate loses 40 × 10⁻⁹ / 80 × 10⁻⁶ = 5 × 10⁻⁴ of its coherence per gate from idling alone; the measured 3 × 10⁻³ says control errors dominate. Now cost Grover for N = 2²⁰: 804 iterates of a few hundred gates each is 10⁵ to 10⁶ gates, and at p = 10⁻³ per gate the expected number of faults is 10² to 10³. The figure below models each iterate as succeeding with probability 1 − p and otherwise dumping the register into I/N, P(w) = (1 − p)k sin²((2k+1)θ) + (1 − (1 − p)k)/N; at p = 0.05 the N = 1024 peak drops from 0.999 to 0.33.
Error correction measures the error, not the state
No-cloning forbids a backup, so redundancy is spread rather than copied: two CNOTs take α|0⟩ + β|1⟩ to |ψL⟩ = α|000⟩ + β|111⟩. The stabilisers Z₁Z₂ and Z₂Z₃ return +1 on both |000⟩ and |111⟩, so measuring them reveals nothing about α and β; a bit flip X₂ makes both −1, X₁ gives (−1, +1) and X₃ gives (+1, −1), and each syndrome names one correction. Measuring also discretises a small rotation e(−iεX₂), a superposition of I and X₂, into one of the two. Two or more flips defeat it: pL = 3p²(1 − p) + p³, so p = 0.01 becomes 2.98 × 10⁻⁴. Phase flips need the same code in the |±⟩ basis with X₁X₂ and X₂X₃; Shor's 9-qubit code nests the two and corrects any single-qubit error, since every error is a combination of I, X, Y and Z. With fault-tolerant gadgets a distance-3 code gives pL ≈ cp² and ℓ concatenations give (1/c)(cp)(2^ℓ): below pₜₕ = 1/c the logical error falls doubly exponentially while qubits grow only as 7^ℓ. The surface code, with local checks only, has pₜₕ ≈ 10⁻² and pL ≈ 0.1(p/pₜₕ)((d+1)/2): at p = 10⁻³, d = 25 gives 10⁻¹⁴ per cycle for 2d² − 1 = 1249 physical qubits.
Change one variable at a time
Make the relationship visible.
With p = 0, drag k past kₒₚₜ = 25 for N = 1024: the arrow swings beyond |w⟩ and P(w) slides from 0.999 to 0.33 at k = 40 — Grover overshoots. Then set p = 0.05: the arrow shrinks every iterate, the peak moves to about k = 18 and tops out near 0.33, so noise sets the useful depth.
θ = asin(1/√N)1.79 °
kₒₚₜ = round(π/4θ − ½)25
P(w) IDEAL AT k0.999
P(w) WITH NOISE AT k0.999
Live interpretationθ = asin(1/√N): 1.79 °. kₒₚₜ = round(π/4θ − ½): 25. P(w) IDEAL AT k: 0.999. P(w) WITH NOISE AT k: 0.999
Catch the common trap
Explain before calculating.
A Grover search over N = 2¹⁰ = 1024 strings with one marked item is run for k iterates before readout. Which statement about the success probability P(w) is right?
Choose an answer to test the model.
Practice & worked examples
Reason from the model, then test the result.
EasyA three-qubit register (N = 8) has one marked string. Find θ, then the state angle and success probability after k = 1, 2 and 3 Grover iterates, and say where to stop. Compare with two classical probes.
- sin θ = 1/√N = 1/√8 = 0.3536, so θ = asin(0.3536) = 0.3614 rad = 20.70°. The start |s⟩ already has P(w) = sin²θ = 1/8 = 0.125.
- Each iterate G = DO rotates by 2θ = 41.41°, so after k iterates the angle from |w⊥⟩ is (2k+1)θ: 62.11° at k = 1, 103.5° at k = 2, 144.9° at k = 3.
- P(w) = sin²((2k+1)θ): sin²(62.11°) = 0.781, sin²(103.5°) = 0.945, sin²(144.9°) = 0.330. The third call swings the state past |w⟩ and loses most of what the second gained.
- kₒₚₜ = round(π/(4 × 0.3614) − ½) = round(1.673) = 2, matching the table. Two classical probes find the item with probability 2/8 = 0.250; two Grover calls reach 0.945.
Answerθ = 20.70°; P(w) = 0.781, 0.945 and 0.330 for k = 1, 2, 3; stop at k = 2, where 0.945 beats the classical 0.250 for two probes.
MediumThree physical qubits carry |ψL⟩ = α|000⟩ + β|111⟩ through one memory cycle in which each qubit suffers an independent bit flip with probability p = 0.02. Give the syndrome for a flip on qubit 3, the logical error rate, the gain over an unencoded qubit, and the p above which encoding stops helping.
- Stabilisers Z₁Z₂ and Z₂Z₃ both give +1 on |000⟩ and on |111⟩, so their eigenvalues carry no information about α or β. X₃ anticommutes with Z₂Z₃ only: the syndrome is (Z₁Z₂, Z₂Z₃) = (+1, −1), and the correction is X₃.
- Majority correction fails when two or three qubits flip: pL = 3p²(1 − p) + p³ = 3(0.02)²(0.98) + (0.02)³ = 0.001176 + 0.000008 = 1.18 × 10⁻³.
- An unencoded qubit fails with probability p = 0.02, so the code cuts the error by 0.02/0.001184 = 16.9 times. Halving p to 0.01 cuts pL to 2.98 × 10⁻⁴, a factor 4: the code has turned a linear error into a quadratic one.
- Encoding helps while pL < p, i.e. 3p² − 2p³ < p, or 2p² − 3p + 1 > 0, or (2p − 1)(p − 1) > 0: the threshold is p = ½. Above it majority voting amplifies errors.
- The same three qubits do nothing for phase flips: Z₂ commutes with both stabilisers, so its syndrome is (+1, +1) and the error passes unseen. Phase protection needs the code in the |±⟩ basis with X₁X₂ and X₂X₃, or Shor's 9-qubit nesting of both.
AnswerSyndrome (+1, −1), so apply X₃; pL = 1.18 × 10⁻³ against 0.02 unencoded, a factor 16.9; encoding helps for p < ½. Phase flips are invisible to this code.
HardRun Shor's order finding for M = 15 with a = 7 on a first register of 2n = 8 qubits, so Q = 256. Find r by hand, locate the QFT peaks and their probabilities, extract r from a measured k = 192 by continued fractions, give the factors, and state the probability that a single run succeeds.
- Powers of 7 mod 15: 7¹ = 7, 7² = 49 = 45 + 4 → 4, 7³ = 7 × 4 = 28 → 13, 7⁴ = 7 × 13 = 91 = 90 + 1 → 1. So r = 4, which is even, and 7(r/2) = 7² ≡ 4 ≢ 14 ≡ −1.
- After H^⊗8 and the modular exponentiation the state is Q(−1/2) Σₓ |x⟩|7ˣ mod 15⟩; measuring the second register, say as 4, leaves the first in a comb of the 64 values x ≡ 2 (mod 4).
- The QFT of a comb with period r = 4 over Q = 256 has amplitude only where 4k/256 is an integer: k = 0, 64, 128, 192. Because r divides Q exactly, each carries probability ¼.
- Measured k = 192: k/Q = 192/256 = 3/4 is already in lowest terms, so j/r = 3/4 and r = 4. Check 7⁴ ≡ 1. Then gcd(7² − 1, 15) = gcd(3, 15) = 3 and gcd(7² + 1, 15) = gcd(5, 15) = 5.
- k = 64 gives 1/4 and r = 4 as well; k = 128 gives 1/2, so r = 2, and 7² ≡ 4 ≠ 1 fails; k = 0 says nothing. Only j coprime to r works, so one run succeeds with probability 2/4 = ½ and a few repeats are expected.
Answerr = 4; peaks at k = 0, 64, 128, 192 with probability ¼ each; k = 192 gives r = 4 and 15 = 3 × 5; a single run succeeds with probability ½.