Thursday, September 17, 2026

Quantum Fourier Transform: Turning Phase into a Number

The QFT transforms a quantum stateThe mathematical description used to predict the probabilities of different measurement outcomes for a quantum system. so that hidden phase or periodic structure can interfere into something we can measure.

The pattern you cannot see

Suppose a quantum computer has done something useful but inconvenient: the answer is there, encoded in the relative phasesThe phase difference between the parts of a superposition. Invisible when you only ask 0 or 1, it changes the results when you measure another way. of its amplitudesThe complex number attached to each possible outcome of a quantum state. Its size sets the outcome probability and its angle is the phase.. You cannot simply ask each amplitude for its quantum phaseThe angle associated with a quantum amplitude. Differences between these angles determine how amplitudes interfere., because measurementA physical process that produces a classical outcome and updates the quantum state. In an ideal projective measurement, the state is left in an eigenstate associated with the observed outcome. does not work that way. It gives you one classical outcome. The Quantum Fourier TransformThe quantum version of the Fourier transform. It converts a pattern hidden in the phases of a quantum state into an ordinary number you can read out., or QFT, solves a different problem. Instead of trying to read those phases directly, it transforms the state so that particular phase patterns become particular measurement outcomes. Think of it as making the amplitudes interfere with one another before you look.

From phase to peaks

For n qubitsThe basic unit of a quantum computer. Like a 'bit' in a normal computer, but instead of being only 0 or 1 it can be 0, 1, or a blend of both at once. there are N = 2ⁿ computational basis statesOne definite bit string of a qubit register, such as 101. Any quantum state of the register is a combination of these., so a state carries one amplitude for each of them:

|ψ⟩  =  ∑_x a_x |x⟩

The QFT replaces those amplitudes with a new set:¹

b_k  =  (1 / √N) ∑_x a_x e^2πi xk/N

That is mathematically the discrete Fourier transformThe standard mathematical operation that turns a list of numbers into the strengths of the repeating patterns inside it. applied to the amplitudes of the quantum state, but the useful physical picture is simpler. Imagine the terms in the sum as little arrows in the complex plane. For most values of k the arrows point in different directions and mostly cancel; for special values their phases line up, so the amplitudes add instead of canceling and the probability of measuring that k becomes large. If the input contains a repeating pattern, the QFT therefore creates peaks at values related to that repetition, and the hidden spacing has become a measurable pattern.

That is the job the QFT is really doing.

The cleanest example

Quantum phase estimationA quantum algorithm that estimates a phase associated with a quantum operation. In molecular simulation, that phase can be used to recover an energy. makes this almost embarrassingly clear. Suppose another part of the algorithm produces a register whose amplitudesThe complex number attached to each possible outcome of a quantum state. Its size sets the outcome probability and its angle is the phase. rotate steadily:

1,  e^2πiφ,  e^2πi 2φ,  e^2πi 3φ,  …

The unknown quantity is φ, stored as a rate of phase rotation across the register rather than as a binary number you can simply read. If φ = m/N for an integer m, the inverse QFT takes this entire rotating phase pattern and maps it to the computational basis stateOne definite bit string of a qubit register, such as 101. Any quantum state of the register is a combination of these. |m⟩, so a measurementA physical process that produces a classical outcome and updates the quantum state. In an ideal projective measurement, the state is left in an eigenstate associated with the observed outcome. can return m.² If φ falls between those exact n-bit values, the result is no longer one certain bit string: the probability concentrates around the closest estimates instead.²

So the QFT has not somehow measured the phase. It has arranged interferenceThe addition of quantum amplitudes, which can reinforce or cancel one another depending on their relative phases. so that the phase writes its answer into the probability distribution. This is why the QFT sits inside quantum phase estimation and Shor’s factoring algorithm.³ In Shor’s algorithm the hidden structure is periodicity, and the Fourier transform converts that periodic structure into measurement outcomes from which the period can be inferred.

Where the apparent speedup hides

The standard QFT on n qubitsThe basic unit of a quantum computer. Like a 'bit' in a normal computer, but instead of being only 0 or 1 it can be 0, 1, or a blend of both at once. can be built from of order n² elementary gates, mainly Hadamard gatesA one-qubit operation that turns a definite 0 or 1 into a balanced quantum superposition. The standard way to create one. and controlled phase rotationsA two-qubit gate that turns the phase of one qubit by a set angle, but only when the other qubit is 1..¹ A classical Fourier transform of N = 2ⁿ numbers has to process and return N Fourier coefficients, so even the fast Fourier transformThe classical algorithm that computes a discrete Fourier transform of N numbers in about N log N steps instead of N squared. requires work scaling roughly as N log N. That sounds like an exponential victory for the QFT, but there is a catch.

The QFT does not give you all 2ⁿ transformed amplitudesThe complex number attached to each possible outcome of a quantum state. Its size sets the outcome probability and its angle is the phase. as classical numbers. They remain amplitudes inside a quantum stateThe mathematical description used to predict the probabilities of different measurement outcomes for a quantum system., and measurementA physical process that produces a classical outcome and updates the quantum state. In an ideal projective measurement, the state is left in an eigenstate associated with the observed outcome. reveals only limited information, so the QFT is not an exponentially faster replacement for the fast Fourier transform in ordinary signal processing.⁴ Its power appears when an algorithm needs only some global property of those amplitudes, such as a phase or a period, and quantum interferenceThe addition of quantum amplitudes, which can reinforce or cancel one another depending on their relative phases. can concentrate that information into outcomes we can sample. That is the QFT’s trick: not computing every Fourier coefficient for us, but arranging the quantum state so we never have to.

Sources

1. Nielsen, M. A. & Chuang, I. L. Quantum Computation and Quantum Information, 10th Anniversary Edition, Chapter 5 (Cambridge University Press, 2010). DOI: 10.1017/CBO9780511976667. ↩
2. Cleve, R., Ekert, A., Macchiavello, C. & Mosca, M. “Quantum Algorithms Revisited.” Proceedings of the Royal Society A 454, 339–354 (1998). DOI: 10.1098/rspa.1998.0164. Preprint: arXiv:quant-ph/9708016. ↩
3. Shor, P. W. “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.” SIAM Journal on Computing 26, 1484–1509 (1997). DOI: 10.1137/S0097539795293172. Preprint: arXiv:quant-ph/9508027. ↩
4. Dalzell, A. M. et al. “Quantum Fourier Transform.” Chapter 12 in Quantum Algorithms: A Survey of Applications and End-to-End Complexities, 225–227 (Cambridge University Press, 2025). DOI: 10.1017/9781009639651.015. ↩