The Fourier transform and phase estimation

The quantum Fourier transform is a matrix, and a circuit

On N = 2ⁿ basis states the QFT sends |j〉 to N^−1/2 Σ_k e^2πijk/N|k〉. Its matrix F_jk = e^2πijk/N/√N is unitary because the columns are orthonormal: Σ_j e^{2πij(k−k′)/N} = N if k = k′ and 0 otherwise (a geometric series of roots of unity). The circuit that implements it uses n(n+1)/2 gates plus swaps: for each qubit a Hadamard followed by controlled phase rotations of angle 2π/2^m from each later qubit, and a final bit reversal. The product formula behind it is |j〉 → ⊗_l (|0〉 + e^2πij/2l|1〉)/√2.

Two structural facts. Over the group Z₂ⁿ the same construction is the n-fold Hadamard, the transform inside the Deutsch–Jozsa and Bernstein–Vazirani circuits. And F diagonalises the cyclic shift S|k〉 = |k+1〉: F^†SF = diag(ω^k) with ω = e^±2πi/N, which is the whole reason the transform detects periods.

Reading an eigenvalue off the Fourier transform

Let U|u〉 = e^2πiφ|u〉. Controlled-U^2k applied to a uniform superposition of control qubits leaves the register in T^−1/2 Σ_k e^2πikφ|k〉 (T = 2^t), by phase kickback, and the inverse QFT turns that into a peak at φT. If φ = m/T exactly, the output is |m〉 with probability 1. In general, with δ = φ − m/T, summing the geometric series gives

P(m)  =  sin^2(pi T d) / ( T^2 sin^2(pi d) )

The 4/π² bound. For the nearest estimate |δ| ≤ 1/(2T). Using sin x ≥ 2x/π on [0, π/2] gives sin(πTδ) ≥ 2T|δ|, and sin(πδ) ≤ π|δ|, so P ≥ (2Tδ)²/(T²π²δ²) = 4/π² ≈ 0.405 for the best t-bit estimate. Nielsen and Chuang give the stronger form: with t = n + ⌈log(2 + 1/(2ε))⌉ qubits, n bits of φ are returned with probability at least 1 − ε.

From estimate to fraction. If φ = s/r and |s/r − φ′| ≤ 1/(2r²), then s/r is a convergent of the continued fraction of φ′ (Nielsen & Chuang, Theorem 5.1), so a t-bit estimate with 2^−t ≤ 1/(2r²) recovers the exact rational. Kitaev's 1995 paper measures an eigenvalue exactly this way: refine to precision 2⁻²ⁿ⁻¹, then take continued fractions.

Built two ways and compared

F^dagger F = I, N = 2..64                                   worst 6.7e-15
circuit (H + controlled phases + bit reversal) = matrix,
  every basis state, n = 1..7                               worst 1.2e-14
inverse circuit undoes it on a random 5-qubit state
H^(x)n = Z_2^n character table / sqrt(2^n), n = 1..6
F^dagger S F = diag(roots of unity), N = 4, 8, 16, 32        worst 8.3e-15
phase estimation, phi = m/2^t: |m> with probability 1, t = 2..7, every m
simulated distribution vs sin^2(pi T d)/(T^2 sin^2(pi d)),
  40 random (t, phi)                                         worst 5.2e-15
nearest t-bit estimate: P >= 4/pi^2 = 0.4053;               minimum seen 0.4262
continued fractions recover every reduced p/q, q <= 40, from its t-bit
  estimate with t = 2 ceil(log2 q) + 1

Controls: dropping the bit reversal breaks circuit = matrix; using F in place of F^† returns |−3 mod 16〉 = |13〉 instead of |3〉, reading the phase backwards (the first draft of this control claimed it returned “not |3〉” with a bound that was itself wrong: it returns a different state with probability 1); a non-dyadic phase never gives a single outcome with probability 1.

Run it: python3 quantum-maths/qm3-verify.py (standard library only; the sourcing block says SKIP, never PASS, if the source PDF is not in ~/Downloads).