Quantum Fourier transform: Finding hidden periods

In 1807 Joseph Fourier claimed, studying the propagation of heat, that any function can be written as a sum of sines and cosines. Two centuries later the discrete version of his idea is everywhere: compressing images, filtering audio, multiplying large numbers. In 1965 James Cooley and John Tukey rediscovered the fast Fourier transform (FFT), which computes the transform of $N$ numbers in $O (N \log N)$ operations. The quantum version is exponentially faster still, with a catch that we will have to learn to get around.

The discrete and the quantum transform

Let $N = 2^{n}$ and $ω = e^{2 π i / N}$ , a primitive $N$ -th root of unity. The quantum Fourier transform is the linear map defined on the computational basis by

QFT | j ⟩ = \frac{1}{\sqrt{N}} \sum_{k = 0}^{N - 1} ω^{j k} | k ⟩, j = 0, \dots, N - 1 .

Applied to a state $\sum_{j} x_{j} | j ⟩$ , it produces the discrete Fourier transform of the amplitudes, $\sum_{k} y_{k} | k ⟩$ with $y_{k} = \frac{1}{\sqrt{N}} \sum_{j} ω^{j k} x_{j}$ .

Proposition (the QFT is unitary)

The columns of the QFT matrix are orthonormal, so it is a valid quantum gate.

Proof

The inner product of columns $j$ and $j^{'}$ is $\frac{1}{N} \sum_{k = 0}^{N - 1} ω^{(j^{'} - j) k}$ . If $j = j^{'}$ it is 1. Otherwise $q = ω^{j^{'} - j} \neq 1$ is an $N$ -th root of unity and the geometric sum $\sum_{k} q^{k} = \frac{q^{N} - 1}{q - 1} = 0$ .

For $N = 2$ , the QFT is exactly the Hadamard gate. And applying $H$ to each of $n$ qubits is the Fourier transform over the group $(ℤ_{2})^{n}$ : the Deutsch–Jozsa algorithm was already a Fourier transform in disguise.

An exponentially small circuit

The key to its efficiency is that the QFT of a basis state does not create entanglement: it factorizes into $n$ separate qubits. Write $j$ in binary as $j = j_{1} j_{2} \dots j_{n}$ and $0 . j_{l} j_{l + 1} \dots j_{n}$ for the binary fraction $\sum_{m \geq l} j_{m} 2^{l - m - 1}$ .

Theorem (product representation)

QFT | j_{1} \dots j_{n} ⟩ = \frac{(| 0 ⟩ + e^{2 π i 0 . j_{n}} | 1 ⟩) \otimes (| 0 ⟩ + e^{2 π i 0 . j_{n - 1} j_{n}} | 1 ⟩) \otimes \dots \otimes (| 0 ⟩ + e^{2 π i 0 . j_{1} j_{2} \dots j_{n}} | 1 ⟩)}{2^{n / 2}} .

Proof sketch

Write $k = \sum_{l = 1}^{n} k_{l} 2^{n - l}$ . Then $ω^{j k} = \prod_{l} e^{2 π i j k_{l} / 2^{l}}$ , and the sum over $k$ factors into a product of sums over each bit $k_{l} \in {0, 1}$ . In $e^{2 π i j / 2^{l}}$ only the last $l$ bits of $j$ matter, because the others contribute integer multiples of $2 π i$ .

Each factor is prepared with a Hadamard gate and a few controlled phase rotations, $R_{k} = diag (1, e^{2 π i / 2^{k}})$ . In total $n (n + 1) / 2$ gates, plus a reversal of the order of the qubits: $O (n^{2})$ operations to transform $2^{n}$ amplitudes, against the FFT's $O (n 2^{n})$ . Coppersmith (1994) also showed that the smallest rotations can be dropped without significant loss, leaving $O (n \log n)$ gates.

Periodicity becomes peaks

That is exactly what happens with periodic states, the situation that matters for Shor's algorithm.

Theorem (transform of a periodic state)

Let $r$ divide $N$ and $m = N / r$ . The state that is uniform over an arithmetic progression of step $r$ ,

| ψ ⟩ = \frac{1}{\sqrt{m}} \sum_{s = 0}^{m - 1} | x_{0} + s r ⟩,

is transformed into a uniform superposition over the multiples of $m$ : measuring after the QFT gives $k = ℓ N / r$ with $ℓ$ uniform in ${0, \dots, r - 1}$ , whatever the offset $x_{0}$ .

Proof

The amplitude of $| k ⟩$ is $\frac{1}{\sqrt{N m}} ω^{x_{0} k} \sum_{s = 0}^{m - 1} {(ω^{r k})}^{s}$ . Now $ω^{r k} = e^{2 π i k / m}$ is an $m$ -th root of unity. If $m$ divides $k$ it equals 1 and the sum is $m$ , which gives probability $\frac{m^{2}}{N m} = \frac{1}{r}$ . Otherwise the geometric sum is 0. The offset only contributes the phase $ω^{x_{0} k}$ , which does not change the probabilities.

A state on 6 qubits (

N = 64

) that is uniform over a progression with period

r

(top) and its quantum Fourier transform (bottom, colours = phase). When

r

divides 64 the output is a perfect comb of

r

peaks separated by

64 / r

. When it does not, the peaks blur a little but stay near the multiples of

64 / r

, enough to recover

r

, as Shor's algorithm will do. Moving the offset changes only the phases.

Hidden structure in a single query

The same idea gave the first separations between quantum and classical computation, in the model where a function $f$ can only be consulted as a black box.

Bernstein–Vazirani (1993). Let $f (x) = s \cdot x mod 2$ for a secret string $s \in {0, 1}^{n}$ . Classically, each query reveals at most one bit of information about $s$ , so $n$ queries are needed. Quantumly, a single one is enough: prepare $H^{\otimes n} | 0 ⟩$ , apply the oracle as a phase $(- 1)^{s \cdot x}$ , and apply $H^{\otimes n}$ again. Since $H^{\otimes n} \sum_{x} (- 1)^{s \cdot x} | x ⟩ = 2^{n / 2} | s ⟩$ , measuring yields $s$ with certainty.

The Bernstein–Vazirani problem. Choose a secret string. The classical strategy queries

f

e_{1}, e_{2}, \dots

, one bit per query; the quantum circuit asks once, with every input in superposition, and the interference of the phases

(- 1)^{s \cdot x}

leaves exactly

| s ⟩

Simon (1994). If $f (x) = f (y)$ exactly when $y = x$ or $y = x \oplus s$ , finding $s$ requires $Ω (2^{n / 2})$ queries for any classical algorithm, even a randomized one, and $O (n)$ for a quantum one: the first exponential separation against randomized algorithms. Daniel Simon's paper is what inspired Peter Shor.

Phase estimation

Alexei Kitaev (1995) reformulated these ideas into a general tool. Suppose a unitary $U$ and one of its eigenvectors $| u ⟩$ with $U | u ⟩ = e^{2 π i φ} | u ⟩$ . Using $t$ auxiliary qubits, the gates controlled- $U^{2^{j}}$ write the phase $φ$ into the amplitudes as $\frac{1}{2^{t / 2}} \sum_{y} e^{2 π i φ y} | y ⟩$ , and an inverse QFT turns it into a binary number.

Theorem (phase estimation)

With $t$ qubits, the measurement returns the closest $t$ -bit approximation to $φ$ with probability at least $4 / π^{2} \approx 0.405$ ; with $t + O (\log (1 / ε))$ qubits, an approximation to $t$ bits with probability at least $1 - ε$ . If $φ$ has an exact $t$ -bit expansion, the result is certain.

Phase estimation is at the heart of Shor's algorithm, of quantum chemistry (estimating energies, the eigenvalues of a Hamiltonian) and of the algorithms for linear systems. The next chapter puts it to work on the problem that made quantum computing famous.

References

J. W. Cooley and J. W. Tukey (1965). “An Algorithm for the Machine Calculation of Complex Fourier Series”. Mathematics of Computation, 19(90).
E. Bernstein and U. Vazirani (1993). “Quantum complexity theory”. STOC.
D. R. Simon (1994). “On the power of quantum computation”. FOCS (journal version: SIAM J. Computing, 1997).
D. Coppersmith (1994). “An approximate Fourier transform useful in quantum factoring”. IBM Research Report RC19642.
A. Y. Kitaev (1995). “Quantum measurements and the Abelian Stabilizer Problem”. arXiv:quant-ph/9511026.
R. Cleve, A. Ekert, C. Macchiavello and M. Mosca (1998). “Quantum algorithms revisited”. Proceedings of the Royal Society A, 454.

§The discrete and the quantum transform

§An exponentially small circuit

§Periodicity becomes peaks

§Hidden structure in a single query

§Phase estimation