Quantum Fourier Transform (QFT)

Overview

The quantum Fourier transform, or QFT, is the quantum version of the discrete Fourier transform. It takes the amplitudes of a quantum state and rewrites them in terms of frequencies, and it does so with a circuit that has only about n squared gates on n qubits, even though the state has 2 to the n amplitudes. The classical fast Fourier transform needs on the order of n times 2 to the n operations to do the same for a vector of that size.

The QFT is not a standalone speedup you can use to analyze a signal, because you cannot read out all the Fourier coefficients. It is a subroutine. It is the engine inside Shor's algorithm, quantum phase estimation, and many algorithms that detect hidden periodic structure.

The problem it solves

Transforming a quantum state to reveal its underlying periodicity or frequency structure.

History and background

The discrete Fourier transform has been central to signal processing for centuries, and the fast Fourier transform of Cooley and Tukey in 1965 made it practical. In 1994, Don Coppersmith at IBM described an efficient quantum circuit for it in a technical report called An Approximate Fourier Transform Useful in Quantum Factoring. Peter Shor's factoring algorithm, announced the same year, uses the QFT over the integers modulo a power of two.

Alexei Kitaev's phase estimation work in 1995 and the 1998 paper by Cleve, Ekert, Macchiavello, and Mosca placed the QFT at the center of a family of algorithms. In 2000, Thomas Draper showed that the QFT can be used to add numbers on a quantum computer, a technique that is still used to save qubits in arithmetic circuits.

How it works

Uses a sequence of Hadamard and controlled-phase gates to transform amplitudes, extracting frequency information encoded across a register of qubits.

A classical Fourier transform takes a list of N numbers and returns N new numbers that describe how much of each frequency the list contains. The quantum version does the same to the amplitudes of a state over N = 2 to the n basis states, mapping the state with amplitudes a sub x to a state with amplitudes b sub y equal to the sum over x of a sub x times e to the power 2 pi i x y over N, divided by the square root of N.

The reason a small circuit suffices is a recursive structure. The binary digits of y determine a sequence of phase rotations, and each qubit needs to be rotated by an angle that depends only on the qubits below it. The circuit consists of a Hadamard gate on each qubit followed by controlled phase rotations of smaller and smaller angles, and finally a reversal of the qubit order.

There is a catch. The output amplitudes cannot all be read out, since measuring gives a single frequency sampled with probability proportional to the squared amplitude. The QFT is useful when the input has a periodic structure, so that the output is concentrated on a few frequencies that carry the answer, as in period finding.

Step by step

1. Start with an n-qubit state whose amplitudes encode the input, for example a periodic pattern.
2. On the most significant qubit, apply a Hadamard gate, then controlled phase rotations from each lower qubit with angles pi over 2, pi over 4, and so on, halving at each step.
3. Move to the next qubit and repeat the same pattern with one fewer control, and continue down to the last qubit, which needs only a Hadamard gate.
4. Swap the qubits in reverse order, since the circuit produces the output with bit order reversed.
5. Measure the register, or pass it on to the next stage of the algorithm, such as the continued-fractions step of Shor's algorithm.
6. Optionally drop the smallest rotations to obtain the approximate QFT, which uses O(n log n) gates with only a small loss of accuracy.

A worked example

For one qubit, the QFT is just a Hadamard gate: the state 0 becomes the equal superposition of 0 and 1, and the state 1 becomes the superposition with a minus sign. For two qubits, the circuit is a Hadamard on the top qubit, a controlled rotation by pi over 2 from the second qubit, a Hadamard on the second qubit, and a swap.

As a concrete use, consider a state that is an equal superposition of the basis states 0, 4, 8, and 12 on four qubits, which has period 4. The QFT maps it to an equal superposition of the states 0, 4, 8, and 12 divided by the period structure, namely multiples of 16 divided by 4. Measuring then reveals a multiple of 4, from which the period can be inferred with a few repetitions.

Complexity and resources

What hardware it needs

• Controlled phase rotations with very small angles, which require precise control, and long-range connections between qubits or swaps.
• Error rates low enough for the small rotations to matter, which is why approximate QFTs are attractive on noisy hardware.

Applications

• Period finding in Shor's algorithm and in the hidden subgroup problem.
• Phase estimation, which underlies quantum chemistry algorithms and many others.
• Quantum arithmetic, including Draper's QFT-based adder.
• Quantum signal analysis when the input state is already available in a quantum register.

Limitations and caveats

• You cannot extract all Fourier coefficients, so it does not give a general speedup for signal processing.
• Loading classical data into a quantum state costs about as much as the classical FFT, which removes the advantage for classical data.
• Small rotation angles are hard to implement accurately on noisy hardware.

Common misconceptions

• The QFT is not exponentially faster than the FFT in practice for classical data. The comparison holds only for data already in a quantum state.
• It does not process all frequencies and print them out. A measurement returns one sample.

How it compares

• The classical FFT works on explicit vectors, while the QFT works on quantum amplitudes and has exponentially fewer gates relative to the vector length.
• Hadamard transforms, used in Deutsch-Jozsa and Simon's algorithms, are the QFT over the group of bit strings, while the QFT here is over the integers modulo 2 to the n.
• Compared with the full Shor circuit, the QFT is the cheap part, and modular exponentiation is the costly one.

Real-world impact

A core subroutine used inside Shor's Algorithm and quantum phase estimation; rarely used as a standalone algorithm but essential as a building block.

Why it matters

Almost every quantum algorithm with an exponential speedup that is known to be real contains a Fourier transform of some kind. Understanding the QFT is the key to understanding why Shor's algorithm and phase estimation work.

It also illustrates a general rule: quantum computers shine when the structure of the answer, here a period, is visible in the Fourier domain, and the transform is cheap enough that finding that structure is easy.

Frequently asked questions

Keep learning

• Related algorithm: Shor's Algorithm
• Related algorithm: Quantum Phase Estimation (QPE)
• Related algorithm: Simon's Algorithm
• Related algorithm: Iterative Quantum Phase Estimation

This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.

← Back to Algorithms Database