CHAPTER 12

Fourier transforms and phase estimation

Learning goals. Calculate a quantum Fourier transform, track bit reversal, derive the phase-estimation distribution, and account for controlled powers.

12.1 The QFT is a unitary change of amplitudes

For $N=2^n$, define

$$F_N|x\rangle=\frac1{\sqrt N}\sum_{y=0}^{N-1} e^{2\pi ixy/N}|y\rangle.$$

The inverse uses the negative sign in the exponent. To verify unitarity, take the overlap of columns x and x’:

$$\frac1N\sum_{y=0}^{N-1}e^{2\pi i(x-x')y/N} =\delta_{xx'}.$$

For x≠x’, the ratio $r=e^{2\pi i(x-x')/N}$ obeys $r^N=1$ but r≠1, so the geometric sum $(1-r^N)/(1-r)$ vanishes.

Worked example.

$$F_4|1\rangle=\frac{|0\rangle+i|1\rangle-|2\rangle-i|3\rangle}{2}.$$

The four probabilities are equal. The transform has encoded x in relative phases. Measuring immediately in Z does not reveal those phases or return a table of classical Fourier coefficients.

For $|\psi\rangle=\sum_xa_x|x\rangle$, the output amplitudes are $b_y=N^{-1/2}\sum_xa_xe^{2\pi ixy/N}$. A QFT circuit can transform a register with O(n²) elementary controlled-phase and Hadamard gates, but generic amplitude loading and complete output readout can cost exponentially in n. Comparing this operation directly with an FFT that writes all N coefficients is an input-output mismatch.

12.2 Building the circuit and tracking order

Write x in binary. Factoring the phase across output bits gives tensor factors with binary-fraction phases. One standard construction applies H to a wire, controlled phase rotations from later wires, repeats down the register, and finally reverses wire order with swaps.

For two qubits in our most-significant-first convention, a forward QFT is: H on $q_0$; controlled phase $\pi/2$ between $q_1$ and $q_0$; H on $q_1$; then SWAP. The controlled phase multiplies only $|11\rangle$ by i. Omitting final swaps implements a bit-reversed output convention, not the exact $F_4$ defined above.

Small controlled rotations can sometimes be omitted for an approximate QFT with a bounded error. A valid approximation statement specifies the norm or algorithmic success criterion, not just the number of gates removed.

12.3 Phase estimation derives a measurable phase

Suppose $U|u\rangle=e^{2\pi i\phi}|u\rangle$, with $0\le\phi<1$. Use an m-qubit control register, $Q=2^m$, prepared uniformly. Controlled powers $U^{2^{m-1-j}}$ act from control wire j under our ordering. Phase kickback gives

$$\frac1{\sqrt Q}\sum_{x=0}^{Q-1}e^{2\pi i\phi x}|x\rangle|u\rangle.$$

Apply $F_Q^\dagger$ to the controls. The amplitude of y is

$$A_y=\frac1Q\sum_{x=0}^{Q-1}e^{2\pi ix(\phi-y/Q)}.$$

If $\phi=k/Q$ exactly, orthogonality gives output y=k with certainty. Otherwise let $\delta=\phi-y/Q$. The geometric sum gives

$$p(y)=|A_y|^2 =\frac{\sin^2(\pi Q\delta)}{Q^2\sin^2(\pi\delta)},$$

using the continuous limiting value one when $\delta$ is an integer. The distribution peaks near y/Q≈φ, including wraparound near zero.

Worked exact phase. Let m=3 and $\phi=3/8=0.011_2$. The phase-kicked control amplitudes are $e^{2\pi i3x/8}/\sqrt8$. Inverse QFT returns integer three, bit string 011. The eigentarget stays in $|u\rangle$.

For a target superposition $\sum_jc_j|u_j\rangle$, linearity creates correlated phase-register and eigenstate branches. Resolvable eigenphases appear with probabilities approximately $|c_j|^2$. Phase estimation does not generally return the expectation of U’s phase; it samples eigencomponents.

12.4 Precision has a physical cost

m control qubits provide grid spacing $2^{-m}$. But the controlled powers collectively use U a total of $1+2+\cdots+2^{m-1}=2^m-1$ times if implemented by repetition. Thus increasing precision is not free because the QFT has only polynomial gate count.

Sometimes controlled powers can be implemented more efficiently using known structure, as in modular arithmetic. For Hamiltonian evolution, long controlled evolution time remains a resource. Iterative phase estimation can reduce simultaneous ancilla qubits by using repeated experiments and feed-forward, but does not remove the fundamental need for sufficient phase information [18, 19].

The eigenphase is only defined modulo one. When converting a Hamiltonian energy E using $U=e^{-iHt}$, $\phi=-Et/(2\pi)$ modulo one. The energy range and evolution time must avoid ambiguity or supply a known offset. A phase estimate without its sign and units is incomplete.

12.5 Exercises