Simple Algorithm
Quantum Computing · Rydberg State · 28 min

Deriving the QFT Circuit

The product formula, O(n²) gates and the approximate QFT.

The textbook QFT asks for controlled rotations by angles as small as 2π/2n2\pi/2^n. For the 4000-qubit registers of cryptographic factoring that is a rotation by 2π/240002\pi/2^{4000}, a gate no device will ever resolve, and none needs to. This lesson derives the circuit exactly, proves that almost all of its rotations can be dropped, and shows that measurement with classical feed-forward can replace every two-qubit gate.

What you’ll learn

  • Derive the QFT from the characters of ZN\Z_N, including the shift–phase duality FNXFN†=ZF_NXF_N^\dagger=Z.
  • Prove that the product-formula circuit computes F2nF_{2^n} exactly, count its gates, and schedule it in depth 2n−12n-1.
  • Prove ∥F2n−AQFTm∥<2πn/2m\norm{F_{2^n}-\mathrm{AQFT}_m}<2\pi n/2^m and conclude that O(nlog⁡(n/ε))\order{n\log(n/\varepsilon)} gates suffice.
  • Justify the semiclassical QFT, and explain why the QFT is never the bottleneck of Shor's algorithm.

Fourier analysis on Z_N

Two groups of order 2n2^n matter in quantum algorithms. For G=Z2nG=\Z_2^n (bit strings under XOR) the characters are (−1)x⋅y(-1)^{x\cdot y} and FG=H⊗nF_G=H^{\otimes n}, the transform behind Bernstein–Vazirani and Simon. For G=Z2nG=\Z_{2^n} (integers mod 2n2^n) you get the QFT. Same Hilbert space, different group, different transform: the symmetry the problem hides decides which transform you need.

DerivationProof of the first identity, and the convolution theorem
  1. FNX∣x⟩=FN∣x+1⟩=1N∑yωN(x+1)y∣y⟩F_NX\ket{x}=F_N\ket{x+1}=\frac{1}{\sqrt N}\sum_y\omega_N^{(x+1)y}\ket{y}

    Apply the definition to the shifted basis state.

  2. =1N∑yωNy ωNxy∣y⟩=Z FN∣x⟩=\frac{1}{\sqrt N}\sum_y\omega_N^{y}\,\omega_N^{xy}\ket{y}=Z\,F_N\ket{x}

    The extra factor ωNy\omega_N^y depends only on the output label: it is the diagonal operator ZZ. So FNX=ZFNF_NX=ZF_N on a basis, hence everywhere.

  3. FN(∑cf(c)Xc)FN†=∑cf(c)ZcF_N\Bigl(\sum_{c}f(c)X^{c}\Bigr)F_N^\dagger=\sum_{c}f(c)Z^{c}

    Every translation, and every translation-invariant operator (a circulant matrix), is diagonalized by the QFT. This is the convolution theorem, and the reason periodicity turns into peaks: a state invariant under XrX^r must be supported on eigenvalues of ZrZ^r equal to 1, i.e. on multiples of N/rN/r.

Think first In Simon's problem the hidden symmetry is f(x)=f(x⊕s)f(x)=f(x\oplus s); in period finding it is f(x)=f(x+r)f(x)=f(x+r). Why does the first need H⊗nH^{\otimes n} and the second the QFT?

Each transform diagonalizes the translations of its own group. H⊗nH^{\otimes n} diagonalizes x↦x⊕sx\mapsto x\oplus s (Pauli-XX strings) and turns XOR-periodicity into the linear condition y⋅s=0y\cdot s=0. The QFT diagonalizes x↦x+r mod 2nx\mapsto x+r \bmod 2^n and turns additive periodicity into peaks at multiples of 2n/r2^n/r. Addition carries and XOR does not, so the translations of one group are not translations of the other, and the wrong transform reveals no structure.

The exact circuit: proof, gate count, depth

DerivationProof by induction over the blocks
  1. [⨂i≤j12(∣0⟩+e2πi 0.xi⋯xn∣1⟩)]⊗∣xj+1⋯xn⟩\Bigl[\bigotimes_{i\le j}\tfrac{1}{\sqrt2}\bigl(\ket0+e^{2\pi i\,0.x_i\cdots x_n}\ket1\bigr)\Bigr]\otimes\ket{x_{j+1}\cdots x_n}

    Invariant after B1,…,BjB_1,\dots,B_j applied to ∣x⟩\ket{x}: wire i≤ji\le j holds its finished factor, and wires i>ji>j still hold their input bits. For j=0j=0 this is just ∣x⟩\ket x.

  2. 12(∣0⟩+e2πi (0.xj+1+∑k=2n−jxj+k2−k)∣1⟩)=12(∣0⟩+e2πi 0.xj+1⋯xn∣1⟩)\tfrac{1}{\sqrt2}\Bigl(\ket0+e^{2\pi i\,(0.x_{j+1}+\sum_{k=2}^{n-j}x_{j+k}2^{-k})}\ket1\Bigr)=\tfrac{1}{\sqrt2}\bigl(\ket0+e^{2\pi i\,0.x_{j+1}\cdots x_n}\ket1\bigr)

    Bj+1B_{j+1} applies HH to wire j+1j+1, producing the phase e2πi 0.xj+1e^{2\pi i\,0.x_{j+1}}, then RkR_k controlled by wire j+kj+k for k=2,…,n−jk=2,\dots,n-j. Those control wires have not been touched yet, so they are in basis states and each rotation adds exactly xj+k/2kx_{j+k}/2^k.

  3. Πrev Bn⋯B1∣x⟩=F2n∣x⟩for all x\Pi_{\mathrm{rev}}\,B_n\cdots B_1\ket{x}=F_{2^n}\ket{x}\quad\text{for all }x

    Wires i≤ji\le j do not participate in Bj+1B_{j+1}, so the invariant holds for j+1j+1. After BnB_n, wire ii holds factor n+1−in+1-i of the product formula and Πrev\Pi_{\mathrm{rev}} moves it to position ii. Two linear maps that agree on a basis are equal. ■\blacksquare

Each controlled rotation costs two CNOTs and three single-qubit phase gates: C-P(θ)=(P(θ2)⊗P(θ2)) CNOT (I⊗P(−θ2)) CNOTC\text{-}P(\theta)=\bigl(P(\tfrac\theta2)\otimes P(\tfrac\theta2)\bigr)\,\mathrm{CNOT}\,\bigl(\id\otimes P(-\tfrac\theta2)\bigr)\,\mathrm{CNOT}, because the phases add up to θ2 (c+t−c⊕t)=θ ct\tfrac\theta2\,(c+t-c\oplus t)=\theta\,ct on ∣c,t⟩\ket{c,t}. All the controlled rotations are diagonal, so they commute with each other; the only ordering constraint is that the rotation between wires i<i′i<i' comes after H(i)H^{(i)} and before H(i′)H^{(i')}.

DerivationA schedule of depth 2n − 1
  1. H(i)↦layer 2i−1,CR(i,i′)↦layer i+i′−1H^{(i)}\mapsto\text{layer }2i-1,\qquad C R^{(i,i')}\mapsto\text{layer }i+i'-1

    Assign every gate to a time layer.

  2. 2i−1 < i+i′−1 < 2i′−1(i<i′)2i-1\ <\ i+i'-1\ <\ 2i'-1\qquad(i<i')

    The ordering constraints hold.

  3. depth=2n−1(plus the swaps, or none if the wires are relabeled)\text{depth}=2n-1\quad(\text{plus the swaps, or none if the wires are relabeled})

    No conflicts: in layer τ\tau, wire ww can only be paired with wire τ+1−w\tau+1-w, so it carries at most one gate; when τ+1−w=w\tau+1-w=w, that layer is exactly its Hadamard layer. The last gate is H(n)H^{(n)} in layer 2n−12n-1. With nearest-neighbor connectivity only, swap networks still give linear depth.

The approximate QFT

DerivationProof
  1. ∥U2U1−V2V1∥≤∥U2(U1−V1)∥+∥(U2−V2)V1∥=∥U1−V1∥+∥U2−V2∥\norm{U_2U_1-V_2V_1}\le\norm{U_2(U_1-V_1)}+\norm{(U_2-V_2)V_1}=\norm{U_1-V_1}+\norm{U_2-V_2}

    Hybrid argument: for unitaries, ∥UT⋯U1−VT⋯V1∥≤∑t∥Ut−Vt∥\norm{U_T\cdots U_1-V_T\cdots V_1}\le\sum_t\norm{U_t-V_t}, by inserting the hybrids UT⋯Ut+1Vt⋯V1U_T\cdots U_{t+1}V_t\cdots V_1, the triangle inequality and unitary invariance of the operator norm.

  2. ∥CRk−I∥=∣e2πi/2k−1∣=2sin⁡π2k≤2π2k\norm{C R_k-\id}=\abs{e^{2\pi i/2^k}-1}=2\sin\frac{\pi}{2^k}\le\frac{2\pi}{2^k}

    Deleting a gate replaces it by the identity, and a controlled-RkR_k differs from I\id only on ∣11⟩\ket{11}.

  3. ∥F2n−AQFTm∥≤∑k=m+1n(n−k+1)2π2k<2πn∑k>m2−k=2πn2m\norm{F_{2^n}-\mathrm{AQFT}_m}\le\sum_{k=m+1}^{n}(n-k+1)\frac{2\pi}{2^k}<2\pi n\sum_{k>m}2^{-k}=\frac{2\pi n}{2^m}

    The exact circuit contains n−k+1n-k+1 copies of CRkCR_k, one in each of the blocks B1,…,Bn−k+1B_1,\dots,B_{n-k+1}. ■\blacksquare

For basis-state inputs the error is far smaller. AQFTm∣x⟩\mathrm{AQFT}_m\ket{x} is still a product state, and output wire jj only misses the bits beyond xj+m−1x_{j+m-1} in its binary fraction: a phase error ∣δj∣<2π/2m\abs{\delta_j}<2\pi/2^m. Two equatorial qubit states differing by phase δ\delta have overlap ∣cos⁡(δ/2)∣\abs{\cos(\delta/2)}, so

∣⟨x∣F2n† AQFTm∣x⟩∣ ≥ cos⁡nπ2m ≥ 1−nπ22⋅4m.\abs{\bra{x}F_{2^n}^\dagger\,\mathrm{AQFT}_m\ket{x}}\ \ge\ \cos^n\frac{\pi}{2^m}\ \ge\ 1-\frac{n\pi^2}{2\cdot4^m}.

For arbitrary superpositions the operator-norm bound is the safe statement. Analyses of period finding (Coppersmith 1994; Barenco, Ekert, Suominen & Törmä 1996) found that keeping rotations only up to k≈log⁡2nk\approx\log_2n plus a small constant leaves the success probability essentially unchanged, so in practice the QFT costs O(nlog⁡n)\order{n\log n} gates.

Predict before you look

Using the bound 2πn/2m≤ε2\pi n/2^m\le\varepsilon, what is the smallest cutoff mm that guarantees operator-norm error at most ε=0.01\varepsilon=0.01 for n=1000n=1000 qubits?

Show the answer

20

2π⋅1000/0.01≈6.3×1052\pi\cdot1000/0.01\approx6.3\times10^5 and log⁡2(6.3×105)≈19.3\log_2(6.3\times10^5)\approx19.3, so m=20m=20. The circuit keeps about n m≈2×104n\,m\approx2\times10^4 rotations instead of n(n−1)/2≈5×105n(n-1)/2\approx5\times10^5, and no rotation smaller than 2π/2202\pi/2^{20}.

Think first In the widget below, the three-qubit QFT acts on ∣001⟩\ket{001} with its smallest rotation (controlled-TT, angle π/4\pi/4) deleted. Before touching anything: what fidelity with the exact F8∣001⟩F_8\ket{001} do you expect?

Only one output qubit is affected, with phase error δ=π/4\delta=\pi/4 (the missing x3/8x_3/8 term). The fidelity is cos⁡2(δ/2)=cos⁡2(π/8)≈0.854\cos^2(\delta/2)=\cos^2(\pi/8)\approx0.854. Dropping a rotation by π/4\pi/4 is a large error; dropping one by 2π/2252\pi/2^{25} in a huge register costs about sin⁡2(π/225)≈10−14\sin^2(\pi/2^{25})\approx10^{-14}.

Measure instead of entangle: the semiclassical QFT

In every algorithm in this course the QFT, or its inverse, is followed immediately by measurement of all its qubits. Griffiths and Niu (1996) observed that this makes every two-qubit gate of the transform unnecessary.

DerivationThe semiclassical inverse QFT in phase estimation
  1. 12(∣0⟩+e2πi 0.φjφj+1⋯φt∣1⟩)\tfrac{1}{\sqrt2}\bigl(\ket0+e^{2\pi i\,0.\varphi_j\varphi_{j+1}\cdots\varphi_t}\ket1\bigr)

    For φ=0.φ1⋯φt\varphi=0.\varphi_1\cdots\varphi_t, the counting qubit that controlled U2j−1U^{2^{j-1}} is in this state, since the integer part of 2j−1φ2^{j-1}\varphi drops out.

  2. H 12(∣0⟩+(−1)φt∣1⟩)=∣φt⟩H\,\tfrac{1}{\sqrt2}\bigl(\ket0+(-1)^{\varphi_t}\ket1\bigr)=\ket{\varphi_t}

    Start with j=tj=t: its phase is 0.φt=φt/20.\varphi_t=\varphi_t/2, so a Hadamard maps it to ∣φt⟩\ket{\varphi_t}. Measure.

  3. P(−2π 0.0φj+1⋯φt) then H ⟹ ∣φj⟩P\bigl(-2\pi\,0.0\varphi_{j+1}\cdots\varphi_t\bigr)\ \text{then}\ H\ \Longrightarrow\ \ket{\varphi_j}

    Knowing φj+1,…,φt\varphi_{j+1},\dots,\varphi_t, remove their contribution with one classically computed phase gate, apply HH, and measure φj\varphi_j.

  4. t counting qubits ⟶ 1 recycled control qubitt\ \text{counting qubits}\ \longrightarrow\ 1\ \text{recycled control qubit}

    Apply the controlled-U2j−1U^{2^{j-1}} in the order j=t,t−1,…,1j=t,t-1,\dots,1; then the counting qubits are needed one at a time, and a single control qubit, measured and reset tt times, suffices. For a general φ\varphi the procedure reproduces exactly the output statistics of the full circuit.

Compact factoring circuits are built this way: Beauregard's (2003) circuit for Shor's algorithm uses 2L+32L+3 qubits for an LL-bit modulus with one recycled control qubit, and the trapped-ion experiment of Monz et al. (2016) used the same recycling idea.

Fault-tolerant cost. On an error-corrected machine, Clifford gates are cheap, while each arbitrary-angle rotation must be synthesized from T gates, about 3log⁡2(1/ϵ)3\log_2(1/\epsilon) of them for precision ϵ\epsilon (Ross & Selinger). The semiclassical QFT needs only O(n)\order{n} such rotations, whereas the modular exponentiation it follows needs billions of Toffoli gates for RSA-size inputs. The QFT is never the bottleneck of Shor's algorithm.

Check your understanding

In the semiclassical inverse QFT of phase estimation with tt counting qubits, how many two-qubit gates does the Fourier part use?

  1. t(t−1)/2t(t-1)/2
  2. t−1t-1
  3. 00
  4. ⌊t/2⌋\lfloor t/2\rfloor
Show the answer

C. 00

Every controlled rotation becomes a classically controlled single-qubit phase, and the final swaps become a relabeling of the classical output bits. Only the controlled-U2jU^{2^j}, which are not part of the Fourier transform, remain two-qubit operations.

Key takeaways

  • FGF_G diagonalizes the translations of GG: FNXFN†=ZF_NXF_N^\dagger=Z turns shifts into phases. The group decides the transform: H⊗nH^{\otimes n} for Z2n\Z_2^n, the QFT for Z2n\Z_{2^n}.
  • F2n=ΠrevBn⋯B1F_{2^n}=\Pi_{\mathrm{rev}}B_n\cdots B_1: nn Hadamards, n(n−1)/2n(n-1)/2 controlled rotations (two CNOTs each), ⌊n/2⌋\lfloor n/2\rfloor swaps, schedulable in depth 2n−12n-1.
  • ∥F2n−AQFTm∥<2πn/2m\norm{F_{2^n}-\mathrm{AQFT}_m}<2\pi n/2^m, so O(nlog⁡(n/ε))\order{n\log(n/\varepsilon)} gates suffice; basis-state errors are only O(n/4m)\order{n/4^m}, and m≈log⁡2n+O(1)m\approx\log_2n+\order1 works for period finding.
  • When the QFT is followed by measurement, measurement plus classical feed-forward replaces every two-qubit gate; phase estimation then needs a single recycled control qubit.
  • The QFT is cheap and, on its own, classically simulable: the cost and the power of Shor's algorithm lie in modular exponentiation.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

For n=4000n=4000 and target error ε=10−3\varepsilon=10^{-3}, which cutoff does 2πn/2m≤ε2\pi n/2^m\le\varepsilon require, and roughly how many controlled rotations remain?

  1. m=12m=12, about 5×1045\times10^4 rotations
  2. m=4000m=4000, about 8×1068\times10^6 rotations
  3. m=25m=25, about 10510^5 rotations
  4. m=25m=25, about 8×1068\times10^6 rotations
Show the answer

C. m=25m=25, about 10510^5 rotations

2π⋅4000/10−3≈2.5×1072\pi\cdot4000/10^{-3}\approx2.5\times10^7 and log⁡2(2.5×107)≈24.6\log_2(2.5\times10^7)\approx24.6, so m=25m=25. Each of the 4000 blocks keeps at most 24 rotations: about 10510^5 in total, versus n(n−1)/2≈8×106n(n-1)/2\approx8\times10^6 for the exact QFT.

Question 2

The identity FNXFN†=ZF_NXF_N^\dagger=Z implies which fact used in period finding?

  1. Shifting the input by x0x_0 multiplies each output amplitude by a phase, leaving the output distribution unchanged
  2. The QFT maps every periodic state to a basis state
  3. The QFT commutes with the shift operator
  4. The QFT is a Clifford operation
Show the answer

A. Shifting the input by x0x_0 multiplies each output amplitude by a phase, leaving the output distribution unchanged

FNXx0∣ψ⟩=Zx0FN∣ψ⟩F_NX^{x_0}\ket\psi=Z^{x_0}F_N\ket\psi, and Zx0Z^{x_0} is diagonal with unit-modulus entries ωNx0y\omega_N^{x_0y}: it changes phases, not probabilities.

Question 3

Why may each controlled rotation of an inverse QFT be replaced by measuring its control first and applying a classically controlled phase?

  1. Because the QFT is its own inverse
  2. Because all the rotations are Clifford gates
  3. Because the control qubits are never entangled with the targets
  4. Because a controlled phase is diagonal in the control's computational basis, so it commutes with measuring the control, and the control is not acted on again before it is measured
Show the answer

D. Because a controlled phase is diagonal in the control's computational basis, so it commutes with measuring the control, and the control is not acted on again before it is measured

This is the deferred-measurement principle run backwards. The projectors ∣0⟩ ⁣⟨0∣,∣1⟩ ⁣⟨1∣\dyad0,\dyad1 on the control commute with the controlled gate, so measuring early gives the same joint statistics.

Question 4

Which statement about the QFT is correct?

  1. Implementing it exactly requires exponentially many gates
  2. Applied to product states and measured, it is efficiently classically simulable; the hardness of Shor's algorithm comes from the entangled state it acts on
  3. It consists of Clifford gates only, so the Gottesman–Knill theorem applies
  4. Dropping the small rotations degrades the fidelity exponentially in nn
Show the answer

B. Applied to product states and measured, it is efficiently classically simulable; the hardness of Shor's algorithm comes from the entangled state it acts on

The exact QFT needs O(n2)\order{n^2} gates, contains non-Clifford rotations, and tolerates dropping all rotations beyond k≈log⁡nk\approx\log n. On product inputs its output statistics can be computed classically; the quantum advantage in factoring needs the entangled output of modular exponentiation.

Further reading

  • D. Coppersmith, "An approximate Fourier transform useful in quantum factoring", IBM Research Report RC19642 (1994); arXiv:quant-ph/0201067.
  • R. B. Griffiths & C.-S. Niu, "Semiclassical Fourier transform for quantum computation", Phys. Rev. Lett. 76, 3228 (1996).
  • A. Barenco, A. Ekert, K.-A. Suominen & P. Törmä, "Approximate quantum Fourier transform and decoherence", Phys. Rev. A 54, 139 (1996).
  • R. Cleve & J. Watrous, "Fast parallel circuits for the quantum Fourier transform", Proc. 41st IEEE FOCS (2000).
  • M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, §5.1 (Cambridge, 2010).