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 . For the 4000-qubit registers of cryptographic factoring that is a rotation by , 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 , including the shift–phase duality .
- Prove that the product-formula circuit computes exactly, count its gates, and schedule it in depth .
- Prove and conclude that 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 matter in quantum algorithms. For (bit strings under XOR) the characters are and , the transform behind Bernstein–Vazirani and Simon. For (integers mod ) you get the QFT. Same Hilbert space, different group, different transform: the symmetry the problem hides decides which transform you need.
Apply the definition to the shifted basis state.
The extra factor depends only on the output label: it is the diagonal operator . So on a basis, hence everywhere.
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 must be supported on eigenvalues of equal to 1, i.e. on multiples of .
Think first In Simon's problem the hidden symmetry is ; in period finding it is . Why does the first need and the second the QFT?
Each transform diagonalizes the translations of its own group. diagonalizes (Pauli- strings) and turns XOR-periodicity into the linear condition . The QFT diagonalizes and turns additive periodicity into peaks at multiples of . 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
Invariant after applied to : wire holds its finished factor, and wires still hold their input bits. For this is just .
applies to wire , producing the phase , then controlled by wire for . Those control wires have not been touched yet, so they are in basis states and each rotation adds exactly .
Wires do not participate in , so the invariant holds for . After , wire holds factor of the product formula and moves it to position . Two linear maps that agree on a basis are equal.
Each controlled rotation costs two CNOTs and three single-qubit phase gates: , because the phases add up to on . All the controlled rotations are diagonal, so they commute with each other; the only ordering constraint is that the rotation between wires comes after and before .
Assign every gate to a time layer.
The ordering constraints hold.
No conflicts: in layer , wire can only be paired with wire , so it carries at most one gate; when , that layer is exactly its Hadamard layer. The last gate is in layer . With nearest-neighbor connectivity only, swap networks still give linear depth.
The approximate QFT
Hybrid argument: for unitaries, , by inserting the hybrids , the triangle inequality and unitary invariance of the operator norm.
Deleting a gate replaces it by the identity, and a controlled- differs from only on .
The exact circuit contains copies of , one in each of the blocks .
For basis-state inputs the error is far smaller. is still a product state, and output wire only misses the bits beyond in its binary fraction: a phase error . Two equatorial qubit states differing by phase have overlap , so
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 plus a small constant leaves the success probability essentially unchanged, so in practice the QFT costs gates.
Using the bound , what is the smallest cutoff that guarantees operator-norm error at most for qubits?
Show the answer
20
and , so . The circuit keeps about rotations instead of , and no rotation smaller than .
Think first In the widget below, the three-qubit QFT acts on with its smallest rotation (controlled-, angle ) deleted. Before touching anything: what fidelity with the exact do you expect?
Only one output qubit is affected, with phase error (the missing term). The fidelity is . Dropping a rotation by is a large error; dropping one by in a huge register costs about .
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.
For , the counting qubit that controlled is in this state, since the integer part of drops out.
Start with : its phase is , so a Hadamard maps it to . Measure.
Knowing , remove their contribution with one classically computed phase gate, apply , and measure .
Apply the controlled- in the order ; then the counting qubits are needed one at a time, and a single control qubit, measured and reset times, suffices. For a general 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 qubits for an -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 of them for precision (Ross & Selinger). The semiclassical QFT needs only 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.
In the semiclassical inverse QFT of phase estimation with counting qubits, how many two-qubit gates does the Fourier part use?
Show the answer
C.
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-, which are not part of the Fourier transform, remain two-qubit operations.
Key takeaways
- diagonalizes the translations of : turns shifts into phases. The group decides the transform: for , the QFT for .
- : Hadamards, controlled rotations (two CNOTs each), swaps, schedulable in depth .
- , so gates suffice; basis-state errors are only , and 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.
For and target error , which cutoff does require, and roughly how many controlled rotations remain?
- , about rotations
- , about rotations
- , about rotations
- , about rotations
Show the answer
C. , about rotations
and , so . Each of the 4000 blocks keeps at most 24 rotations: about in total, versus for the exact QFT.
The identity implies which fact used in period finding?
- Shifting the input by multiplies each output amplitude by a phase, leaving the output distribution unchanged
- The QFT maps every periodic state to a basis state
- The QFT commutes with the shift operator
- The QFT is a Clifford operation
Show the answer
A. Shifting the input by multiplies each output amplitude by a phase, leaving the output distribution unchanged
, and is diagonal with unit-modulus entries : it changes phases, not probabilities.
Why may each controlled rotation of an inverse QFT be replaced by measuring its control first and applying a classically controlled phase?
- Because the QFT is its own inverse
- Because all the rotations are Clifford gates
- Because the control qubits are never entangled with the targets
- 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 on the control commute with the controlled gate, so measuring early gives the same joint statistics.
Which statement about the QFT is correct?
- Implementing it exactly requires exponentially many gates
- 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
- It consists of Clifford gates only, so the Gottesman–Knill theorem applies
- Dropping the small rotations degrades the fidelity exponentially in
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 gates, contains non-Clifford rotations, and tolerates dropping all rotations beyond . 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).