Quantum Fourier transform

The problem it solves

Given a sequence of 2^n numbers encoded in the amplitudes of an n-qubit quantum state, the Quantum Fourier Transform (QFT) produces a new quantum state whose amplitudes are the discrete Fourier transform of the original sequence. The discrete Fourier transform is a classical workhorse that decomposes any signal into its constituent frequencies, revealing hidden periodicities. The QFT performs this same mathematical operation on exponentially large amplitude vectors using only a polynomial number of quantum gate operations, making it an indispensable subroutine for algorithms that need to detect periodicity in quantum states [1, 2].

How it works (technical)

The QFT maps a computational basis state |j> to an equal superposition of all basis states, where each basis state |k> receives a phase of exp(2 pi i j k / 2^n). This is precisely the action of the discrete Fourier transform on the standard basis, lifted to operate on quantum amplitudes. The circuit that realises this consists of a Hadamard gate on each qubit followed by a ladder of controlled phase-rotation gates with angles pi / 2^m for increasing m, and concludes with a reversal of the qubit ordering via SWAP gates [2]. The total gate count is O(n^2) two-qubit gates, which is efficient in n even though the state vector the transform acts on has 2^n entries [1].

Comparing complexities requires care. The classical Fast Fourier Transform (FFT) processes an explicit array of 2^n numbers using O(n times 2^n) arithmetic operations. The QFT circuit uses only O(n^2) gates, but this does not directly imply a speedup on its own: loading 2^n classical numbers into a quantum state already takes exponential resources under most models, and reading the transformed amplitudes requires repeated measurement. The QFT's advantage materialises specifically in settings where the input state is prepared efficiently by a preceding quantum subroutine, which is exactly the case inside phase estimation and order-finding.

Phase estimation is the primary consumer of the QFT in practice. A unitary operator U is applied to an eigenstate a controlled number of times, accumulating a phase that encodes an eigenvalue. The QFT then converts this phase, spread across the amplitudes of an ancilla register, into a basis state that can be measured and interpreted as a binary fraction. This composition is the algorithmic heart of Shor's factoring algorithm, HHL-style linear-systems solvers, and quantum simulation routines for estimating ground-state energies [2].

The approximate QFT, introduced by Coppersmith [1], discards controlled-rotation gates whose angles are smaller than a chosen threshold. This reduces the gate count to O(n log n) while introducing only a bounded error in the output amplitudes, which is acceptable for phase estimation because the measurement step is already probabilistic. The approximation is important for fault-tolerant implementations where the compilation cost of small-angle rotations can dominate the total resource budget.

What it's good for

The QFT is a subroutine rather than a standalone algorithm, so its use cases are inherited from the algorithms that embed it. Demonstrated and well-established uses include: integer factoring via Shor's algorithm, where the QFT extracts the period of a modular exponential function; quantum phase estimation, which underlies essentially all quantum algorithms that need eigenvalue information; and discrete logarithm computation over cyclic groups. Prospective and research-stage uses include: quantum simulation of physical systems where energy eigenvalues are estimated by phase estimation circuits; solving certain structured linear systems; and signal-processing subroutines inside quantum machine-learning proposals. All prospective uses require fault-tolerant hardware that is not yet available, and the practical advantage in each case depends heavily on assumptions about state preparation and readout.

Known results

Coppersmith's original 1994 report established the O(n^2)-gate exact circuit and introduced the approximate variant that reduces depth to O(n log n) by discarding small-angle rotations below a precision threshold [1]. Nielsen and Chuang present a clean proof that the QFT circuit is correct and that the approximate version produces output within a controllable distance of the exact result [2]. The QFT is provably optimal up to constant factors for the task of implementing the discrete Fourier transform unitarily: no circuit can do it in fewer than O(n^2) gates in general on a nearest-neighbour architecture, making Coppersmith's construction essentially tight. Small-scale QFT circuits have been demonstrated experimentally on NMR systems, trapped-ion processors, and superconducting-qubit platforms, verifying the circuit structure at sizes ranging from 2 to roughly 10 qubits, though these demonstrations do not themselves yield a computational speedup [2].

Caveats

The QFT does not deliver a standalone exponential speedup; it is only advantageous inside a larger algorithm where the input state is prepared cheaply by a preceding quantum step. If you need to Fourier-transform an explicitly given classical dataset, loading that data into a quantum state requires quantum random-access memory (QRAM) or an equivalent state-preparation circuit, both of which are either unproven at scale or expensive enough to erase any gate-count advantage [2]. Reading out the full transformed amplitude vector is impossible without exponentially many measurements, so the QFT is useful only when a small number of measurements of the output state are sufficient to answer the question at hand. All practically relevant uses of the QFT at scale require fault-tolerant quantum hardware with error-corrected logical qubits; current noisy intermediate-scale devices can execute the circuit for small n but cannot sustain the coherence needed for the deep circuits that arise in, for example, factoring large integers. The approximate QFT [1] reduces rotation-gate overhead but introduces bounded errors that must be accounted for in the overall algorithm's error budget.

Try it in Qiskit

An original, self-contained example written for this catalog (Qiskit ≥ 1.0 with qiskit-aer). Download it and run it locally.

```python
"""
Quantum Fourier Transform (QFT) -- catalog example
Demonstrates a 3-qubit QFT on a simple computational basis input state,
then verifies the output by sampling and by statevector inspection.
Written for Qiskit 1.x with qiskit-aer.
"""

import math
import numpy as np
from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector
from qiskit_aer import AerSimulator
from qiskit_aer.primitives import Sampler

# ------------------------------------------------------------------
# 1. Build the QFT circuit for n qubits.
#    The circuit applies:
#      - a Hadamard gate to each target qubit  (creates superposition)
#      - controlled phase rotations CP(pi/2^k) from every later qubit
#        (entangles qubits so amplitudes pick up the correct phases)
#      - SWAP gates at the end to reverse qubit ordering
# ------------------------------------------------------------------

def qft_circuit(n: int) -> QuantumCircuit:
    """Return an n-qubit QFT circuit (no inverse, no barriers for clarity)."""
    qc = QuantumCircuit(n, name="QFT")

    for target in range(n):
        # Hadamard puts the target qubit into equal superposition
        qc.h(target)

        # Controlled phase rotations from each subsequent qubit
        for ctrl in range(target + 1, n):
            angle = math.pi / (2 ** (ctrl - target))
            qc.cp(angle, ctrl, target)

    # Reverse qubit order so the output matches the standard DFT convention
    for i in range(n // 2):
        qc.swap(i, n - 1 - i)

    return qc


# ------------------------------------------------------------------
# 2. Choose an input state: |5> on 3 qubits  (binary 101)
#    We prepare this by flipping qubits 0 and 2 with X gates.
# ------------------------------------------------------------------

n_qubits = 3
input_index = 5  # the integer whose computational basis state we transform

prep = QuantumCircuit(n_qubits)
# Encode |input_index> in binary: qubit 0 is the least-significant bit
for bit in range(n_qubits):
    if (input_index >> bit) & 1:
        prep.x(bit)

# Attach the QFT circuit after state preparation
qft = qft_circuit(n_qubits)
full_circuit = prep.compose(qft)
full_circuit.measure_all()

print("Circuit:")
print(full_circuit.draw(fold=-1))

# ------------------------------------------------------------------
# 3. Verify the output using exact statevector simulation (no measurement).
#    The QFT of |j> on N = 2^n points should give equal-magnitude amplitudes
#    with phases exp(2 pi i * j * k / N) for output index k.
# ------------------------------------------------------------------

# Build a version without measurements for statevector inspection
full_no_meas = prep.compose(qft)
sv = Statevector(full_no_meas)

N = 2 ** n_qubits
print(f"\nStatevector amplitudes after QFT of |{input_index}>  (N={N}):")
print(f"{'State':>6}  {'Amplitude magnitude':>20}  {'Phase (degrees)':>18}  {'Expected phase (deg)':>22}")

for k, amp in enumerate(sv.data):
    # Expected amplitude: 1/sqrt(N) * exp(2*pi*i * input_index * k / N)
    expected_phase_deg = (360.0 * input_index * k / N) % 360.0
    actual_phase_deg = math.degrees(np.angle(amp)) % 360.0
    magnitude = abs(amp)
    print(
        f"  |{k:>2}>  {magnitude:>20.6f}  {actual_phase_deg:>18.2f}  {expected_phase_deg:>22.2f}"
    )

expected_magnitude = 1.0 / math.sqrt(N)
print(f"\nAll magnitudes should equal 1/sqrt({N}) = {expected_magnitude:.6f}")

# ------------------------------------------------------------------
# 4. Sample the circuit on AerSimulator to show the measurement outcome.
#    Because all output amplitudes are equal in magnitude, all 2^n basis
#    states appear with roughly equal frequency -- just as the DFT of a
#    single basis vector predicts.
# ------------------------------------------------------------------

simulator = AerSimulator()
sampler = Sampler()
job = sampler.run([full_circuit], shots=4096)
counts = job.result()[0].data.meas.get_counts()

print("\nMeasurement counts (should be roughly uniform across all 8 states):")
for state in sorted(counts):
    bar = "#" * (counts[state] // 20)
    print(f"  {state}: {counts[state]:>5}  {bar}")
```