quantum Fourier transform

In plain terms

Start with the classical tool. A Fourier transform takes a signal and re-expresses it as a mixture of regular oscillations, reporting which frequencies are present and how strongly, and the discrete version does the same for a finite list of numbers and is the workhorse of signal processing, so if you feed it a list that repeats with some period its output piles up at the frequencies of that period.

Now the quantum problem. A quantum register holds an amplitude for each of its possible readings, a number whose squared size gives the probability of that reading, and whose angle, called its phase, is invisible to any single measurement. Quantum interference only helps if the structure you care about, a repeating period or a hidden phase, can be steered onto readings a measurement actually produces, so you need a lens that focuses spread-out regularity into sharp peaks.

The quantum Fourier transform is that lens. It's the same discrete transform, executed as one physical evolution of the register rather than as arithmetic on a list of numbers, so if you feed it a state whose amplitudes repeat with some period the output concentrates on the frequencies of that period, where a measurement finds them. Shor's algorithm is the famous customer, as you load a sequence from modular arithmetic, apply the transform, and the period that encodes the factors stands out like a struck bell.

In CSD

The transform is a library primitive in the corpus, kept deliberately free of CSD content so an outside project can import it. It's stated for a register with any number of levels and not only powers of two, so it's directly the discrete Fourier transform, and the qubit case is an instance. Its unitarity, the property of being a reversible, length-preserving change of the register, which is what any physical evolution must be, is proved from the orthogonality of the roots of unity, which is a geometric series and nothing deeper.

The algorithm witnesses that need it, Shor's algorithm and phase estimation, consume it. The standing disclaimer for the algorithm layer applies, as these results rest on the programme's unitary-evolution pillar and don't support it or the foundations, and they mark the scope of what the library can express.

Mathematically

A Cat-1 (CSD-free) library primitive, F j k = (1/sqrt N) omega^{jk} with omega = exp(2 pi i / N) a primitive N-th root of unity. Unitarity F^H F = 1 is the orthogonality sum over k of zeta^k = N [zeta = 1], closed by the geometric series (qft_unitary).

It's matrix level only, as the corpus states the transform as an N x N unitary and proves its algebra, and no gate-level circuit decomposition is claimed.

The name

Joseph Fourier (1768-1830) was an orphan from Auxerre who taught at the Ecole Polytechnique, governed Lower Egypt under Napoleon, and administered the Isere department from Grenoble, where, between prefectural duties, he wrote the analytical theory of heat. His claim that arbitrary functions decompose into sines scandalised Lagrange and became the spine of applied mathematics anyway.

The quantum version arrived with Shor's 1994 paper and its predecessors, with the insight that the transform's butterfly structure makes it exponentially cheap as a quantum circuit, which is exactly what period-finding needed.

Related entries

• Shor's algorithmShor's algorithm factors large numbers in polynomial time on a quantum computer, and it turned quantum computing from a curiosity into a budget line and made every deployed cryptosystem provisional.
• phase estimationPhase estimation, the workhorse subroutine of quantum computing, carries a guarantee, as if you read the dial at the nearest tick you're right at least four divided by pi squared of the time, a little over forty percent, however fine the dial.
• Simon's algorithmSimon's algorithm was the exponential separation that convinced Shor, as a hidden bitwise mask, unfindable classically without exponential work, falls to a handful of quantum queries and some linear algebra.
• Hadamard testThe Hadamard test turns a matrix element, a complex number buried inside an operator, into the bias of a single coin.
• amplitude estimationPoint phase estimation at the rotation inside amplitude amplification and the success probability itself becomes measurable, quadratically faster than sampling could ever learn it.