person Tute World Team

Quantum Fourier Transform

The Fourier Transform is one of the most powerful mathematical tools in existence — it decomposes a signal into its frequencies. The Quantum Fourier Transform (QFT) does the same thing, but on quantum states, and does it exponentially faster. It's the engine powering Shor's algorithm and many other quantum algorithms.

First: What is the Classical Fourier Transform?

The Fourier Transform converts a function from the "time domain" to the "frequency domain." In everyday terms: given a complex signal (like music), it tells you which frequencies (notes) are present and at what strength.

The Discrete Fourier Transform (DFT) does this for discrete signals. For an input of N values, the DFT produces N frequency components. The naive algorithm takes O(N²) operations. The Fast Fourier Transform (FFT), invented in 1965, does it in O(N log N) — much faster.

Classical DFT O(N²)
Classical FFT O(N log N) = O(n · 2ⁿ)
Quantum QFT O(n²) = O((log N)²)

Where n = log₂(N) is the number of qubits. For N = 2^50 (about 10^15), the FFT needs ~50 × 10^15 operations. The QFT needs just 50² = 2,500 gates. That's an extraordinary speedup.

What the QFT Does

The QFT takes a quantum state — a superposition of n-qubit basis states — and transforms it into another superposition where the amplitudes encode the frequency information of the original state.

Mathematically, the QFT maps:

|j⟩ → (1/√N) Σ e^(2πijk/N) |k⟩

In plain English: each basis state |j⟩ gets transformed into a superposition of all N basis states, with complex phases that encode the frequency j/N. This is exactly the DFT, applied to quantum amplitudes.

The catch: The QFT is exponentially fast, but you can't directly read out all N amplitudes (that would require exponentially many measurements). The QFT is only useful when combined with other quantum operations (like in Shor's phase estimation) where you only need to extract one specific piece of frequency information.

The QFT Circuit

The QFT circuit for n qubits uses only O(n²) gates:

  • n Hadamard gates — one per qubit, creating superpositions
  • n(n-1)/2 controlled phase rotation gates (Rₖ) — adding relative phases between qubits
  • SWAP gates — reversing the bit order at the end

The controlled-Rₖ gate

The Rₖ gate applies a phase rotation of 2π/2ᵏ to |1⟩. With k=2, it's a 90° rotation; with k=3, it's 45°; and so on. By applying progressively smaller rotations controlled by each qubit, the circuit builds up the correct Fourier phases across the full quantum state.

How the QFT Powers Shor's Algorithm

In Shor's algorithm, you need to find the period r of the function f(x) = aˣ mod N. After applying the quantum oracle that evaluates f, you have a superposition like this:

Σ |x⟩|aˣ mod N⟩

Measuring the second register collapses it to some value f(x₀). The first register then contains a superposition of all x values where f(x) = f(x₀) — which are periodic with period r: x₀, x₀+r, x₀+2r, ...

Apply the QFT to the first register. The result is a superposition with large amplitudes at integer multiples of N/r. Measuring gives you N/r, and simple classical math (continued fractions) extracts r. From r, you factor N.

The QFT extracts the period in O(n²) gates. This is the quantum advantage that makes Shor's exponentially faster than classical factoring.

Other Uses of the QFT

Quantum Phase Estimation (QPE)

QPE estimates the eigenvalue (phase) of a quantum gate's eigenvector. This is used in quantum chemistry simulations (finding molecular energy levels) and is the basis of many variational quantum algorithms.

Quantum machine learning

Some quantum ML algorithms use the QFT to efficiently compute inner products between data vectors encoded in quantum states.

Quantum signal processing

Any quantum algorithm that needs to work with periodic or frequency-domain information can leverage the QFT for exponential speedup over its classical counterpart.

Frequently Asked Questions

Can the QFT replace the classical FFT for everyday applications?

No. The QFT's exponential advantage comes with a catch: you can't efficiently read out the N output amplitudes. Doing so would require exponentially many measurements. The QFT is useful only in quantum algorithms where a small amount of frequency information is sufficient — like Shor's period-finding. For classical signal processing, the FFT remains the tool of choice.

What's the difference between QFT and quantum phase estimation?

The QFT is a mathematical transform. Quantum Phase Estimation (QPE) is an algorithm that uses the QFT as a subroutine. QPE estimates the phase φ of an eigenvalue e^(2πiφ) of a unitary operator — this is how Shor's period-finding works, and how quantum chemistry simulations compute ground-state energies.

How many qubits does the QFT need?

To transform a 2ⁿ-point DFT, you need n qubits. For Shor's algorithm factoring a 2048-bit number, you'd need about 4,096 qubits for the QFT register. The circuit has O(n²) ≈ 16 million gates — well beyond current NISQ hardware, but feasible for future fault-tolerant machines.

← Shor's Algorithm Next: Phase 4 — Hardware →

Frequently Asked Questions

What will I learn here?

This page covers the core concepts and techniques you need to understand the topic and progress confidently to the next lesson.

How should I use this page?

Start with the overview, then follow the section links to deepen your understanding. Use the table of contents on the right to jump to specific sections.

What should I read next?

Use the navigation below to continue to the next lesson or explore related topics.