Method

The quantum Fourier transform explained: a cheap circuit you cannot read out

The quantum Fourier transform (QFT) is the discrete Fourier transform applied to the 2n2^n amplitudes of an n-qubit register, built from about n2/2n^2/2 gates where a classical FFT needs about n⋅2nn \cdot 2^n operations. It is not a faster FFT: the transformed amplitudes cannot be read out, and one measurement returns a single index. It pays when a few measurements are enough, which is the case of phase estimation and of the period finding inside Shor's algorithm.

Updated

At a glance

What it is
The discrete Fourier transform of the 2n2^n amplitudes of an n-qubit register, as a unitary circuit. A change of basis, not a solver
Gates
nn Hadamards, n(n−1)/2n(n-1)/2 controlled phase rotations and ⌊n/2⌋\lfloor n/2 \rfloor swaps, in the circuit by Coppersmith[1]
Classical counterpart
The FFT on the same 2n2^n numbers takes about n⋅2nn \cdot 2^n operations, but returns all of them
What you can read
One index per run, drawn with the probability of its transformed amplitude. Never the amplitudes themselves
Where it pays
Phase estimation[3] and period finding, the quantum step of Shor's factoring algorithm[2]
Approximate version
Dropping the smallest rotations leaves order nlog⁡nn \log n gates and costs little accuracy[1][5]
In eigenkit
QFTBlock(n_qubits, inverse=False), an exact transform with no parameters; QPEBlock and the HHL solver are built on it

What the quantum Fourier transform does

A register of nn qubits holds N=2nN = 2^n amplitudes, one per basis state (see quantum superposition). The QFT replaces them with their discrete Fourier transform. On a basis state it acts as ∣k⟩↦1N∑j=0N−1e2πijk/N∣j⟩|k\rangle \mapsto \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} e^{2\pi i jk/N} |j\rangle and on any other state by linearity. This is the same matrix as the classical discrete Fourier transform, with the normalisation that makes it unitary.

Two readings of that formula explain every use of the transform. Read forwards, it writes a number kk into phases: each basis state ∣j⟩|j\rangle gets the phase 2πjk/N2\pi jk/N, a wave of frequency kk across the register. Read backwards, the inverse transform takes a register whose phases advance at a steady rate and turns it into the basis state that names the rate. An algorithm that manages to store its answer as a rate of phase can therefore measure the answer as ordinary bits.

A periodic state shows the same thing from the other side. If the amplitudes repeat with period rr, the transform concentrates the probability on multiples of N/rN/r. Measuring gives one of those multiples, and a few of them are enough to recover rr.

The QFT circuit, gate by gate

The circuit is due to Coppersmith[1]. It needs only three kinds of gate, and it works because the output of the transform on a basis state is a product of single-qubit states, each with a phase set by the bits of the input[4].

  1. A Hadamard on the first qubit

    The Hadamard turns the qubit's bit into a relative phase of 0 or π\pi: the most significant binary digit of the phase this output qubit has to carry.

  2. A controlled phase from every later qubit

    Qubit jj controls a rotation of angle 2π/2j−k+12\pi/2^{j-k+1} on qubit kk. Each less significant bit adds its own weight to the phase, half the one before it. The last rotation on an n-qubit register has angle 2π/2n2\pi/2^n.

  3. The same on each following qubit

    The second qubit gets a Hadamard and rotations from the qubits after it, and so on. The last qubit gets a Hadamard alone. That is nn Hadamards and n(n−1)/2n(n-1)/2 controlled phases.

  4. Reverse the register

    The construction leaves the output bits in the opposite order, so ⌊n/2⌋\lfloor n/2 \rfloor swap gates put them back. When the transform is followed by measurement the swaps can be left out and the bits reordered in software.

A period, read from the transform

import numpy as np
from eigenkit import Circuit, Z, assemble
from eigenkit.core.blocks import AmplitudeEncoding, QFTBlock

print([g.name for g in assemble([QFTBlock(n_qubits=3)]).gates])
# ['H', 'CPHASE', 'CPHASE', 'H', 'CPHASE', 'H', 'SWAP']

def spectrum(period, n=4):
    state = np.zeros(2 ** n)
    state[::period] = 1.0            # equal amplitude on 0, period, 2 * period, ...
    state /= np.linalg.norm(state)
    spec = assemble([AmplitudeEncoding(state), QFTBlock(n_qubits=n)])
    return np.asarray(Circuit(spec, observables=Z(0)).probabilities([]))

print(np.round(spectrum(4), 3))
# [0.25 0. 0. 0. 0.25 0. 0. 0. 0.25 0. 0. 0. 0.25 0. 0. 0.]
three = spectrum(3)
print(round(float(three[5]), 3), round(float(three[11]), 3))
# 0.234 0.234

On 16 basis states, a state that repeats every 4 steps comes out on the indices 0, 4, 8 and 12, the multiples of 16/4, each with probability 25%. A period of 3 does not divide 16, so the peaks at 5 and 11 (the integers nearest 16/3 and 32/3) are broadened: they hold 23.4% each, and the rest leaks to their neighbours. The built-in NumPy simulator returns exact probabilities; a QPU would return one index per shot.

Gate counts, next to the FFT

Gates of the exact circuit on nn qubits, and the n⋅2nn \cdot 2^n operations of a radix-2 FFT on the same 2n2^n numbers. The two columns do not buy the same thing, which is what the next section is about.

Qubits nAmplitudesHadamardsControlled phasesSwapsQFT gates in totalFFT operations
38331724
4164621264
82568284402,048
1665,5361612081441,048,576
32about 4.3×1094.3 \times 10^{9}3249616544about 1.4×10111.4 \times 10^{11}
64about 1.8×10191.8 \times 10^{19}642,016322,112about 1.2×10211.2 \times 10^{21}

Computed from the formulas; the 3-qubit row is the gate list the code above prints. On error-corrected hardware each small rotation is itself built from many elementary gates, so the real cost is higher than the count of rotations.

Why the QFT is not a faster FFT

The table invites the wrong conclusion. An FFT returns all 2n2^n transformed values. The QFT leaves them as amplitudes, and a measurement returns one index, drawn with probability equal to the squared magnitude of its amplitude. Phases are lost. Estimating even the magnitudes to a useful accuracy takes a number of runs that grows with the size of the vector, which gives the speed-up back.

The input is the second catch. An FFT starts from numbers in memory. The QFT starts from a quantum state that already holds those numbers as amplitudes, and loading an arbitrary list of 2n2^n values into a register takes on the order of 2n2^n gates. A signal, an image or a time series stored classically cannot be transformed faster this way.

The third point is subtler: the transform is not where the quantum power lies. Aharonov, Landau and Makowsky showed that the QFT circuit itself can be simulated efficiently on a classical computer, and that this does not make factoring classical, because the hard part is the state the transform is applied to[8]. In Shor's algorithm that state comes from modular exponentiation, which also accounts for almost all of the gates.

So the QFT is useful in one situation: a quantum state with hidden periodic structure, made by an earlier part of the circuit, where a handful of measurements after the transform reveal the structure. Signal processing on classical data is not that situation.

Phase estimation: the inverse QFT at work

import numpy as np
from eigenkit import Circuit, Z, assemble
from eigenkit.core.blocks import AmplitudeEncoding, QPEBlock, QubitUnitary

def estimate(phi, n_clock=4):
    U = np.diag([1.0, np.exp(2j * np.pi * phi)])   # eigenvalue exp(2 pi i phi) on |1>
    oracle = assemble([QubitUnitary(U, wires=(0,))])
    start = np.zeros(2 ** (n_clock + 1))
    start[1] = 1.0                            # clock at zero, state qubit in |1>
    spec = assemble([AmplitudeEncoding(start), QPEBlock(oracle, n_clock=n_clock)])
    probs = np.asarray(Circuit(spec, observables=Z(0)).probabilities([]))
    clock = probs.reshape(2 ** n_clock, 2).sum(axis=1)
    best = int(clock.argmax())
    return format(best, "04b"), best / 2 ** n_clock, round(float(clock[best]), 4)

print(estimate(5 / 16))   # ('0101', 0.3125, 1.0)
print(estimate(1 / 3))    # ('0101', 0.3125, 0.6849)

A one-qubit gate with eigenvalue e2πiφe^{2\pi i\varphi}, and four clock qubits. QPEBlock applies Hadamards to the clock, the controlled powers of the gate, and the inverse QFT. A phase of 5/16 fits in four bits and is read with certainty as 0101. A phase of 1/3 does not: the nearest four-bit value, 0.3125, comes out with probability 68.5%, and its neighbours take the rest. Each extra clock qubit adds one bit of precision and doubles the number of applications of the gate.

Where the QFT is used

Phase estimation. A unitary applied to one of its eigenstates only multiplies it by a phase e2πiφe^{2\pi i\varphi}. Controlling the powers U,U2,U4,…U, U^2, U^4, \dots on a clock register makes the clock's phases advance at the rate φ\varphi, and the inverse QFT turns that rate into the binary digits of φ\varphi[3][4]. With tt clock qubits the answer has tt bits, and the powers of UU cost about 2t2^t applications in total: precision ε\varepsilon costs order 1/ε1/\varepsilon applications. This is the routine behind the long-term plans for quantum chemistry, where UU is the time evolution of a molecule and the phase is its energy (see quantum computing for chemistry).

Period finding and Shor's algorithm. Factoring an integer reduces to finding the period of ax mod Na^x \bmod N. Shor's algorithm computes that function on a superposition of all xx, which leaves a periodic state, and a QFT turns the period into peaks that a measurement can hit[2]. The transform is the cheap part. In the resource estimates for 2048-bit RSA, the cost is the modular arithmetic and the error correction under it: 20 million noisy qubits for 8 hours[11] in the 2019 estimate, less than a million noisy qubits for less than a week[12] in the 2025 one.

Linear systems. The HHL algorithm uses phase estimation to write the eigenvalues of a matrix into a register, inverts them with a controlled rotation, and runs phase estimation backwards[13]. The QFT appears twice, once in each direction.

Arithmetic. In the Fourier basis, adding a number is a set of phase rotations, so a QFT, some rotations and an inverse QFT make an adder that needs no carry qubits[9]. Circuits for modular arithmetic on few qubits use this.

Amplitude estimation. The original algorithm ran phase estimation on the Grover operator. Later variants such as iterative amplitude estimation removed the QFT, and reach the same scaling with shallower circuits (see quantum amplitude estimation against Monte Carlo). Where a QFT can be avoided, current practice avoids it.

Claims you will see, and what holds

ClaimWhat holds
Exponentially faster than the FFTExponentially fewer gates than the FFT has operations, on a state that is already in the register. The output cannot be read, so it does not replace an FFT on classical data.
Speeds up signal and image processingNot for data stored classically: loading 2n2^n values costs about 2n2^n gates, and reading the spectrum back costs many runs.
The QFT is what makes Shor's algorithm quantumThe transform alone can be simulated classically[8]. The hard part, and nearly all the cost, is the modular exponentiation that prepares the periodic state.
It needs impossibly precise rotationsThe rotations smaller than a threshold can be dropped. Coppersmith's approximate transform keeps order nlog⁡nn \log n gates[1], and under decoherence the approximate circuit can do better than the exact one[5].
Demonstrated on hardwareOn small registers. Shor's algorithm factored 15 on a trapped-ion computer with success probabilities above 90%[10], using a QFT reduced to one qubit that is measured and reused.

Approximate and semiclassical versions

The controlled rotations get small fast: the angle halves with every qubit of distance, and on a wide register most of them are far below what any device can apply accurately. Coppersmith's paper already proposed to drop every rotation below a cut-off, which leaves about nlog⁡nn \log n gates[1]. Barenco, Ekert, Suominen and Törmä analysed this approximate transform with decoherence and found that extensive approximation is possible before accuracy suffers, and that in some computations the shorter circuit performs better than the exact one[5].

When the transform is the last step before measurement, which is the usual case, it does not need two-qubit gates at all. Griffiths and Niu showed that each qubit can be measured in turn and the result used to choose the single-qubit rotations on the qubits that follow[6]. Kitaev's version of Shor's algorithm goes further and reuses one qubit for the whole clock register, which is how the trapped-ion demonstration ran[10].

On error-corrected hardware the cost that matters is the number of T gates, because arbitrary small rotations have to be synthesised from them. The standard construction needs order nlog⁡2nn \log^2 n T gates, and Nam, Su and Maslov brought the approximate QFT down to order nlog⁡nn \log n[7]. Even so, a QFT wide enough to matter sits inside a circuit that needs error correction for its other parts.

eigenkit keeps every rotation. QFTBlock is exact, takes no parameters, and compiles on any backend that has H, CPHASE and SWAP; inverse=True gives the adjoint that phase estimation uses. There is no approximate or semiclassical variant, and no Shor or period-finding solver. The transform is there for QPEBlock and for HHL, and for circuits you assemble yourself.

Run it on a real QPU with EigenOrbit RouterThe four-qubit phase estimation above, where gate errors spread the clock register's sharp peak over its neighbours.In eigenkit: pip install "eigenkit[router]", then provider=RouterConfig(device=...) (docs).

Questions

What is the quantum Fourier transform?

It is the discrete Fourier transform applied to the amplitudes of a quantum register: a unitary circuit that maps a basis state k to an equal superposition with phases that advance at the rate k. It is a change of basis that other algorithms use to turn a phase or a period into bits that can be measured.

How many gates does the QFT need?

The exact circuit on n qubits has n Hadamard gates, n(n-1)/2 controlled phase rotations and n/2 swaps, rounded down. That is 7 gates on 3 qubits and 2,112 on 64. The approximate version drops the smallest rotations and keeps on the order of n log n gates.

Is the quantum Fourier transform faster than the FFT?

It uses exponentially fewer gates than the FFT has operations, but it does not do the same job. The result stays in the amplitudes of the register and a measurement returns a single index, and classical data must first be loaded into a quantum state at a cost that grows with its size. It cannot replace an FFT on a signal or an image.

What is the QFT used for?

Phase estimation, which reads an eigenvalue of a unitary as binary digits, and period finding, the quantum step of Shor's factoring algorithm. Through phase estimation it also appears in the HHL algorithm for linear systems and in long-term algorithms for molecular energies. It is also used for arithmetic on few qubits.

What is the difference between the QFT and the inverse QFT?

The forward transform writes a number into the phases of a register. The inverse transform reads a rate of phase back as a number. Phase estimation ends with the inverse transform, which is the direction most algorithms need.

Can the QFT run on today's quantum computers?

On a few qubits, yes: it is a short circuit. The algorithms around it are the problem. Shor's algorithm on a 2048-bit number needs error correction and, by a 2025 estimate, close to a million physical qubits running for days. Demonstrations so far factor numbers such as 15.

Does eigenkit implement the quantum Fourier transform?

Yes, as QFTBlock, an exact transform and its inverse built from Hadamard, controlled phase and swap gates. QPEBlock builds phase estimation on it, and the HHL solver uses both. eigenkit has no approximate QFT and no Shor solver.

Sources

  1. D. Coppersmith. An approximate Fourier transform useful in quantum factoring. IBM Research Report RC 19642, 1994. arXiv:quant-ph/0201067.
  2. P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing 26(5), 1484–1509, 1997. arXiv:quant-ph/9508027.
  3. A. Yu. Kitaev. Quantum measurements and the Abelian stabilizer problem. arXiv preprint, 1995. arXiv:quant-ph/9511026.
  4. R. Cleve, A. Ekert, C. Macchiavello, M. Mosca. Quantum algorithms revisited. Proceedings of the Royal Society A 454, 339–354, 1998. arXiv:quant-ph/9708016.
  5. A. Barenco, A. Ekert, K.-A. Suominen, P. Törmä. Approximate quantum Fourier transform and decoherence. Physical Review A 54, 139–146, 1996. arXiv:quant-ph/9601018.
  6. R. B. Griffiths, C.-S. Niu. Semiclassical Fourier transform for quantum computation. Physical Review Letters 76, 3228–3231, 1996. arXiv:quant-ph/9511007.
  7. Y. Nam, Y. Su, D. Maslov. Approximate quantum Fourier transform with O(n log(n)) T gates. npj Quantum Information 6, 26, 2020. arXiv:1803.04933.
  8. D. Aharonov, Z. Landau, J. Makowsky. The quantum FFT can be classically simulated. arXiv preprint, 2006. arXiv:quant-ph/0611156.
  9. T. G. Draper. Addition on a quantum computer. arXiv preprint, 2000. arXiv:quant-ph/0008033.
  10. T. Monz, D. Nigg, E. A. Martinez, M. F. Brandl, P. Schindler, R. Rines, S. X. Wang, I. L. Chuang, R. Blatt. Realization of a scalable Shor algorithm. Science 351, 1068–1070, 2016. arXiv:1507.08852.
  11. C. Gidney, M. Ekerå. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum 5, 433, 2021. arXiv:1905.09749.
  12. C. Gidney. How to factor 2048 bit RSA integers with less than a million noisy qubits. arXiv preprint, 2025. arXiv:2505.15917.
  13. A. W. Harrow, A. Hassidim, S. Lloyd. Quantum algorithm for linear systems of equations. Physical Review Letters 103, 150502, 2009. arXiv:0811.3171.

Run it yourself with eigenkit

eigenkit is EigenOrbit's open-source Python library: write a circuit once, run it on any simulator or QPU, and test it against a classical baseline on your own data before you invest in it or rule it out.

$ pip install eigenkit