Simple Algorithm
Quantum Computing · Excited State · 24 min

The Quantum Fourier Transform & Phase Estimation

An exponentially fast Fourier transform, and how to use it.

A classical computer needs about n 2nn\,2^n operations to Fourier-transform a list of 2n2^n numbers, even with the fast Fourier transform. A quantum computer applies the same transform to the 2n2^n amplitudes of nn qubits with about n2/2n^2/2 gates. The catch: you cannot read those amplitudes, only sample from them. This lesson shows exactly when that is enough, and builds phase estimation, the engine inside Shor's algorithm.

What you’ll learn

  • Define the quantum Fourier transform on nn qubits and prove that it is unitary.
  • Show that a periodic state is mapped to sharp peaks at multiples of N/rN/r, with the offset hidden in the phases.
  • Derive the product formula and build the QFT from Hadamards and controlled phase rotations with O(n2)\order{n^2} gates.
  • Analyze phase estimation: the role of controlled-U2jU^{2^j}, the exact case, and the output distribution for a general phase.
  • Explain why the QFT does not speed up the Fourier transform of classical data.

The Fourier transform as a unitary

Let N=2nN=2^n and ωN=e2πi/N\omega_N=e^{2\pi i/N}. The quantum Fourier transform is the linear map defined on the computational basis by

FN∣x⟩=1N∑y=0N−1ωNxy∣y⟩,x∈{0,1,…,N−1},F_N\ket{x}=\frac{1}{\sqrt N}\sum_{y=0}^{N-1}\omega_N^{xy}\ket{y},\qquad x\in\{0,1,\dots,N-1\},

where the integer xx is written in binary on nn qubits, qubit 0 (the top wire) holding the most significant bit. On a general state it is the discrete Fourier transform of the amplitude vector: ∑xαx∣x⟩↦∑yα~y∣y⟩\sum_x\alpha_x\ket{x}\mapsto\sum_y\tilde\alpha_y\ket{y} with α~y=1N∑xωNxyαx\tilde\alpha_y=\frac{1}{\sqrt N}\sum_x\omega_N^{xy}\alpha_x.

F4=12(11111i−1−i1−11−11−i−1i)F_4=\frac12\begin{pmatrix}1&1&1&1\\1&i&-1&-i\\1&-1&1&-1\\1&-i&-1&i\end{pmatrix}
For n=2n=2, ω4=i\omega_4=i: row yy, column xx holds ω4xy/2\omega_4^{xy}/2.
DerivationWhy F_N is unitary
  1. ⟨x′∣FN†FN∣x⟩=1N∑y=0N−1ωN(x−x′)y\bra{x'}F_N^\dagger F_N\ket{x}=\frac1N\sum_{y=0}^{N-1}\omega_N^{(x-x')y}

    The columns of FNF_N are the vectors FN∣x⟩F_N\ket{x}; compute their inner products.

  2. ∑y=0N−1ωNky=1−ωNkN1−ωNk=0(k≢0 mod N)\sum_{y=0}^{N-1}\omega_N^{ky}=\frac{1-\omega_N^{kN}}{1-\omega_N^{k}}=0\qquad(k\not\equiv0 \bmod N)

    For k=x−x′≠0k=x-x'\neq0 this is a geometric series whose ratio ωNk≠1\omega_N^k\neq1 is an NN-th root of unity, so it sums to zero.

  3. ⟨x′∣FN†FN∣x⟩=δxx′\bra{x'}F_N^\dagger F_N\ket{x}=\delta_{xx'}

    For k=0k=0 every term is 11, giving N/N=1N/N=1. The columns are orthonormal, so FNF_N is unitary.

Think first What is F2F_2, the QFT on a single qubit? And what is FN∣0⟩F_N\ket{0}?

F2=12(111−1)=HF_2=\tfrac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}=H, the Hadamard gate, because ω2=−1\omega_2=-1. And FN∣0⟩=1N∑y∣y⟩F_N\ket{0}=\tfrac{1}{\sqrt N}\sum_y\ket{y}, the uniform superposition. Every basis state becomes a "plane wave" of equal magnitudes: all of its information sits in the phases.

Periodic states make sharp peaks

The QFT shines on periodic states. Suppose the period rr divides NN and the state is a uniform superposition over one residue class:

∣ψx0⟩=rN∑j=0N/r−1∣x0+jr⟩,0≤x0<r.\ket{\psi_{x_0}}=\sqrt{\frac rN}\sum_{j=0}^{N/r-1}\ket{x_0+jr},\qquad 0\le x_0<r.

In Shor's algorithm a state like this appears with an offset x0x_0 that is random and unknown to you.

DerivationFourier transform of a periodic state
  1. FN∣ψx0⟩=rN∑y=0N−1ωNx0y∑j=0N/r−1e2πi jy/(N/r)∣y⟩F_N\ket{\psi_{x_0}}=\frac{\sqrt r}{N}\sum_{y=0}^{N-1}\omega_N^{x_0y}\sum_{j=0}^{N/r-1}e^{2\pi i\,jy/(N/r)}\ket{y}

    Insert the definition and split ωN(x0+jr)y=ωNx0y e2πi jy/(N/r)\omega_N^{(x_0+jr)y}=\omega_N^{x_0y}\,e^{2\pi i\,jy/(N/r)}.

  2. ∑j=0N/r−1e2πi jy/(N/r)={N/rif y is a multiple of N/r0otherwise\sum_{j=0}^{N/r-1}e^{2\pi i\,jy/(N/r)}=\begin{cases}N/r & \text{if } y \text{ is a multiple of } N/r\\ 0 & \text{otherwise}\end{cases}

    The same geometric-series argument as for unitarity, now with N/rN/r terms.

  3. FN∣ψx0⟩=1r∑s=0r−1e2πi x0s/r∣sN/r⟩F_N\ket{\psi_{x_0}}=\frac{1}{\sqrt r}\sum_{s=0}^{r-1}e^{2\pi i\,x_0s/r}\ket{sN/r}

    Only y=sN/ry=sN/r survives. Each of the rr peaks has probability 1/r1/r, and the offset x0x_0 appears only in the phases.

Predict before you look

Five qubits (N=32N=32), input with period r=8r=8 and some offset. What is the probability of measuring y=12y=12 after the QFT?

Show the answer

12.5 %

The peaks sit at multiples of N/r=4N/r=4, namely 0,4,8,…,280,4,8,\dots,28, and 12=3⋅412=3\cdot4 is one of them. Each of the r=8r=8 peaks has probability 1/8=12.5%1/8=12.5\%, whatever the offset.

Think first What happens when rr does not divide NN?

The peaks no longer sit on integers. Probability concentrates on the integers nearest to sN/rsN/r, with tails that fall off like the inverse square of the distance; the nearest integer to each sN/rsN/r is still hit with probability roughly 4/(π2r)4/(\pi^2r) or more. You get an approximation of s/rs/r, and Shor's algorithm turns it into the exact fraction with continued fractions.

The product formula

Write x=x1x2⋯xnx=x_1x_2\cdots x_n in binary, x=x12n−1+⋯+xn20x=x_12^{n-1}+\dots+x_n2^0, and use binary fractions 0.xjxj+1⋯xn=xj/2+xj+1/4+⋯+xn/2n−j+10.x_jx_{j+1}\cdots x_n=x_j/2+x_{j+1}/4+\dots+x_n/2^{n-j+1}. The QFT of a basis state then factorizes into single-qubit states, which is the key to building it from small gates.

DerivationDeriving the product formula
  1. FN∣x⟩=12n/2∑y1,…,yn∈{0,1}e2πi x∑l=1nyl2−l∣y1⋯yn⟩F_N\ket{x}=\frac{1}{2^{n/2}}\sum_{y_1,\dots,y_n\in\{0,1\}}e^{2\pi i\,x\sum_{l=1}^{n}y_l2^{-l}}\ket{y_1\cdots y_n}

    Expand y/2n=∑lyl2−ly/2^n=\sum_l y_l2^{-l}, with y1y_1 the most significant output bit.

  2. =12n/2⨂l=1n(∣0⟩+e2πi x/2l∣1⟩)=\frac{1}{2^{n/2}}\bigotimes_{l=1}^{n}\Bigl(\ket0+e^{2\pi i\,x/2^{l}}\ket1\Bigr)

    The exponential of a sum is a product, and each factor involves only one yly_l: the sum over bit strings factorizes into a tensor product.

  3. e2πi x/2l=e2πi 0.xn−l+1⋯xne^{2\pi i\,x/2^{l}}=e^{2\pi i\,0.x_{n-l+1}\cdots x_n}

    Only the fractional part of x/2lx/2^l matters, and it consists of the last ll bits of xx.

  4. FN∣x1⋯xn⟩=(∣0⟩+e2πi 0.xn∣1⟩)(∣0⟩+e2πi 0.xn−1xn∣1⟩)⋯(∣0⟩+e2πi 0.x1x2⋯xn∣1⟩)2n/2F_N\ket{x_1\cdots x_n}=\frac{\bigl(\ket0+e^{2\pi i\,0.x_n}\ket1\bigr)\bigl(\ket0+e^{2\pi i\,0.x_{n-1}x_n}\ket1\bigr)\cdots\bigl(\ket0+e^{2\pi i\,0.x_1x_2\cdots x_n}\ket1\bigr)}{2^{n/2}}

    The product formula. Output qubit 1 depends only on xnx_n; output qubit nn depends on every input bit.

Check your understanding

In F8∣110⟩F_8\ket{110} (so x=6x=6), what is the state of the last output qubit, the least significant bit y3y_3?

  1. ∣+⟩\ket{+}
  2. ∣−⟩\ket{-}
  3. ∣+i⟩\ket{+i}
  4. ∣−i⟩\ket{-i}
Show the answer

D. ∣−i⟩\ket{-i}

The last factor has phase e2πi 0.x1x2x3=e2πi 0.110=e2πi⋅3/4=−ie^{2\pi i\,0.x_1x_2x_3}=e^{2\pi i\,0.110}=e^{2\pi i\cdot3/4}=-i, giving 12(∣0⟩−i∣1⟩)=∣−i⟩\tfrac{1}{\sqrt2}(\ket0-i\ket1)=\ket{-i}. Equivalently, the coefficient of y3y_3 in ω86y\omega_8^{6y} is e2πi⋅6/8e^{2\pi i\cdot6/8}.

Building the circuit

Let Rk=(100e2πi/2k)R_k=\begin{pmatrix}1&0\\0&e^{2\pi i/2^k}\end{pmatrix}, so R1=ZR_1=Z, R2=SR_2=S and R3=TR_3=T. A controlled-RkR_k multiplies ∣11⟩\ket{11} by e2πi/2ke^{2\pi i/2^k} and leaves the other basis states alone, so it is symmetric in its two qubits. In the composer below it is a control dot and a phase gate in the same column.

DerivationEach wire builds one factor
  1. H∣x1⟩=12(∣0⟩+e2πi 0.x1∣1⟩)H\ket{x_1}=\tfrac{1}{\sqrt2}\bigl(\ket0+e^{2\pi i\,0.x_1}\ket1\bigr)

    Because e2πi 0.x1=(−1)x1e^{2\pi i\,0.x_1}=(-1)^{x_1}.

  2. → C-R2 from x2 12(∣0⟩+e2πi 0.x1x2∣1⟩)\xrightarrow{\ C\text{-}R_2 \text{ from } x_2\ }\tfrac{1}{\sqrt2}\bigl(\ket0+e^{2\pi i\,0.x_1x_2}\ket1\bigr)

    Controlled on x2x_2, the rotation R2R_2 adds x2/4x_2/4 to the binary fraction.

  3. → C-R3,…,C-Rn 12(∣0⟩+e2πi 0.x1x2⋯xn∣1⟩)\xrightarrow{\ C\text{-}R_3,\dots,C\text{-}R_n\ }\tfrac{1}{\sqrt2}\bigl(\ket0+e^{2\pi i\,0.x_1x_2\cdots x_n}\ket1\bigr)

    After n−1n-1 controlled rotations, wire 1 holds the last factor of the product formula. The control wires are untouched and still in basis states.

  4. wire j: H, then C-R2,…,C-Rn−j+1 ⟹ 12(∣0⟩+e2πi 0.xj⋯xn∣1⟩)\text{wire } j:\ H,\ \text{then } C\text{-}R_2,\dots,C\text{-}R_{n-j+1}\ \Longrightarrow\ \tfrac{1}{\sqrt2}\bigl(\ket0+e^{2\pi i\,0.x_j\cdots x_n}\ket1\bigr)

    Repeat for each wire in turn. Wire jj needs controls only from the wires below it, which have not been touched yet.

  5. SWAP  j↔n+1−j\text{SWAP}\ \ j\leftrightarrow n+1-j

    The wires now hold the factors in reverse order. Final swaps (or simply relabeling the wires) put them in place.

GateNumber in F2nF_{2^n}For n=3n=3
Hadamardnn3
Controlled-RkR_kn(n−1)/2n(n-1)/23
SWAP⌊n/2⌋\lfloor n/2\rfloor1
TotalO(n2)\order{n^2}7
python
from math import pi
from qiskit import QuantumCircuit

def qft(n: int) -> QuantumCircuit:
    """QFT with qubit 0 as the most significant bit (this course's convention)."""
    qc = QuantumCircuit(n)
    for j in range(n):
        qc.h(j)
        for k in range(2, n - j + 1):
            qc.cp(2 * pi / 2**k, j + k - 1, j)   # controlled-R_k: control j+k-1, target j
    for j in range(n // 2):
        qc.swap(j, n - 1 - j)
    return qc

Qiskit numbers qubits little-endian (qubit 0 is the least significant bit), so compare this with its library QFT only after accounting for the wire order.

Phase estimation

Here is the most important use of the QFT. A unitary UU has an eigenstate ∣u⟩\ket{u} with U∣u⟩=e2πiφ∣u⟩U\ket{u}=e^{2\pi i\varphi}\ket{u}, and you want the phase φ∈[0,1)\varphi\in[0,1). You are given ∣u⟩\ket{u} and may apply controlled-U2jU^{2^j}. Recall phase kickback: a controlled-UU acting on ∣+⟩∣u⟩\ket{+}\ket{u} leaves ∣u⟩\ket{u} alone and writes the eigenvalue onto the control, 12(∣0⟩+e2πiφ∣1⟩)∣u⟩\tfrac{1}{\sqrt2}(\ket0+e^{2\pi i\varphi}\ket1)\ket u.

DerivationPhase estimation with t counting qubits
  1. ∣0⟩⊗t∣u⟩ →H⊗t 12t/2∑k=02t−1∣k⟩∣u⟩\ket{0}^{\otimes t}\ket{u}\ \xrightarrow{H^{\otimes t}}\ \frac{1}{2^{t/2}}\sum_{k=0}^{2^t-1}\ket{k}\ket{u}

    Put the tt-qubit counting register into uniform superposition.

  2. 12t/2∑k=02t−1∣k⟩ Uk∣u⟩=12t/2∑k=02t−1e2πiφk∣k⟩∣u⟩\frac{1}{2^{t/2}}\sum_{k=0}^{2^t-1}\ket{k}\,U^k\ket{u}=\frac{1}{2^{t/2}}\sum_{k=0}^{2^t-1}e^{2\pi i\varphi k}\ket{k}\ket{u}

    Counting qubit jj (top =1=1) controls U2t−jU^{2^{t-j}}. Together they apply UkU^k with k=∑jkj2t−jk=\sum_jk_j2^{t-j}, and the eigenvalue kicks back the phase e2πiφke^{2\pi i\varphi k}.

  3. φ=m2t ⟹ 12t/2∑ke2πi mk/2t∣k⟩=F2t∣m⟩\varphi=\frac{m}{2^t}\ \Longrightarrow\ \frac{1}{2^{t/2}}\sum_ke^{2\pi i\,mk/2^t}\ket{k}=F_{2^t}\ket{m}

    If φ\varphi has an exact tt-bit binary expansion, the counting register is exactly the Fourier transform of ∣m⟩\ket{m}.

  4. F2t† ⟹ ∣m⟩=∣φ1φ2⋯φt⟩F_{2^t}^\dagger\ \Longrightarrow\ \ket{m}=\ket{\varphi_1\varphi_2\cdots\varphi_t}

    The inverse QFT returns m=2tφm=2^t\varphi with certainty.

  5. P(m)=14t∣∑k=02t−1e2πikδm∣2=sin⁡2(π2tδm)4tsin⁡2(πδm),δm=φ−m2tP(m)=\frac{1}{4^{t}}\Bigl|\sum_{k=0}^{2^t-1}e^{2\pi i k\delta_m}\Bigr|^2=\frac{\sin^2(\pi2^t\delta_m)}{4^t\sin^2(\pi\delta_m)},\qquad\delta_m=\varphi-\frac{m}{2^t}

    In general the output is spread over mm, sharply peaked at the tt-bit values nearest to φ\varphi.

Check your understanding

You run phase estimation on the input 12(∣u1⟩+∣u2⟩)\tfrac{1}{\sqrt2}(\ket{u_1}+\ket{u_2}), where ∣u1⟩,∣u2⟩\ket{u_1},\ket{u_2} are eigenstates with distinct phases φ1,φ2\varphi_1,\varphi_2 that are exact tt-bit numbers. What does the counting register read?

  1. An estimate of the average (φ1+φ2)/2(\varphi_1+\varphi_2)/2
  2. φ1\varphi_1 or φ2\varphi_2, each with probability 12\tfrac12
  3. Always φ1\varphi_1, the phase of the first term
  4. Nothing useful: phase estimation requires an exact eigenstate
Show the answer

B. φ1\varphi_1 or φ2\varphi_2, each with probability 12\tfrac12

By linearity the final state is 12(∣φ1⟩∣u1⟩+∣φ2⟩∣u2⟩)\tfrac{1}{\sqrt2}(\ket{\varphi_1}\ket{u_1}+\ket{\varphi_2}\ket{u_2}). The work-register states are orthogonal, so measuring the counting register gives φ1\varphi_1 or φ2\varphi_2 with probability 12\tfrac12 each, and the work register collapses to the matching eigenstate. Shor's algorithm relies on exactly this.

What the QFT buys you

ProblemUnitary UUThe eigenphase reveals
Order finding (Shor)∣y⟩↦∣ay mod N⟩\ket y\mapsto\ket{ay \bmod N}s/rs/r, and from it the order rr of aa modulo NN
Quantum countingthe Grover iteratean angle θ\theta with sin⁡2(θ/2)=M/N\sin^2(\theta/2)=M/N, the fraction of marked items
Energy estimatione−iHτe^{-iH\tau}an eigenvalue EE of the Hamiltonian, via φ=−Eτ/2π mod 1\varphi=-E\tau/2\pi \bmod 1
Discrete logarithms (Shor)multiplication by gg and hh on two registersthe exponent ℓ\ell in h=gℓh=g^\ell

Next, Shor's Factoring Algorithm applies phase estimation to modular multiplication and uses continued fractions to turn the estimate of s/rs/r into the exact period.

Key takeaways

  • FN∣x⟩=N−1/2∑yωNxy∣y⟩F_N\ket x=N^{-1/2}\sum_y\omega_N^{xy}\ket y is unitary. A state with period r∣Nr\mid N becomes rr equal peaks at multiples of N/rN/r; the offset survives only as phases.
  • The product formula gives a circuit of nn Hadamards, n(n−1)/2n(n-1)/2 controlled rotations and ⌊n/2⌋\lfloor n/2\rfloor swaps: O(n2)\order{n^2} gates versus O(n2n)\order{n2^n} for the FFT, but acting on amplitudes.
  • Phase estimation: H⊗tH^{\otimes t}, controlled-U2jU^{2^j}, then F†F^\dagger. An exact tt-bit phase is read with certainty; otherwise the nearest tt-bit value has probability at least 4/π24/\pi^2.
  • A superposition of eigenstates yields one eigenphase at random, with probability equal to its squared amplitude: the engine of Shor's algorithm.
  • The QFT does not speed up Fourier transforms of classical data; input loading and readout dominate.

Check yourself

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

Question 1

How many controlled phase rotations does the textbook QFT circuit on n=10n=10 qubits contain?

  1. 10
  2. 45
  3. 90
  4. 1024
Show the answer

B. 45

Wire jj receives n−jn-j controlled rotations, so the total is ∑j=1n(n−j)=n(n−1)/2=45\sum_{j=1}^{n}(n-j)=n(n-1)/2=45.

Question 2

N=64N=64. The input is the uniform superposition over all x≡5(mod16)x\equiv5\pmod{16}. Which outcomes can a measurement after the QFT return?

  1. Only y=5y=5
  2. Multiples of 16
  3. y≡5(mod16)y\equiv5\pmod{16}
  4. Multiples of 4
Show the answer

D. Multiples of 4

The period is r=16r=16, so the peaks sit at multiples of N/r=4N/r=4, each with probability 1/161/16. The offset 5 changes only the phases.

Question 3

You run phase estimation with t=3t=3 counting qubits on U=TU=T and its eigenstate ∣1⟩\ket1. What does the counting register read?

  1. ∣001⟩\ket{001} with certainty
  2. ∣100⟩\ket{100} with certainty
  3. ∣001⟩\ket{001} with probability about 0.810.81
  4. A uniformly random 3-bit string
Show the answer

A. ∣001⟩\ket{001} with certainty

T∣1⟩=eiπ/4∣1⟩=e2πi⋅(1/8)∣1⟩T\ket1=e^{i\pi/4}\ket1=e^{2\pi i\cdot(1/8)}\ket1, so φ=1/8=0.0012\varphi=1/8=0.001_2. A phase with an exact 3-bit expansion is returned with certainty: m=23φ=1m=2^3\varphi=1.

Question 4

Why does the QFT not give an exponential speedup for the discrete Fourier transform of a classical list of N=2nN=2^n numbers?

  1. The QFT circuit needs O(Nlog⁡N)\order{N\log N} gates, like the FFT
  2. The QFT computes a different transform from the DFT
  3. Loading NN arbitrary numbers into amplitudes and reading out NN amplitudes each cost Ω(N)\Omega(N) operations or samples in general
  4. Quantum gates are slower than classical operations
Show the answer

C. Loading NN arbitrary numbers into amplitudes and reading out NN amplitudes each cost Ω(N)\Omega(N) operations or samples in general

The transform itself is cheap, O(n2)\order{n^2} gates. Input and output are the bottleneck: amplitudes are not directly readable, and preparing a generic NN-dimensional state is costly.

Question 5

In phase estimation with a generic phase φ\varphi, what does one extra counting qubit do?

  1. Doubles the probability of the most likely outcome
  2. Halves the grid spacing 2−t2^{-t}, and doubles the total number of controlled-UU applications
  3. Nothing, unless φ\varphi has an exact binary expansion
  4. Adds a second eigenphase to the output
Show the answer

B. Halves the grid spacing 2−t2^{-t}, and doubles the total number of controlled-UU applications

The estimate lives on a grid of spacing 2−t2^{-t}, so precision doubles. The new top qubit controls U2tU^{2^{t}}, so the total count of UU applications, 2t+1−12^{t+1}-1, roughly doubles too.

Go deeper

Further reading

  • M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, ch. 5 (Cambridge, 10th anniv. ed., 2010).
  • R. Cleve, A. Ekert, C. Macchiavello & M. Mosca, "Quantum algorithms revisited", Proc. R. Soc. Lond. A 454, 339 (1998).
  • A. Yu. Kitaev, "Quantum measurements and the Abelian stabilizer problem", arXiv:quant-ph/9511026 (1995).
  • D. Coppersmith, "An approximate Fourier transform useful in quantum factoring", IBM Research Report RC19642 (1994); arXiv:quant-ph/0201067.