The Fourier transform on basis states has an apparently exponential-sized matrix. Its special phase structure nevertheless permits a circuit with quadratically many elementary rotations. To see how, we must keep track of which bit carries which fraction of the input: reversing those bits changes the unitary unless the outputs are reinterpreted.
Factor the Fourier sum
Definition 2.3.1
(Quantum Fourier transform on n qubits)
Let and . The quantum Fourier transform is the unitary on qubits with
Write and , so is the least significant bit. For define the binary fraction .
The matrix has entries, yet each output bit can be summed independently.
Theorem 2.3.2
(Product form of the Fourier transform)
With the notation above,
The factors are listed from the most significant output bit to the least significant one.
Proof
(Summing one output bit at a time)
Expand with . Then
The sum over all is a sum over independent bits , and a sum of products of functions of separate variables is the product of the separate sums. Hence
The phase of the factor at output bit weight depends only on modulo . Terms with contribute integers and may be discarded. The remaining terms give . For this is and for it is , which is the displayed order.
In the displayed tensor order the most significant output bit appears first. The binary fractions therefore appear in the reverse order from the input wires.
Construct the circuit
Definition 2.3.3
(Phase gate and controlled phase gate)
For an integer let . The controlled multiplies by and fixes the other three computational basis states of its two wires.
On wires numbered by their input bit weights, perform the following steps in order:
- For , apply a Hadamard to wire .
- Immediately afterward, for each , apply controlled with control wire and target wire .
- After all these blocks, reverse the wire order using swaps.
Theorem 2.3.4
(Exact circuit for the Fourier transform)
The circuit above, with Hadamards, controlled rotations and swaps, equals as a unitary map, for the positive-exponent convention of the definition.
Proof
(One wire at a time on a basis input)
When wire is processed on a basis input, the lower-index control wires have not yet been changed. Its Hadamard contributes phase to the term; the rotations contribute . Thus its factor is
Before the swaps these factors occur in decreasing , the reverse of the product for . The swaps put them in the displayed order. Since the circuit and agree on every computational basis vector, linearity makes them equal on every input state, including entangled or superposed inputs. The proof uses the stated positive-exponent convention; the inverse transform reverses the gate order and replaces each gate by its adjoint.
Proof X-ray
Where each hypothesis of the circuit proof is used
The argument has three moving parts. First, the order is what keeps every control wire in its input state when it is used, so the rotation angles depend on input bits and not on already transformed wires. Second, the angle is chosen so that the control bit adds exactly the term of the binary fraction. Third, the swaps repair only the ordering of the product, not any phase.
The calculation is carried out on basis inputs, and it proves an equality of two linear maps, not a claim that the input is known to be a basis state. Once the maps agree on a basis, linearity fixes them on every superposition. The description of untouched control bits belongs to the basis calculation; it must not be read as a measurement of those bits.
Worked example 2.3.5
(Phases for three bits)
For and , the input is . Before reversal the wire factors from most to least significant carry phases , , and . After reversal,
The relative phase is the negative of ; replacing it changes the state, not merely its global phase. If the output swaps are omitted, this expression's tensor factors are reversed, so bit labels must be interpreted accordingly.
Worked example 2.3.6
(A trace for two bits)
Take and , so . Wire is processed first. Its Hadamard gives , and the controlled with control wire in state multiplies the term by . The wire factor is , which matches the phase . Wire then receives only a Hadamard and becomes . Before the swap the state is ; after the swap
Directly, has coefficients for , in agreement.
Worked example 2.3.7
(The smallest case )
For there are no controlled rotations, since is impossible for , and swaps. The circuit is a single Hadamard. The product form gives , so the quantum Fourier transform on one qubit is the Hadamard gate.
Concept lensStructural
The transform that turns the cyclic shift into phases
Let and . The definition gives with , so . The Fourier transform is the change of basis that diagonalizes the cyclic shift, which is why it is sensitive to periodic structure.
A product-form output for every basis input suggests that every output is a product state; this fails as soon as the input is a superposition.
Counterexample mode
A sum of product states need not be a product state
Claim: since is a product state for every basis input, is a product state for every input . For the basis input does produce a product state as above. But input produces coefficients in order , because and . Its coefficient matrix has nonzero determinant , so the output is entangled. Linearity does not say that a sum of product states is itself a product state; the claim is true only for basis inputs.
Common mistake
(Forgetting the bit reversal)
Without the final swaps the circuit above does not implement . For and the correct output is , while the unswapped circuit outputs . These are different states, not the same state up to a global phase. The unswapped circuit is a bit-reversed Fourier transform, which is fine only if later steps relabel the wires.
Gate cost and approximate rotations
There are Hadamards, controlled rotations, and swaps. Counting each rotation and swap as one ideal gate gives gates; a swap can instead be decomposed into three CNOT gates. This is a circuit-size count, not a claim that an arbitrary rotation has zero synthesis cost in a fixed finite gate set.
Proposition 2.3.8
(Dropping small rotations)
Let be an integer. Omit every controlled with , keeping all other gates and the final swaps, and call the resulting unitary . For operator norm ,
Proof
(Telescoping over the omitted gates)
Replace omitted gates by identities one at a time. A telescoping sum and unitary invariance of operator norm bound the total difference by the sum of individual gate differences. For a controlled , that difference is . Each target wire loses at most one rotation for each , and the infinite tail is . Summing over at most targets proves the bound.
For any normalized input, the Euclidean norm of the difference of the two output state vectors is bounded by the same quantity. At most controlled rotations remain. Taking makes this bound at most . This estimate concerns ideal retained gates; approximating them over a fixed gate set adds further error that must be accounted for separately.
Measurement is not a classical Fourier table
For a computational-basis input , measuring in the computational basis yields every with probability , since each amplitude has magnitude . This uniformity does not hold for arbitrary inputs: maps the uniform superposition to , which is measured as zero with certainty. The phase information becomes useful through subsequent interference; one measurement does not reveal the entire vector of complex Fourier amplitudes. This observation does not make the transform useless—it identifies what a surrounding algorithm must do with it.
Common mistake
(Reading the output as a table of Fourier coefficients)
After applying the circuit to an unknown state, one measurement returns a single index sampled with probability . It does not return the complex numbers . Obtaining that table would need many repeated preparations, and even then phases are lost. The quadratic gate count therefore does not give a fast classical Fourier transform.
Practice with solutions
Quick check
(For and , write the two factors of in output order.)
Solution · Answer
Here and . The first factor has phase and the second has phase , so .
Quick check
(For , how many controlled rotations and swaps does the exact circuit use?)
Solution · Answer
There are controlled rotations and swap.
Quick check
(Why is a circuit omitting final swaps not literally the stated in the same wire convention?)
Solution · Answer
The output wires carry the Fourier factors in reverse order; swaps or an explicit reinterpretation of bit labels are required.
Quick check
(For and , give the general operator-norm error bound above.)
Solution · Answer
. This bound is vacuous: any two unitaries differ in operator norm by at most , which is smaller than . A larger improves the displayed estimate.