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 amplitudes of an n-qubit register, built from about gates where a classical FFT needs about 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 amplitudes of an n-qubit register, as a unitary circuit. A change of basis, not a solver
- Gates
- Hadamards, controlled phase rotations and swaps, in the circuit by Coppersmith[1]
- Classical counterpart
- The FFT on the same numbers takes about 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 gates and costs little accuracy[1][5]
- In eigenkit
QFTBlock(n_qubits, inverse=False), an exact transform with no parameters;QPEBlockand the HHL solver are built on it
What the quantum Fourier transform does
A register of qubits holds amplitudes, one per basis state (see quantum superposition). The QFT replaces them with their discrete Fourier transform. On a basis state it acts as 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 into phases: each basis state gets the phase , a wave of frequency 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 , the transform concentrates the probability on multiples of . Measuring gives one of those multiples, and a few of them are enough to recover .
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].
A Hadamard on the first qubit
The Hadamard turns the qubit's bit into a relative phase of 0 or : the most significant binary digit of the phase this output qubit has to carry.
A controlled phase from every later qubit
Qubit controls a rotation of angle on qubit . 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 .
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 Hadamards and controlled phases.
Reverse the register
The construction leaves the output bits in the opposite order, so 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.234On 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 qubits, and the operations of a radix-2 FFT on the same numbers. The two columns do not buy the same thing, which is what the next section is about.
| Qubits n | Amplitudes | Hadamards | Controlled phases | Swaps | QFT gates in total | FFT operations |
|---|---|---|---|---|---|---|
| 3 | 8 | 3 | 3 | 1 | 7 | 24 |
| 4 | 16 | 4 | 6 | 2 | 12 | 64 |
| 8 | 256 | 8 | 28 | 4 | 40 | 2,048 |
| 16 | 65,536 | 16 | 120 | 8 | 144 | 1,048,576 |
| 32 | about | 32 | 496 | 16 | 544 | about |
| 64 | about | 64 | 2,016 | 32 | 2,112 | about |
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 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 values into a register takes on the order of 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 , 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 . Controlling the powers on a clock register makes the clock's phases advance at the rate , and the inverse QFT turns that rate into the binary digits of [3][4]. With clock qubits the answer has bits, and the powers of cost about applications in total: precision costs order applications. This is the routine behind the long-term plans for quantum chemistry, where 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 . Shor's algorithm computes that function on a superposition of all , 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
| Claim | What holds |
|---|---|
| Exponentially faster than the FFT | Exponentially 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 processing | Not for data stored classically: loading values costs about gates, and reading the spectrum back costs many runs. |
| The QFT is what makes Shor's algorithm quantum | The 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 rotations | The rotations smaller than a threshold can be dropped. Coppersmith's approximate transform keeps order gates[1], and under decoherence the approximate circuit can do better than the exact one[5]. |
| Demonstrated on hardware | On 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 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 T gates, and Nam, Su and Maslov brought the approximate QFT down to order [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
- D. Coppersmith. An approximate Fourier transform useful in quantum factoring. IBM Research Report RC 19642, 1994. arXiv:quant-ph/0201067.
- 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.
- A. Yu. Kitaev. Quantum measurements and the Abelian stabilizer problem. arXiv preprint, 1995. arXiv:quant-ph/9511026.
- 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.
- 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.
- R. B. Griffiths, C.-S. Niu. Semiclassical Fourier transform for quantum computation. Physical Review Letters 76, 3228–3231, 1996. arXiv:quant-ph/9511007.
- 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.
- D. Aharonov, Z. Landau, J. Makowsky. The quantum FFT can be classically simulated. arXiv preprint, 2006. arXiv:quant-ph/0611156.
- T. G. Draper. Addition on a quantum computer. arXiv preprint, 2000. arXiv:quant-ph/0008033.
- 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.
- 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.
- C. Gidney. How to factor 2048 bit RSA integers with less than a million noisy qubits. arXiv preprint, 2025. arXiv:2505.15917.
- 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