Algorithms, decoherence and error correction

Ten qubits live in C² ⊗ … ⊗ C² = C¹⁰²⁴, and H⊗¹⁰ on |0…0⟩ gives |s⟩ = 2⁽⁻⁵⁾ Σₓ |x⟩, a vector with 1024 equal amplitudes. A reversible oracle U_f|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⊗ⁿ 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.

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⊗ⁿ(2|0⟩⟨0| − I)H⊗ⁿ 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 G^k|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 numpy.linalg.matrix_power(D @ O, k) @ s reproduces every number above.

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.00000 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 k drawn at random from a growing range, or the algorithm overshoots.

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 = 2ᵐ, 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.

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 exp(−t/T_φ) and leaves the populations alone. Together 1/T₂ = 1/(2T₁) + 1/T_φ, so T₂ ≤ 2T₁: the coherence can never outlive twice the population lifetime, and dephasing usually makes it 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⁻⁹ s)/(80 × 10⁻⁶ s) = 5 × 10⁻⁴ of its coherence per gate from idling alone; a measured gate error of 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.

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: p_L = 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 p_L ≈ cp² and ℓ concatenations give (1/c)(cp)^{(2^ℓ)}: below pₜₕ = 1/c the logical error falls doubly exponentially while qubits grow only as 7^ℓ for the 7-qubit Steane code. The surface code, with local checks only, has pₜₕ ≈ 10⁻² and p_L ≈ 0.1(p/pₜₕ)^(t+1), where t = (d − 1)/2 is the number of correctable errors: at p = 10⁻³, d = 25 gives t + 1 = 13 and 10⁻¹⁴ per cycle for 2d² − 1 = 1249 physical qubits.