Quantum Fourier Transform

The QFT is the quantum analogue of the discrete Fourier transform, acting on amplitudes rather than a classical vector. It underlies period finding, phase estimation, and several Hamiltonian-simulation techniques.

TakesNothingWhat joins here

No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.

Nothing in the Atlas meets this end.

ReturnsNothingWhat joins here

No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.

Nothing in the Atlas meets this end.

This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →

The Quantum Fourier Transform on $n$ qubits ( $N=2^n$ basis states) is the unitary

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

Unlike the classical discrete Fourier transform, which returns a full length- $N$ output vector, the QFT acts on the amplitudes of an $n$ -qubit register and its output can only be sampled through measurement — it is a resource for building algorithms, not a way to read out a classical spectrum for free.

Circuit structure. The standard decomposition applies, for each qubit $j$ (most significant first), a Hadamard followed by controlled phase gates $R_k=\mathrm{diag}(1,e^{2\pi i/2^k})$ controlled by the less significant qubits, and finishes with a reversal of qubit order (implemented as $\lfloor n/2\rfloor$ SWAPs, or by relabeling wires in software). This gives exactly $n$ Hadamards and $n(n-1)/2$ controlled-phase gates: $O(n^2)$ gates total. Coppersmith's approximate QFT drops controlled rotations with angle smaller than $2\pi/2^m$ for a cutoff $m$ , reducing the gate count to $O(n\log n)$ while introducing only exponentially small error for many downstream uses (period finding, phase estimation).

Small worked instance. Take $n=3$ ( $N=8$ ) and the input $|j=0\rangle = |000\rangle$ . Every phase factor $e^{2\pi i \cdot 0 \cdot k/8}=1$ , so

\mathrm{QFT}_8|000\rangle = \frac{1}{\sqrt8}\sum_{k=0}^{7}|k\rangle,

exactly the state produced by applying $H$ to each of the three qubits independently — a directly checkable identity, since no controlled phase can fire when every control qubit is $|0\rangle$ . For $j=1$ , $\mathrm{QFT}_8|001\rangle=\frac{1}{\sqrt8}\sum_k e^{2\pi i k/8}|k\rangle$ , i.e. the amplitudes trace out the eight 8th roots of unity in order — exactly the classical DFT of a Kronecker delta at index 1.

Where it is used. The QFT (or its inverse) is the last step of quantum phase estimation, the core of Shor's period-finding routine, and a building block for quantum arithmetic and some Hamiltonian-simulation schemes.

TakesNothingWhat joins here

No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.

Nothing in the Atlas meets this end.

ReturnsNothingWhat joins here

No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.

Nothing in the Atlas meets this end.

This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →

Qubits: 3 shown (n general)
Depth: O(n²) gates exact · O(n log n) approximate
Gate count (n=3): 3 H + 3 CP + 1 SWAP
Formula: QFT|j⟩ = (1/√N) Σ_k e^{2πijk/N}|k⟩
Exact gate count: O(n²)
Approximate variant: O(n log n), Coppersmith 2002

H×3 on q[0], q[1], q[2]
Controlled phases on q[0], q[1], q[2]
Swap (reversal) on q[0], q[2]

Uniform across 8 outcomes (|0⟩ input)13%

8th-root-of-unity phase pattern (|1⟩ input)13%

Quantum vs classical

Metric	Classical	Quantum
Operation count	O(N log N) — FFT	O(n²) = O(log²N)
Register size	N complex values	n = log₂N qubits
Output access	full vector	sampled amplitudes only

Classical baseline

The classical fast Fourier transform (FFT) computes a full length-N output vector explicitly in O(N log N) arithmetic operations.

Quantum claim

The QFT transforms the amplitudes of an n = log N qubit register with O(n²) gates, but the output is only accessible through sampling, not as a free classical vector.

How to compare

Compare circuit depth, approximation cutoff, state preparation cost, and the actual downstream measurement objective against the classical FFT cost for the same task.

Nobody has reviewed this record for gaps yet.

FrameworkNative

quantum_fourier_transform.py

from qiskit import QuantumCircuit
import numpy as np

def qft(n):
    qc = QuantumCircuit(n, name="QFT")
    for j in range(n):
        qc.h(j)
        for k in range(j + 1, n):
            qc.cp(np.pi / 2 ** (k - j), k, j)
    for i in range(n // 2):
        qc.swap(i, n - i - 1)
    return qc

qc = QuantumCircuit(3, 3)
qc.append(qft(3), [0, 1, 2])
qc.measure(range(3), range(3))

FINAL_CIRCUIT = qc

Where this sits

This record is named by the layer graph at:

Phase estimation into an ancilla register Method
Takes A circuit for U that can be applied as controlled U^(2^j), a preparation routine for a state whose overlap with the target eigenvector is not negligible, the number of bits of the phase wanted, and the failure probability that may be tolerated. Returns An estimate of the eigenphase to the requested number of bits, with the failure probability it was obtained at, plus the two costs that actually differ between routes: how many ancillas were held at once, and how many sequential rounds were run.

QFT then its inverse, on |0101⟩

Quantum vs classical

Classical baseline

Quantum claim

How to compare

Where this sits

Related entries

References