The quantum Fourier transform (QFT) is a central subroutine in quantum algorithms, but its circuit ordering, phase conventions, and output interpretation can be easy to get wrong. This guide explains the intuition, derives a practical circuit, shows exact and approximate implementations in Qiskit and Cirq, and gives a repeatable way to verify amplitudes, gate counts, and phase-estimation results.
Overview
The QFT is the quantum analogue of the discrete Fourier transform. For an n-qubit register with N = 2n basis states, it maps a computational basis state |x⟩ to a state whose amplitudes contain regularly spaced phases:
QFT|x⟩ = 1/√N Σy=0N−1 exp(2πixy/N)|y⟩.
Unlike a classical Fourier transform, the QFT does not require you to read every transformed amplitude. Measurement still returns only a classical bit string. Its value comes from placing the transformed register inside a larger algorithm, such as quantum phase estimation, where interference makes useful phase information appear as a concentrated measurement distribution.
The standard decomposition uses three ingredients:
- Hadamard gates, which create equal superpositions and introduce a local phase;
- controlled phase-rotation gates, which add relationships between qubits; and
- SWAP gates, which reverse the order of the output qubits.
For n qubits, the straightforward exact QFT uses n Hadamards, n(n−1)/2 controlled phase rotations, and floor(n/2) swaps if the final bit reversal is implemented explicitly. Its two-qubit gate count grows quadratically, although it is still far smaller than a generic dense unitary decomposition.
Be precise about conventions. Some circuit diagrams omit the final swaps and call the reversed register the QFT output. That is valid when the surrounding algorithm expects reversed bit order, but it will appear incorrect if you compare the result with a formula using ordinary integer ordering.
How to estimate
1. Choose the register size and input state
Set n and decide whether the input is a basis state, a prepared superposition, or the output of another circuit. The QFT acts linearly, so a basis-state test is useful for debugging, but it does not represent every phase-estimation workload.
2. Build the exact circuit
A common construction processes qubits from the most significant side. Apply a Hadamard to the current qubit, then controlled rotations between that qubit and the remaining qubits. The rotation angle decreases with separation: an interaction at distance d uses an angle proportional to π/2d. Finish with pairwise swaps to reverse the register.
The inverse QFT reverses the operation order, uses the conjugate (negative) rotation angles, and applies the swaps in reverse order. Because the circuit is unitary, a reliable inverse-QFT test is to apply QFT followed by inverse QFT and check that the original state is restored.
3. Estimate resources
For an exact implementation with n qubits:
- Hadamards: n
- Controlled phase rotations: n(n−1)/2
- Explicit bit-reversal swaps: floor(n/2)
These counts describe the logical circuit before transpilation. Hardware connectivity, native gate sets, and optimization settings can add operations or change depth. For a hardware estimate, inspect the transpiled circuit rather than relying only on the abstract QFT formula. The same principle applies to simulator runtime: state-vector simulation generally scales with the dimension of the full state, 2n, while circuit gate count is only one part of the workload.
4. Decide whether approximation is acceptable
An approximate QFT removes small-angle controlled rotations. If the maximum retained interaction distance is k, with k < n, the number of retained controlled rotations is approximately:
kn − k(k+1)/2.
Use this as a logical count for a simple distance cutoff. It excludes the n Hadamards and any explicit swaps. Increasing k improves fidelity to the exact QFT but increases gate count. The right cutoff depends on the phase resolution required by the larger algorithm, not on gate count alone.
Inputs and assumptions
Record the following inputs before comparing implementations:
| Input | Why it matters |
|---|---|
| Number of qubits, n | Sets the transform dimension, exact rotation count, and simulator state size. |
| Input state | Determines the ideal amplitudes and whether the output should be a uniform, peaked, or interference-heavy distribution. |
| Bit-order convention | Determines whether swaps are required and how measured strings map to integers. |
| Approximation cutoff, k | Controls which small-angle rotations are removed. |
| Execution model | Statevector simulation exposes amplitudes; shot-based simulation and hardware expose sampled counts. |
| Phase-estimation precision | Determines how many counting qubits and how much phase resolution the inverse QFT must support. |
For amplitude verification, compare the simulated statevector with the mathematical target up to the framework's qubit-order convention and global phase. A global phase does not affect measurement probabilities, so comparing raw complex numbers without accounting for it can produce a false failure.
For measurement verification, calculate probabilities as the squared magnitudes of amplitudes, then compare those probabilities with normalized shot counts. Do not expect a finite-shot histogram to match ideal probabilities exactly. If a phase-estimation result is spread across neighboring bit strings, inspect the encoded phase, register order, controlled-unitary powers, and inverse-QFT direction before assuming the QFT is wrong.
Worked examples
Qiskit: a small exact QFT
The following construction is intentionally explicit so that the gate pattern can be inspected. It uses a little-endian indexing convention and includes the final swaps.
from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector
import numpy as np
def qft(qc, qubits, inverse=False):
n = len(qubits)
indices = list(range(n))
if inverse:
indices = indices[::-1]
for i in indices:
if inverse:
for j in range(i):
angle = -np.pi / (2 ** (i - j))
qc.cp(angle, qubits[j], qubits[i])
qc.h(qubits[i])
else:
qc.h(qubits[i])
for j in range(i + 1, n):
angle = np.pi / (2 ** (j - i))
qc.cp(angle, qubits[j], qubits[i])
for a in range(n // 2):
qc.swap(qubits[a], qubits[n - a - 1])
n = 3
qc = QuantumCircuit(n)
qc.x(0) # basis-state test input
qft(qc, list(range(n)))
state = Statevector.from_instruction(qc)
print(qc.draw())
print(state.probabilities_dict())
Framework versions can differ in how controlled rotations and bit strings are displayed, so use the circuit diagram and statevector dimensions as part of the check. For an inverse test, construct a second circuit containing the inverse operation or call the inverse of a separately built QFT circuit, then verify that the final state returns to the prepared input.
Cirq: inspect the same pattern
Cirq expresses the controlled phase operation through controlled gates. This example keeps the construction visible rather than relying on a convenience transform.
import cirq
import numpy as np
def qft(qubits):
circuit = cirq.Circuit()
n = len(qubits)
for target in range(n):
circuit.append(cirq.H(qubits[target]))
for control in range(target + 1, n):
angle = 1 / (2 ** (control - target + 1))
circuit.append(cirq.CZ(qubits[control], qubits[target]) ** angle)
for i in range(n // 2):
circuit.append(cirq.SWAP(qubits[i], qubits[n - i - 1]))
return circuit
qubits = cirq.LineQubit.range(3)
circuit = qft(qubits)
print(circuit)
result = cirq.Simulator().simulate(circuit)
print(result.final_state_vector)
When comparing Qiskit and Cirq, first align qubit indexing and phase-angle conventions. Then compare probabilities rather than printed amplitude order alone. A useful regression test is to generate the ideal target vector independently, reorder entries if necessary, and assert that the maximum amplitude or probability error stays below your chosen tolerance.
Exact versus approximate QFT
| Version | Controlled rotations | Logical depth trend | Expected accuracy |
|---|---|---|---|
| Exact, n qubits | n(n−1)/2 | Quadratic before scheduling and hardware mapping | Matches the mathematical QFT up to numerical and convention errors |
| Approximate, cutoff k | Approximately kn − k(k+1)/2 when k < n | Lower as k decreases, subject to scheduling | Usually lower phase fidelity; evaluate against the target workload |
For example, with eight qubits, the exact construction has 28 controlled rotations. A distance cutoff of three retains 3×8 − 3×4/2 = 18 controlled rotations, before counting Hadamards and swaps. That reduction is meaningful only if the discarded rotations do not erase the phase resolution needed by the algorithm. Test both circuits on the actual input states used by your application.
A practical verification checklist is:
- Confirm the number of qubits and the register order.
- Compare QFT followed by inverse QFT with the original state.
- Check statevector probabilities against an independently calculated target.
- Count logical gates before and after transpilation or decomposition.
- For shots, compare normalized counts with ideal probabilities and record the shot count.
- In phase estimation, verify the controlled powers, inverse-QFT sign, swaps, and binary interpretation of the measured string.
When to recalculate
Recalculate the circuit and resource estimate whenever you change the qubit count, input-state preparation, approximation cutoff, register order, or phase-estimation precision. These changes can alter both the expected output distribution and the useful accuracy threshold.
Also rerun the checks after changing SDK versions, transpilation settings, simulator backends, or target hardware. Gate names may be decomposed differently, and hardware connectivity can change the physical depth even when the logical QFT is unchanged. If you move from simulation to hardware, include calibration-aware analysis and error mitigation only as separate, documented steps; begin with an ideal reference circuit.
Keep a small regression notebook or test script that records n, cutoff k, input state, circuit depth, gate counts, statevector error, and sampled distributions. Updating that record every six months, or whenever the surrounding phase-estimation circuit changes, makes the QFT a measurable component rather than a black box. For broader circuit optimization, pair this workflow with guidance on quantum circuit transpilation and depth reduction; for noisy-device validation, review randomized benchmarking and quantum error-correction basics.