7 The quantum Fourier transform

This chapter introduces the quantum Fourier transform (QFT) as a foundational primitive in quantum computing and a key ingredient in algorithms such as Shor’s factoring and quantum phase estimation. At a high level, the QFT converts information encoded in the phases of a quantum state into magnitudes that can be learned by measurement, leveraging interference and quantum parallelism for efficiency. The text frames QFT as the quantum analogue of the discrete Fourier transform (DFT), highlighting how both transforms expose periodic structure, and emphasizes that the QFT and its inverse (IQFT) are efficient, compact circuit constructions central to achieving quantum speedups.

To build intuition, the chapter begins with periodic signals, sinusoids, and the classical DFT, using familiar examples from audio to show how complex waveforms decompose into frequency components. It then translates these ideas to quantum states, encoding periodic patterns via complex sinusoids with uniform magnitudes and systematically advancing phases—so-called geometric sequence states. Roots of unity and Fourier bases are presented as the mathematical backbone of these encodings. A single-qubit example shows the essence of “phase-to-magnitude” conversion: after phase encoding, a Hadamard gate maps phase differences to measurable probability differences, revealing the encoded angle. This simple case anticipates the structure of multi-qubit QFTs, where Hadamards and controlled phase rotations generalize this conversion.

Bridging classical and quantum perspectives, the chapter defines the QFT/IQFT as inner products with Fourier bases (with 1/√N normalization) and demonstrates classical simulations that mirror their action. It then presents the gate-based implementations built from layered Hadamards and controlled phase rotations, optionally followed by swaps or bit-order reversal, and contrasts their quadratic gate complexity in the number of qubits with the exponential-in-digit-cost of classical FFT when N = 2^n. Conceptually, the QFT maps computational basis states to geometric sequence (Fourier) states whose “frequency” equals the basis index, while the IQFT recovers that frequency, revealing bits step-by-step through successive Hadamards and phase un-rotations. Practical circuit notes—like control/target symmetry for controlled-phase gates and when final swaps are unnecessary—round out the implementation-focused treatment.

A dependency diagram of concepts introduced in this chapter.

A simple sinusoidal wave, \(\sin (x) \text{ for } -2\pi \le x \le 2\pi\).

The sinusoidal wave, \(\sin (x)\) for real values \(x\), has amplitude 1, phase 0, and frequency 1.

The sine and cosine waves plotted together.

Visualization of the signal with the 8 discrete values.

Projections of the sine and cosine parts of a complex sinusoid.

Table 7.1 The geometric sequence state for an angle \(\theta\).

Unit color wheel representation of the geometric sequence state for \(\theta = \frac{\pi}{3}\).

Unit color wheel for the geometric sequence state for \(\theta = \frac{\pi}{6}\).

Table 7.2 The 3-qubit geometric sequence state for \(v = 1.7\).

Phase encoding for a single qubit with \(\theta = \frac{\pi}{3}\).

Converting difference in phase (\(\theta = \frac{\pi}{3}\)) to difference in magnitudes.

Conversion from phase to magnitude encoding in a single-qubit state with a Hadamard gate.

Table 7.3 Fourier bases \(n\)-qubit quantum state where \(N = 2^n\), \(0 \le k < N\), and \(0 \le l < N\).

The general form of the amplitudes of a quantum state before and after applying an inverse Fourier transform to it.

The general form of a quantum state before and after a quantum Fourier transform.

The Fourier transforms of the computational bases for a three-qubit system.

A relative comparison of the operations required to compute the QFT and the FFT for a growing number of qubits or binary digits.

Circuit diagram of the QFT on a 4-qubit system.

Circuit diagram of the IQFT on a 4-qubit system.

The first step of the IQFT on a four-qubit state, where a Hadamard gate is applied to the qubit in position 3, followed by three controlled phase rotations.

The second step of the IQFT on a four-qubit state, where a Hadamard gate is applied to the qubit in position 2, followed by two controlled phase rotations.

The third step of the IQFT on a four-qubit state, where a Hadamard gate is applied to the qubit in position 1, followed by one controlled phase rotation.

The fourth step of the IQFT on a four-qubit state, where a Hadamard gate is applied to the qubit in position 0.

• The QFT is essential in many quantum algorithms. The QFT can convert information stored in the phase of a quantum state to magnitudes. It can also help us efficiently prepare states, like the geometric sequence with a certain frequency.
• We learned we can represent periodic patterns in quantum states with real amplitudes or complex.

• The inner product of two state vectors captures their similarity.
• The QFT converts a quantum state into another quantum state consisting of the inner products of the original state with Fourier bases (conjugated).

FAQ