# Fourier transforms and phase estimation {#fourier}

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

## 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.

## 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.

![An exact two-qubit forward QFT in the book’s wire order. The controlled phase contributes i only to the 11 component; the final swap fixes output order.](figures/qft.svg)

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.

::: {.lab #lab-qft}
**Laboratory L16 — Fourier transform.** Prepare a basis state or an editable periodic amplitude pattern. Inspect complex output amplitudes, switch forward/inverse sign, and apply the inverse to verify recovery.
:::

## 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.$$

![Phase estimation with three control qubits. Their powers are 4, 2, and 1 from top to bottom. The inverse QFT converts the kicked-back phase into a binary estimate.](figures/qpe.svg)

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.

::: {.lab #lab-qpe}
**Laboratory L17 — Phase estimation.** Adjust φ and control precision. Inspect the phase-kicked amplitudes, inverse-QFT distribution, sampled estimates, and circular error. Compare exactly representable and nearby phases.
:::

## 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 [@kitaev; @qpe].

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.

## Exercises

:::: {.exercise #ex12-1}
**12.1.** Calculate $F_4|2\rangle$.

::: {.solution}

The phases are $e^{i\pi y}=(-1)^y$, so the amplitudes are $(1,-1,1,-1)/2$.
:::

::::

:::: {.exercise #ex12-2}
**12.2.** What does inverse QFT do to a uniform state?

::: {.solution}

It returns $|0\rangle$, since the sum of all nontrivial roots of unity vanishes.
:::

::::

:::: {.exercise #ex12-3}
**12.3.** For m=4 and $\phi=11/16$, give the certain bit string in our convention.

::: {.solution}

Integer 11 is 1011. The leftmost bit has weight eight.
:::

::::

:::: {.exercise #ex12-4}
**12.4.** How many repeated U applications implement all controlled powers for m=10?

::: {.solution}

$2^{10}-1=1023$, excluding control overhead, preparation, QFT, and repetitions.
:::

::::

:::: {.exercise #ex12-5}
**12.5.** A target is $(|u_0\rangle+|u_1\rangle)/\sqrt2$ with exactly resolvable phases 1/4 and 3/4. What does phase estimation measure?

::: {.solution}

Each phase occurs with probability $1/2$, and the target is conditioned on the associated eigenstate. It does not return their mean phase 1/2.
:::

::::

