Quantum Mathematics Learning Guide 9: Quantum Fourier Transform, Roots of Unity and Interference

The Quantum Fourier Transform is the discrete Fourier transform written as a unitary map on quantum amplitudes. Its power comes from roots of unity, orthogonality and interference—not from magically reading every Fourier coefficient at once.

The first eight Quantum Mathematics guides built the state, operator, tensor-product, open-system and information layers. This ninth guide begins the algorithmic layer. We will construct the Quantum Fourier Transform from first principles, connect it to complex roots of unity, prove its unitarity, factor it into simple gates and see why periodic phase structure becomes concentrated measurement probability after interference.

Complex phase → roots of unity → Fourier basis → interference → concentrated information.

1. Start with the ordinary discrete Fourier transform

For a length-N complex vector x=(x_0,...,x_{N-1}), the discrete Fourier transform produces coefficients

X_y=(1/√N)Σ_{x=0}^{N-1} x_x e^{2πixy/N}.

The normalising factor 1/√N is chosen here so that the transform is unitary. Classical signal processing often distributes normalisation differently between the forward and inverse transforms; quantum mechanics needs the transformation itself to preserve norm.

2. The root of unity that organises the transform

Define the primitive Nth root of unity

ω_N=e^{2πi/N}.

Then ω_N^N=1, and the Fourier phase can be written ω_N^{xy}. As x or y changes, these powers move around the unit circle. Their geometric cancellation properties are exactly what make Fourier orthogonality work.

Worked example: fourth roots of unity

For N=4, ω_4=e^{2πi/4}=i. Its powers are

• ω_4^0=1
• ω_4^1=i
• ω_4^2=-1
• ω_4^3=-i
• ω_4^4=1

These four equally spaced points on the unit circle form the phase vocabulary of the four-dimensional Fourier transform.

3. Geometric sums create orthogonality

The key identity is

Σ_{x=0}^{N-1} ω_N^{kx} = N if k≡0 mod N, and 0 otherwise.

When k is not divisible by N, this is a finite geometric series with ratio r=ω_N^k≠1. Since r^N=1,

1+r+...+r^{N-1}=(1-r^N)/(1-r)=0.

This exact cancellation is the algebraic engine behind the Fourier basis.

4. Define the Quantum Fourier Transform

On the N computational basis states |0⟩,...,|N-1⟩, define

QFT_N|x⟩=(1/√N)Σ_{y=0}^{N-1}e^{2πixy/N}|y⟩.

Equivalently,

QFT_N|x⟩=(1/√N)Σ_y ω_N^{xy}|y⟩.

By linearity, this determines the transform of every state vector in the N-dimensional Hilbert space.

5. Matrix form

The matrix entries are

F_{y,x}=(1/√N)ω_N^{xy}.

For N=4,

F_4=(1/2)[[1,1,1,1],[1,i,-1,-i],[1,-1,1,-1],[1,-i,-1,i]].

Every entry has magnitude 1/2; the information lies in the phase pattern.

6. Worked basis examples for N=4

The four basis states transform as follows:

• |0⟩ → (1/2)(|0⟩+|1⟩+|2⟩+|3⟩)
• |1⟩ → (1/2)(|0⟩+i|1⟩-|2⟩-i|3⟩)
• |2⟩ → (1/2)(|0⟩-|1⟩+|2⟩-|3⟩)
• |3⟩ → (1/2)(|0⟩-i|1⟩-|2⟩+i|3⟩)

All four outputs have uniform computational-basis probabilities. They are distinguished entirely by relative phase.

7. Why the QFT is unitary

Take two Fourier-transformed basis states originating from x and x’. Their inner product is

(1/N)Σ_y ω_N^{(x'-x)y}.

If x=x', the sum is N and the inner product is one. If x≠x' modulo N, the root-of-unity sum vanishes. Therefore the transformed basis vectors are orthonormal.

A linear map that sends an orthonormal basis to an orthonormal basis is unitary. Thus F_N†F_N=I.

QFT unitarity is root-of-unity orthogonality written as linear algebra.

8. The inverse transform

Because the QFT is unitary,

QFT_N^{-1}=QFT_N†.

The inverse therefore changes the phase sign:

QFT_N^{-1}|y⟩=(1/√N)Σ_x e^{-2πixy/N}|x⟩.

This inverse transform will become the decisive final step of quantum phase estimation in Guide 10.

9. Uniform superposition and exact concentration

Let

|s⟩=(1/√N)Σ_x|x⟩.

This is exactly QFT_N|0⟩. Therefore

QFT_N^{-1}|s⟩=|0⟩.

A completely spread amplitude distribution can therefore become a single basis state when the phases line up correctly under the inverse transform. This is the clearest small example of interference concentrating probability.

10. Periodic structure and Fourier peaks

Suppose an amplitude pattern repeats with some period r. Fourier analysis converts translation periodicity into concentration around reciprocal frequencies. Quantum algorithms exploit the same mathematics, except the periodic information is stored in amplitudes and must be arranged so that measurement samples useful Fourier locations.

Worked example: period two in N=4

Take

|ψ⟩=(|0⟩+|2⟩)/√2.

The QFT amplitude for y is proportional to

1+e^{2πi(2)y/4}=1+(-1)^y.

For odd y the two contributions cancel. For even y they reinforce. Hence

QFT_4|ψ⟩=(|0⟩+|2⟩)/√2.

The Fourier distribution exposes reciprocal period structure through exact interference.

11. The n-qubit case

For n qubits, N=2^n. Write the computational basis integer x in binary:

x=x_1x_2...x_n.

The QFT can be factorised into a tensor product of single-qubit phase states, up to reversal of qubit order:

QFT|x_1...x_n⟩=(1/2^{n/2})(|0⟩+e^{2πi0.x_n}|1⟩)⊗...⊗(|0⟩+e^{2πi0.x_1...x_n}|1⟩).

Here binary fractions such as 0.x_jx_{j+1}... encode phase angles. This factorisation explains the standard gate decomposition.

12. Hadamards and controlled phase rotations

The standard QFT circuit uses Hadamard gates and controlled phase rotations. Define

R_k=diag(1,e^{2πi/2^k}).

A Hadamard creates an equal two-way superposition. Controlled R_k gates attach progressively smaller phase corrections according to lower-significance input bits. The final qubit order is reversed, so swap gates are commonly included.

13. Two-qubit circuit structure

For two qubits, one standard decomposition is:

1. Apply H to the most significant qubit.
2. Apply a controlled phase R_2 from the second qubit.
3. Apply H to the second qubit.
4. Swap the two output qubits.

Different circuit diagrams may reverse indexing conventions, but they represent the same transform when the bit ordering is handled consistently.

14. Exact gate count and approximation

The textbook n-qubit QFT uses O(n²) one- and two-qubit gates, dominated by controlled phase rotations. Rotations with very small angles contribute progressively less to many tasks, so approximate QFT circuits omit sufficiently tiny rotations and reduce depth while introducing controlled error.

This is a recurring engineering pattern: preserve the mathematical structure that materially affects the final measurement while discarding operations below the required precision threshold.

15. QFT is not the same computational object as FFT

The classical Fast Fourier Transform takes a list of N numbers and explicitly outputs N Fourier coefficients, using roughly O(N log N) arithmetic operations. The QFT transforms amplitudes of a quantum state using a circuit polynomial in log₂N.

But the quantum circuit does not hand us all N transformed amplitudes as classical data. Measurement returns a sample. Quantum algorithms gain an advantage only when later interference and measurement extract a small amount of useful global structure without requiring the full coefficient list to be read out.

Fast state transformation is not the same as fast classical readout of every transformed coefficient.

16. Phase gradients

A Fourier basis state has amplitudes with a constant phase increment from one computational basis index to the next. For input x, the y-dependent phase is

2πxy/N.

As y increases by one, the phase increases by 2πx/N. Thus x can be interpreted as a discrete phase gradient across the basis. The inverse QFT converts this structured phase ramp back into the label x when the gradient matches the Fourier grid exactly.

17. Worked example: inverse QFT reads an exact phase ramp

For N=4, consider

|φ⟩=(1/2)(|0⟩+i|1⟩-|2⟩-i|3⟩).

This is exactly QFT_4|1⟩. Therefore

QFT_4^{-1}|φ⟩=|1⟩.

The phase pattern has been converted into a computational-basis label. Quantum phase estimation generalises this idea by first manufacturing a phase ramp from controlled powers of a unitary.

18. Fourier resolution

With N Fourier bins, exact grid phases are separated by increments of 1/N in cycles. A phase that lies between grid points does not concentrate perfectly into one basis state. Instead, its probability spreads into nearby outcomes according to a finite geometric-sum profile.

This is not a failure of the transform. It is finite resolution. Increasing the number of qubits increases N and therefore refines the phase grid.

19. Interference is global addition of complex amplitudes

Every Fourier output amplitude is a sum of many complex contributions. When phases align, contributions reinforce. When they wrap symmetrically around the unit circle, they cancel. Quantum algorithms use this same arithmetic deliberately.

The language “constructive and destructive interference” is therefore not metaphorical. It is literal vector addition in the complex plane.

20. Common misconception: the QFT searches all frequencies and tells us the answer

The QFT performs a unitary basis change. Whether its measurement outcomes reveal useful structure depends entirely on the state entering it. A poorly prepared input can produce an uninformative distribution. The algorithmic work often lies in encoding the desired global structure into relative phase before the transform.

21. Common misconception: Fourier amplitudes are probabilities

They are complex amplitudes. Probabilities arise only after squared magnitudes are taken. Relative phase among Fourier components remains essential until measurement.

22. Common misconception: the QFT gives exponential speedup by itself

A fast QFT circuit is an important primitive, but a useful quantum algorithm needs more: efficient state preparation, a problem structure that becomes measurable after Fourier processing, and an output that can be extracted without reconstructing exponentially many amplitudes.

23. Worked synthesis problem

Let N=8 and consider the periodic state

|ψ⟩=(1/2)(|0⟩+|2⟩+|4⟩+|6⟩).

Step 1: Identify the period. Basis support repeats every 2.

Step 2: Compute a Fourier amplitude. For output y, the phase sum is

1+ω_8^{2y}+ω_8^{4y}+ω_8^{6y}.

This is a four-term geometric series in ω_8^{2y}=e^{2πiy/4}.

Step 3: Find surviving y. The sum is non-zero only when y≡0 mod 4, so only y=0 and y=4 survive.

Step 4: Normalise. The output is

(|0⟩+|4⟩)/√2.

Interpretation. A spacing-2 pattern in the input becomes spacing-4 Fourier support. Periodic structure has moved into reciprocal structure.

24. Practice set

1. Define ω_N.
2. Evaluate 1+i-1-i and explain its Fourier significance.
3. Write QFT_N|x⟩.
4. Write QFT_N^{-1}|y⟩.
5. Compute QFT_4|2⟩.
6. Why is the QFT unitary?
7. What is QFT_N^{-1} of the uniform state?
8. Why can a periodic input produce sparse Fourier support?
9. What roles do Hadamard and controlled phase gates play?
10. Why does a fast QFT circuit not imply fast classical access to every Fourier coefficient?

Answers

1. e^{2πi/N}.
2. Zero; equally spaced phases cancel.
3. (1/√N)Σ_yω_N^{xy}|y⟩.
4. (1/√N)Σ_xω_N^{-xy}|x⟩.
5. (1/2)(|0⟩-|1⟩+|2⟩-|3⟩).
6. Root-of-unity orthogonality makes the transformed computational basis orthonormal.
7. |0⟩.
8. Non-matching phases cancel while reciprocal-period phases reinforce.
9. Hadamards create equal local superpositions; controlled phases encode binary-fraction phase structure.
10. Measurement samples the transformed state rather than outputting its full amplitude vector.

25. Series navigation

• Guide 9: Quantum Fourier Transform, Roots of Unity and Interference
• Guide 10: Quantum Phase Estimation, Eigenphases and Controlled Powers
• Guide 11: Amplitude Amplification, Grover Rotations and Search Geometry
• Guide 12: Stabilizer Mathematics, Pauli Groups, Syndromes and Quantum Error Correction
• Return to the BTT Mathematics Learning Hub

Educational note: this guide treats the ideal finite-dimensional QFT. Hardware implementations also face gate synthesis, connectivity, finite precision and noise.