Quantum Fourier Transform

The discrete Fourier transform over the cyclic group $\mathbb{Z}_N$ is a fixed unitary change of basis — the same linear map that a classical fast Fourier transform computes in $O(N\log N)$ arithmetic operations. The quantum Fourier transform (QFT) performs that identical map, but on the $N=2^n$ complex amplitudes that live inside the state of just $n$ qubits, and it does so with only $O(n^2)=O((\log N)^2)$ elementary gates. That is an exponential compression of the transform itself, and it is why the QFT sits at the heart of almost every quantum algorithm with an exponential speedup. The engine behind the efficient circuit is the product (Coppersmith) form. When $N=2^n$ , the QFT of a computational basis state $|j\rangle$ does not entangle the output qubits at all: it factors into a tensor product in which the $\ell$ -th output qubit carries a single relative phase $e^{2\pi i\,0.j_{n-\ell+1}\cdots j_n}$ written as a binary fraction. Each factor is manufactured by one Hadamard followed by a short cascade of controlled-phase rotations conditioned on the lower-order input bits, and a final layer of SWAPs reverses the qubit order. One must be honest about what the QFT does not buy. Like quantum parallelism, it cannot hand you a classical Fourier spectrum: a single measurement afterwards returns one index $k$ with probability $|\hat\psi_k|^2$ , not the whole vector of amplitudes. The power appears only when the input carries hidden periodic structure — as in order finding or Simon's algorithm — so that interference concentrates the output onto multiples of $N/r$ and reveals the period $r$ . Conceptually the QFT is the character transform of an abelian group: it diagonalizes cyclic shifts and turns translation-invariant information into localized labels.

Key takeaways

The QFT is the unitary that sends a basis state $|j\rangle$ over $\mathbb{Z}_N$ to the Fourier superposition $\frac{1}{\sqrt N}\sum_k e^{2\pi i jk/N}|k\rangle$ — a change to the "frequency" basis.
For $N=2^n$ it factors into a tensor product of single-qubit phases, giving a circuit of $O(n^2)$ Hadamard and controlled-phase gates, exponentially cheaper than the $O(N\log N)$ classical FFT.
Physically it turns the period or eigenphase hidden in a state's relative phases into a position in the computational basis that a measurement can read.
It is the working engine of quantum phase estimation, order finding, Shor's factoring and discrete-log algorithms, and the whole abelian hidden-subgroup framework.
The QFT alone gives no speedup: it needs an oracle to first prepare a periodic state and (in factoring) classical continued-fraction post-processing; dropping its tiny rotations yields the $O(n\log n)$ approximate QFT used under fault tolerance.
Key idea: the QFT diagonalizes cyclic shifts, so it transforms a hidden period (or eigenphase) encoded in relative phases into a measurable position in the computational basis, and for $N=2^n$ it factors into single-qubit phases, giving an $O(n^2)$ -gate circuit.

The core insight

The QFT diagonalizes cyclic shifts, so it converts a hidden period (or eigenphase) carried in a state's relative phases into a position in the computational basis that a single measurement can read out; for $N=2^n$ the transform factors into single-qubit phases, giving an $O(n^2)$ -gate circuit.

Where this lives today

The QFT is now a line item in every serious estimate of what a code-breaking quantum computer would cost. In the landmark 2019 resource analysis by Gidney and Ekerå, factoring a 2048-bit RSA integer is projected to take about 8 hours on roughly 20 million noisy physical qubits — and a central reason that number is even conceivable is that the QFT (in its approximate, rotation-truncated form) and the surrounding phase-estimation circuitry are so gate-efficient. Phase estimation built on small QFTs and inverse QFTs is routinely demonstrated on trapped-ion and superconducting processors, and it is the workhorse subroutine proposed for early fault-tolerant quantum chemistry, where a molecule's ground-state energy reduces to reading an eigenphase to several bits. The same transform, run over $\mathbb{Z}_2^n$ as $H^{\otimes n}$ , powers Simon's and Bernstein–Vazirani algorithms, and its generalization is the open frontier: the non-abelian hidden subgroup problem — whose solution would crack graph isomorphism and certain lattice problems — is unsolved because no efficient QFT-style interference is known for the relevant non-commuting groups.

The physical picture

Think of the QFT as the quantum way of asking "what frequencies are present?" If a state's amplitudes repeat with period $r$ — the same complex weight every $r$ basis states — the transform routes that periodicity into a handful of sharp peaks at the multiples of $N/r$ , while destructive interference cancels everything between. A hidden period in real space becomes a visible spike in Fourier space, and the trick of order finding and Shor's algorithm is to make the answer you want the location of one of those spikes. The circuit that does this is astonishingly cheap. Each output qubit of the $N=2^n$ QFT ends up holding one bit of a binary-fraction phase $0.j_k j_{k+1}\cdots j_n$ : a Hadamard extracts the leading bit's phase into the $|0\rangle,|1\rangle$ relative phase, and the controlled rotations add finer corrections from the less significant input bits. The circuit literally writes a number's binary expansion into a chain of phases, as the first figure shows for three qubits.

Figure

The 3-qubit QFT: a Hadamard plus a cascade of controlled S and T rotations on each line, then one swap to reverse bit order — 6 gates in all matching n(n+1)/2 = 3·4/2 = 6, versus the classical FFT's N log₂N = 8·3 = 24 arithmetic operations on the same 8 amplitudes

Underneath the circuit is a piece of pure structure: the QFT diagonalizes the cyclic shift $S|x\rangle=|x+1 \bmod N\rangle$ . Its eigenvectors are exactly the Fourier states, with eigenvalues $e^{2\pi i k/N}$ , so anything built out of shifts — any periodic function — becomes block-diagonal after the transform, which is why periodic information localizes. No information is created: the QFT is unitary, hence reversible, and its magic is purely interferential — a basis in which the answer you want is localized and one measurement is informative. The second figure shows that interference concretely, with numbers.

Figure

Period becomes frequency: a register of N = 16 amplitudes repeating every r = 4 on the left is mapped by the QFT to a comb of 4 sharp peaks at the multiples of N/r = 4, namely k = 0, 4, 8, 12, each carrying probability 1/r = 1/4 = 0.25 on the right — the constructive interference that reveals a hidden period

The core equations

The definition is a single line: the QFT relabels every basis state by the full set of $\mathbb{Z}_N$ characters (roots of unity) evaluated at that state. It is written most compactly by its action on a basis vector, from which linearity fixes its action on any superposition.

\mathrm{QFT}_N\,|j\rangle=\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} e^{2\pi i jk/N}\,|k\rangle \qquad (1)

where: $N$ — dimension of the cyclic group $\mathbb{Z}_N$ , and for qubits $N=2^n$ ; $|j\rangle$ — computational basis state, an integer $0\le j\le N-1$ ; $e^{2\pi i jk/N}$ — the $jk$ -th character (root of unity) of $\mathbb{Z}_N$ . The input index $j$ sets the rate at which the output phase winds across $k$ , spreading a "position" $j$ into a phase gradient. Assembling those column vectors gives the matrix — a symmetric, unitary matrix of equal-modulus roots of unity, entirely fixed once $N$ is chosen.

(\mathrm{QFT}_N)_{kj}=\frac{\omega^{jk}}{\sqrt{N}},\qquad \omega=e^{2\pi i/N} \qquad (2)

where: $\omega$ — the primitive $N$ -th root of unity; $(\cdot)_{kj}$ — the matrix element in row $k$ , column $j$ . Every entry has modulus $1/\sqrt N$ , so all of the transform's selectivity comes from phase interference, never amplitude weighting. The whole efficiency of the circuit rests on one algebraic fact: for $N=2^n$ the transformed state does not entangle its output qubits but factors into a tensor product of single-qubit states, each carrying a binary-fraction phase.

\mathrm{QFT}_{2^n}|j\rangle=\frac{1}{2^{n/2}}\bigotimes_{\ell=1}^{n}\Big(|0\rangle+e^{2\pi i\,0.j_{n-\ell+1}\cdots j_n}|1\rangle\Big) \qquad (3)

where: $j=j_1 j_2\cdots j_n$ — the binary expansion, $j=\sum_\ell j_\ell 2^{n-\ell}$ ; $0.j_a\cdots j_n=\sum_m j_{a+m}/2^{m+1}$ — a binary fraction. The first output qubit holds only $0.j_n$ , the last holds the full tail $0.j_1\cdots j_n$ — which is why the outputs emerge in reversed bit order. Each tensor factor is produced by a fixed toolkit: a Hadamard plus controlled versions of the phase gate $R_k$ .

R_k=\begin{pmatrix}1&0\\[2pt]0&e^{2\pi i/2^{k}}\end{pmatrix},\qquad R_1=Z,\ \ R_2=S,\ \ R_3=T \qquad (4)

where: $H$ — the Hadamard gate, itself the single-qubit QFT; $R_k$ — the phase gate applying $e^{2\pi i/2^k}$ to $|1\rangle$ . The angle $2\pi/2^k$ halves with every extra qubit of separation, so distant controls contribute exponentially tiny rotations — the fact that later makes the approximate QFT possible. Counting those gates gives the headline complexity, whose comparison with the classical FFT is the entire point of the subroutine.

\#\text{gates}=\binom{n}{2}+n=\frac{n(n+1)}{2}=O(n^2)\quad\text{vs.}\quad\text{FFT }O(N\log N)=O(2^n\,n) \qquad (5)

where: $n$ — the number of qubits, $N=2^n$ ; $\binom{n}{2}=n(n-1)/2$ — controlled-phase gates; $+n$ — the Hadamards; and a further $\lfloor n/2\rfloor$ SWAPs undo the bit reversal. The quantum cost is polynomial in $\log N$ while the classical cost is quasilinear in $N$ — an exponential separation. Finally, the structural fact that makes the QFT natural for periodic problems: it diagonalizes the cyclic shift.

S\,|x\rangle=|x+1 \bmod N\rangle,\qquad \mathrm{QFT}_N\,S\,\mathrm{QFT}_N^{\dagger}=\sum_{k} e^{-2\pi i k/N}\,|k\rangle\langle k| \qquad (6)

where: $S$ — the cyclic shift (translation) operator on $\mathbb{Z}_N$ ; $e^{-2\pi i k/N}$ — the eigenvalue of the shift on Fourier eigenstate $|\tilde k\rangle$ . In the Fourier basis translation is a pure phase, so periodic data is diagonal and its structure becomes discrete labels $k$ .

Derivation AWhy the quantum Fourier transform is unitary

The QFT is only a legitimate quantum operation if it is unitary — norm-preserving and reversible — so before using it we must prove $\mathrm{QFT}^{\dagger}\mathrm{QFT}=I$ . The goal here is to establish that directly from the matrix elements of equation (2), using the single most important identity in the subject: a complete sum of $N$ -th roots of unity vanishes unless the exponent is a multiple of $N$ . Every interference argument in Fourier-based quantum algorithms is this one geometric sum in a different costume, worth seeing cleanly once.

Step 1. Multiply the matrix by its conjugate transpose element-by-element. Since $(\mathrm{QFT})_{kj}=\omega^{jk}/\sqrt N$ and $\mathrm{QFT}^\dagger$ carries the conjugate phase $\omega^{-kj'}/\sqrt N$ , the $(j',j)$ entry is $(\mathrm{QFT}^{\dagger}\mathrm{QFT})_{j'j}=\frac{1}{N}\sum_{k} \omega^{k(j-j')}$ . Why: unitarity means the columns are orthonormal, and this sum is the inner product of columns $j$ and $j'$ .

Step 2. Evaluate the geometric series $\sum_{k=0}^{N-1}\omega^{k(j-j')}$ . If $j=j'$ every term is $1$ and the sum is $N$ . If $j\neq j'$ then $\omega^{(j-j')}\neq1$ is itself a nontrivial root of unity, and the finite geometric sum $\sum_{k=0}^{N-1}z^k=(z^N-1)/(z-1)=0$ because $z^N=\omega^{N(j-j')}=1$ . Hence $\sum_k\omega^{k(j-j')}=N\,\delta_{jj'}$ . Why: this "roots of unity sum to zero" fact is the mathematical form of destructive interference — off-diagonal overlaps cancel perfectly.

Step 3. Substitute back: $(\mathrm{QFT}^{\dagger}\mathrm{QFT})_{j'j}=\frac{1}{N}\,N\,\delta_{j'j}=\delta_{j'j}$ , so $\mathrm{QFT}^{\dagger}\mathrm{QFT}=I$ . The transform is unitary, its inverse is $\mathrm{QFT}^{\dagger}$ (the same matrix with $\omega\to\omega^{-1}$ ), and it runs backwards at identical cost. Why: the inverse QFT — not the forward one — appears at the end of phase estimation, so equal cost matters in practice.

Go deeper · Derivation B · 1 minFrom the exponential sum to the product-form circuit

Derivation BFrom the exponential sum to the product-form circuit

The definition (1) is a sum over $N=2^n$ terms, which looks like it should cost exponentially many operations. The goal here is to show it collapses into a tensor product of $n$ single-qubit states, and then to read the elementary circuit — Hadamards and controlled rotations — straight off that product. This is the Coppersmith factorization, the precise reason a transform over an exponentially large space needs only polynomially many gates.

Step 1. Expand the output index in binary, $k=\sum_{\ell=1}^{n}k_\ell 2^{n-\ell}$ , so that $k/2^n=\sum_\ell k_\ell 2^{-\ell}$ and the exponent becomes $jk/2^n=j\sum_\ell k_\ell 2^{-\ell}$ . Why: splitting $k$ into bits lets the one big sum split into independent per-qubit sums.

Step 2. Because the exponential of a sum is a product, $e^{2\pi i jk/2^n}=\prod_{\ell=1}^{n} e^{2\pi i\, j k_\ell 2^{-\ell}}$ , and summing over all $k$ turns the $\sum_k|k\rangle$ into a tensor product $\bigotimes_{\ell}\big(|0\rangle+e^{2\pi i j 2^{-\ell}}|1\rangle\big)$ , one factor for each output bit $k_\ell\in\{0,1\}$ . Why: this is where the state factorizes — no output entanglement, so each qubit is built separately.

Step 3. Simplify each phase. In $e^{2\pi i j 2^{-\ell}}$ the integer part of $j2^{-\ell}$ contributes $e^{2\pi i(\text{integer})}=1$ and drops out, leaving only the fractional binary tail: $e^{2\pi i j 2^{-\ell}}=e^{2\pi i\,0.j_{n-\ell+1}\cdots j_n}$ . This is precisely the product form (3). Why: only the low-order bits of $j$ survive in each factor, fixing which controls each gate needs.

Step 4. Build one output qubit. A Hadamard on qubit $a$ maps $|j_a\rangle\mapsto\frac{1}{\sqrt2}(|0\rangle+e^{2\pi i\,0.j_a}|1\rangle)$ , writing the leading fractional bit. Then each lower qubit $b>a$ supplies a controlled- $R_{b-a+1}$ that appends its bit, extending the phase to the full $0.j_a j_{a+1}\cdots j_n$ . Processing qubits $a=1,\dots,n$ in turn realizes every factor. Why: the controlled rotations stitch the less significant input bits into one qubit's relative phase.

Step 5. Count and clean up. The construction uses $n$ Hadamards, $\binom{n}{2}=n(n-1)/2$ controlled rotations, and $\lfloor n/2\rfloor$ SWAPs to reverse the output order, for $n(n+1)/2=O(n^2)$ gates total — the exponential improvement over the FFT's $O(2^n n)$ . Why: the swaps are needed because the product form delivers qubit $\ell$ holding $0.j_{n-\ell+1}\cdots j_n$ , in reversed significance.

Go deeper · Derivation C · 1 minHow a hidden period becomes a comb of measurable peaks

Derivation CHow a hidden period becomes a comb of measurable peaks

This is the derivation that makes the QFT useful: a state supported on an arithmetic progression of spacing $r$ is mapped to a state sharply peaked on the multiples of $N/r$ , so a single measurement returns a multiple of $N/r$ and thereby leaks the period $r$ . This is the exact interference mechanism behind order finding, and hence Shor's factoring algorithm. We take $N=2^n$ and a register holding an equal superposition over $x_0+\ell r$ with $r\mid N$ for cleanliness; the result is the boxed peak state.

\mathrm{QFT}_N\Big(\sqrt{\tfrac{r}{N}}\!\sum_{\ell=0}^{N/r-1}\!|x_0+\ell r\rangle\Big)=\frac{1}{\sqrt r}\sum_{s=0}^{r-1} e^{2\pi i x_0 s/r}\,\big|s\,\tfrac{N}{r}\big\rangle \qquad (7)

Step 1. Apply the transform term by term using linearity: $\mathrm{QFT}_N|x_0+\ell r\rangle=\frac{1}{\sqrt N}\sum_k e^{2\pi i(x_0+\ell r)k/N}|k\rangle$ . Why: the QFT is linear, so we may transform each term of the superposition separately and re-sum.

Step 2. Collect the pieces. Pulling out the offset phase $e^{2\pi i x_0 k/N}$ leaves an inner sum: the amplitude of $|k\rangle$ is $\sqrt{\tfrac{r}{N}}\,\tfrac{1}{\sqrt N}\,e^{2\pi i x_0 k/N}\sum_{\ell=0}^{N/r-1}e^{2\pi i \ell r k/N}$ . Why: the $\ell$ -dependence lives entirely in that inner geometric sum, where the selection happens.

Step 3. Evaluate the inner sum by the roots-of-unity identity. It equals $N/r$ when $rk/N$ is an integer — that is, when $k=sN/r$ for integer $s$ — and vanishes otherwise. So only the $r$ frequencies $k=0,\,N/r,\dots,(r-1)N/r$ survive. Why: the same geometric-sum cancellation as in the unitarity proof, here sculpting a comb.

Step 4. Read off the probabilities. At a surviving $k=sN/r$ the amplitude is $\sqrt{\tfrac{r}{N}}\cdot\tfrac{1}{\sqrt N}\cdot\tfrac{N}{r}=\tfrac{1}{\sqrt r}$ , so $\Pr[k=sN/r]=\big(\tfrac{r}{N}\big)\big(\tfrac{1}{N}\big)\big(\tfrac{N}{r}\big)^2=\tfrac{1}{r}$ , uniform over the $r$ peaks. Why: the outcome is a uniformly random multiple of $N/r$ , so one run pins down $N/r$ .

Step 5. Handle the realistic case $r\nmid N$ . The peaks are then no longer exactly at multiples of $N/r$ but stay sharply concentrated near $k/N\approx s/r$ ; the continued-fraction expansion of the measured $k/N$ recovers $s/r$ in lowest terms, and a couple of runs fix $r$ . Why: real order finding never has $r\mid 2^n$ , so continued fractions turn an approximate peak into an exact period.

Limiting cases

How the QFT specializes and degrades:

Case	Result	Meaning
$N=2$ (one qubit)	$\mathrm{QFT}_2=\frac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}=H$	the single-qubit QFT is exactly the Hadamard; the whole $\mathbb{Z}_2^n$ case is $H^{\otimes n}$ , the transform behind Deutsch–Jozsa, Bernstein–Vazirani and Simon
Approximate QFT	drop $R_k$ with $k>m$ , error $\le 2\pi n\,2^{-m}$	discarding rotations below angle $2\pi/2^m$ gives an $O(n\log n)$ -gate circuit with provably small operator-norm error; essential under fault tolerance
Inverse / phase estimation	$\mathrm{QFT}^{\dagger}\|j\rangle=\frac{1}{\sqrt N}\sum_k e^{-2\pi i jk/N}\|k\rangle$	phase estimation applies $\mathrm{QFT}^{\dagger}$ to read an eigenphase; the inverse just conjugates the phase, same gate count
Non-power-of-two $N$	no exact qubit tensor factorization	the clean product form needs $N=2^n$ ; for other $N$ one embeds into $\mathbb{Z}_{2^n}$ with $2^n\gtrsim N^2$ and recovers the answer by continued fractions

Common trapThe QFT is a quantum spectrum analyzer that reads out the whole Fourier transform

It is not. Measuring after the QFT collapses the state to a single index $k$ , drawn with probability $|\hat\psi_k|^2$ — one sample, not the vector of $N$ Fourier amplitudes, and the state is destroyed getting it. On its own the QFT therefore delivers no speedup at all. The exponential advantage appears only in a specific choreography: an oracle first prepares a state with hidden periodicity, the QFT concentrates that periodicity into a few sharp peaks, and — in factoring — classical continued-fraction post-processing turns the measured peak into the period. Two more conventions trip people up: the transform that ends phase estimation is the inverse QFT (phase $e^{-2\pi i jk/N}$ ), and the output qubits emerge in reversed bit order until the SWAP layer fixes them.

Worked examples

1 · Reading a period off the two-qubit QFT (fully worked)

Take $N=4$ ( $n=2$ ) and the period-2 state $|\psi\rangle=\tfrac{1}{\sqrt2}(|0\rangle+|2\rangle)$ . Apply $\mathrm{QFT}_4$ explicitly and show the output is peaked on the multiples of $N/r=2$ .

Step 1. Write the two needed columns of $\mathrm{QFT}_4$ from equation (1) with $\omega=e^{2\pi i/4}=i$ . For $|0\rangle$ : $\mathrm{QFT}_4|0\rangle=\tfrac12(|0\rangle+|1\rangle+|2\rangle+|3\rangle)$ . For $|2\rangle$ the phases are $\omega^{2k}=(-1)^k$ , so $\mathrm{QFT}_4|2\rangle=\tfrac12(|0\rangle-|1\rangle+|2\rangle-|3\rangle)$ .

Step 2. Superpose with the $1/\sqrt2$ prefactor: $\mathrm{QFT}_4|\psi\rangle=\tfrac{1}{\sqrt2}\cdot\tfrac12\big[(|0\rangle+|1\rangle+|2\rangle+|3\rangle)+(|0\rangle-|1\rangle+|2\rangle-|3\rangle)\big]$ . The $|1\rangle,|3\rangle$ terms cancel and the $|0\rangle,|2\rangle$ terms reinforce: $=\tfrac{1}{2\sqrt2}\big(2|0\rangle+2|2\rangle\big)=\tfrac{1}{\sqrt2}\big(|0\rangle+|2\rangle\big)$ .

Step 3. Read the distribution. Measurement gives $k=0$ or $k=2$ , each with probability $\tfrac12$ , and never $k=1$ or $k=3$ — exactly the multiples of $N/r=4/2=2$ , matching equation (7) with $r=2$ . The period-2 input produces peaks only at $k=0$ and $k=2$ , each with probability 0.5; the spacing $N/r=2$ betrays $r=2$ .

2 · The exponential gate advantage, and what the approximate QFT saves

Compare the quantum and classical cost of Fourier-transforming registers of $n=10$ and $n=50$ qubits, then estimate how much the approximate QFT trims the large case.

Step 1. For $n=10$ ( $N=1024$ ): the exact QFT uses $n(n+1)/2=10\cdot11/2=\mathbf{55}$ Hadamard-and-controlled-phase gates plus $\lfloor n/2\rfloor=5$ SWAPs, so $\mathbf{60}$ gates total. The classical FFT on $1024$ points costs $N\log_2 N=1024\cdot10=\mathbf{10\,240}$ operations — already a factor of roughly $170$ .

Step 2. For $n=50$ ( $N=2^{50}\approx1.1\times10^{15}$ ): the QFT still needs only $50\cdot51/2=\mathbf{1275}$ gates, while the classical FFT needs $N\log_2 N=2^{50}\cdot50\approx5.6\times10^{16}$ operations — a circuit smaller by about 13 orders of magnitude, an exponential separation rather than a constant-factor win.

Step 3. Trim with the approximate QFT. To hold the operator-norm error below $\varepsilon$ it suffices to keep controlled rotations down to level $m\approx\log_2(n/\varepsilon)$ ; for $n=50$ , $\varepsilon=10^{-2}$ this is $m\approx\log_2(5000)\approx12.3$ , so $m=13$ . Each qubit then carries at most $m$ rotations, giving $\sim n\,m\approx 50\cdot13=\mathbf{650}$ — about half the exact count, and an $O(n\log n)$ scaling that keeps the fault-tolerant rotation-synthesis cost bounded. Exact: $O(n^2)$ ; approximate: $O(n\log n)$ with error $\le 2\pi n\,2^{-m}$ .

Physics of the portrait

The QFT is where the classical fast Fourier transform meets quantum interference and becomes exponentially cheaper. Its efficient circuit has a clear author: the cryptographer who, in a short 1994 IBM note written in the wake of Shor's algorithm, wrote down both the product-form circuit and its approximate cousin.

Origins · 1 minDon Coppersmith and how this was discovered

Don Coppersmith

b. 1950 · IBM cryptographer who devised the efficient and approximate quantum Fourier transform circuit

Don Coppersmith is an American mathematician and cryptographer who spent most of his career at IBM's Thomas J. Watson Research Center — a gold medallist at the 1971 International Mathematical Olympiad, a three-time Putnam Fellow, and the author of a remarkable spread of results from the design of DES to the Coppersmith–Winograd matrix-multiplication algorithm and "Coppersmith's method" of small-root attacks on RSA. In 1994, immediately after Peter Shor announced a polynomial-time quantum factoring algorithm, Coppersmith circulated a brief IBM note, An Approximate Fourier Transform Useful in Quantum Factoring, that did two lasting things. First, it laid out the tensor-product ("product form") circuit for the QFT on $n$ qubits — the $O(n^2)$ arrangement of Hadamards and controlled-phase rotations that every textbook now draws. Second, it observed that the controlled rotations shrink geometrically with qubit separation, so the tiny ones can simply be dropped: the resulting approximate transform costs only $O(n\log n)$ gates yet is provably close in operator norm. That second point matters enormously for fault-tolerant machines, where each precise rotation is expensive to synthesize from a discrete gate set — the approximate QFT is what keeps Shor's algorithm affordable in a resource count.

History

1965

— Cooley and Tukey publish the classical fast Fourier transform, cost O(N log N)

1994

— Shor gives a polynomial-time quantum algorithm for factoring and discrete logarithms, built on the QFT

1994

— Coppersmith describes the O(n²) product-form circuit and its O(n log n) approximate version

1995

— Kitaev recasts factoring through quantum phase estimation, generalizing the QFT's role

1996

— Cleve, Ekert, Macchiavello and Mosca frame these speedups as the abelian hidden-subgroup problem

Going further

Texts. Nielsen & Chuang, Quantum Computation and Quantum Information, §5.1 (QFT) and §5.3 (order finding) · Preskill, Lecture Notes on Quantum Computation, Ch. 6 · Kitaev, Shen & Vyalyi, Classical and Quantum Computation, Ch. 13 · Mermin, Quantum Computer Science, Ch. 3 · Watrous, The Theory of Quantum Information · Coppersmith, An Approximate Fourier Transform Useful in Quantum Factoring (IBM Research, 1994). The peak probability in the period-to-peaks result is $\big(\tfrac{r}{N}\big)\big(\tfrac1N\big)\big(\tfrac{N}{r}\big)^2=\tfrac1r$ (amplitude $1/\sqrt r$ ). Key identities to keep in mind: $\mathrm{QFT}^\dagger\mathrm{QFT}=I$ ; the binary-fraction factorization of $e^{2\pi i jk/2^n}$ underlies the product form; the gate count is $\binom n2+n$ ; the two-qubit example gives $\tfrac{1}{\sqrt2}(|0\rangle+|2\rangle)\mapsto\tfrac{1}{\sqrt2}(|0\rangle+|2\rangle)$ ; and $R_2=S,\ R_3=T,\ \mathrm{QFT}_2=H$ .

Builds on: Quantum Parallelism and the Oracle Model · Simon's Algorithm. Leads to: Quantum Phase Estimation · Order Finding and Period Finding · Shor's Factoring Algorithm · Hidden Subgroup Problem.

Ask the tutor: Ask me to run the two- or three-qubit QFT by hand on a state of your choice, or to walk through how the period-to-peaks interference powers Shor's algorithm.

Is the QFT just the classical FFT run on a quantum computer?

Not quite — it is the same linear map, but the quantum version buys something the classical one cannot. The classical FFT explicitly outputs all $N$ Fourier amplitudes in $O(N\log N)$ steps. The QFT acts on the $N=2^n$ amplitudes encoded in the state of $n$ qubits and rearranges them in $O(n^2)$ gates — exponentially fewer operations. The catch is access: you never see all $N$ output amplitudes, only one measured index. So the QFT is not a faster FFT for classical data; it is a device for interfering amplitudes you have already arranged, so a measurement lands informatively.

Why do the output qubits come out in reversed bit order?

It falls straight out of the product form. Output qubit $\ell$ ends up holding the binary fraction $0.j_{n-\ell+1}\cdots j_n$ , so the first output qubit carries only the least significant input bit $0.j_n$ , while the last carries the whole tail $0.j_1\cdots j_n$ . The significance order of the outputs is therefore the mirror image of the inputs. You fix it with $\lfloor n/2\rfloor$ SWAP gates exchanging qubit $\ell$ with qubit $n-\ell+1$ , or simply relabel the wires and let the next circuit absorb the reversal. Either way it is bookkeeping, not physics.

What is the QFT over Z₂ⁿ, and why does it look so different?

Over the group $\mathbb{Z}_2^n$ — the Boolean cube, not the cyclic group of order $2^n$ — the Fourier transform is simply $H^{\otimes n}$ , a Hadamard on every qubit and nothing else. There are no controlled-phase gates because every character is just $(-1)^{x\cdot y}$ , a sign rather than a general root of unity. This is the transform behind Deutsch–Jozsa, Bernstein–Vazirani and Simon's algorithm. It differs from the $\mathbb{Z}_{2^n}$ QFT because the underlying group differs: $\mathbb{Z}_2^n$ is a product of $n$ two-element groups, whereas $\mathbb{Z}_{2^n}$ is a single cyclic group of size $2^n$ , so their character tables — hence their Fourier transforms — are genuinely distinct.

Where exactly does the exponential speedup in Shor's algorithm come from?

Not from the QFT by itself — the speedup is a partnership. First, a modular-exponentiation oracle uses quantum parallelism to prepare a state periodic in the exponent register, with period equal to the multiplicative order $r$ you want. Second, the QFT converts that period into a distribution sharply peaked at multiples of $2^n/r$ — this is where interference does the real work, cheaply. Third, a measurement plus a classical continued-fraction computation extracts $r$ . Remove any leg and the advantage vanishes: without the oracle there is no periodicity to transform, without the QFT the period stays hidden in inaccessible phases, and without continued fractions the measured peak is not yet the answer.

How accurate does each controlled rotation have to be?

Less accurate than you would guess, which is the whole point of the approximate QFT. The controlled rotation between qubits $a$ and $b$ applies an angle $2\pi/2^{\,b-a+1}$ , which halves with every extra qubit of separation, so distant pairs contribute exponentially tiny phases. Coppersmith noticed you can simply omit every rotation below a cutoff level $m$ and keep the total operator-norm error under $2\pi n\,2^{-m}$ ; choosing $m\approx\log_2(n/\varepsilon)$ holds the error below $\varepsilon$ while cutting the gate count from $O(n^2)$ to $O(n\log n)$ . This matters most under fault tolerance, where each arbitrary rotation is expensive to synthesize from a discrete gate set.

In what sense is the QFT the "natural" transform for periodic problems?

Because it diagonalizes the cyclic shift $S|x\rangle=|x+1\bmod N\rangle$ . The eigenvectors of $S$ are precisely the Fourier states $|\tilde k\rangle$ , with eigenvalues $e^{2\pi i k/N}$ — a pure phase. Any operator built out of shifts (any translation-invariant, i.e. periodic, structure) is therefore diagonal in the Fourier basis, so what was smeared across many positions in real space becomes a set of isolated labels $k$ . That is exactly why a hidden period turns into discrete, measurable peaks: periodicity is invariance under a shift, and the QFT is the basis in which shifts stop mixing states and act by phases alone.