algorithms intermediate · 25 min read · April 22, 2026

Quantum Fourier Transform and Phase Estimation

The QFT is the quantum cousin of the classical discrete Fourier transform — but it runs in O(n²) instead of O(n·2ⁿ), which is where many quantum speedups ultimately come from. This tutorial derives the QFT circuit, explains Quantum Phase Estimation (the subroutine inside Shor, HHL, and VQE), and delivers complete Qiskit implementations.

Prerequisites: Tutorial 10: Grover and Amplitude Amplification

If you had to name the single most important quantum subroutine, it would be the Quantum Fourier Transform. It’s the engine under Shor’s algorithm (factoring), HHL (linear systems), quantum phase estimation (molecular simulation, VQE), quantum counting, and a dozen other algorithms. Classical DFT takes $O(N \log N)$ time on $N = 2^n$ data points; QFT takes $O(n^2)$ gates on a quantum state encoding those $N$ points — exponentially faster, with the caveat that you can’t read out all the Fourier coefficients (that’s where algorithms get creative).

Quantum Phase Estimation (QPE) uses the QFT as its final step to solve a specific problem: given a unitary $U$ and an eigenvector $|\psi\rangle$ with eigenvalue $e^{2\pi i \varphi}$, estimate $\varphi$. That sounds abstract; it’s actually the missing puzzle piece for Shor, for ground-state chemistry, and for half the “quantum advantage” demos.

The classical DFT, quickly

The discrete Fourier transform takes a sequence of $N$ complex numbers $(x_0, x_1, ..., x_{N-1})$ to another sequence $(y_0, y_1, ..., y_{N-1})$ via:

$$y_k \;=\; \frac{1}{\sqrt{N}}\sum_{j=0}^{N-1} x_j \,e^{2\pi i j k / N}.$$

On $N = 2^n$ points, the Fast Fourier Transform runs in $O(N \log N) = O(n \cdot 2^n)$ time.

The Quantum Fourier Transform

The QFT is the same unitary, but applied to amplitudes of a quantum state rather than elements of a classical array. If the input state is $|\psi_\text{in}\rangle = \sum_{j=0}^{N-1} x_j|j\rangle$, the QFT produces:

$$\text{QFT}\,|\psi_\text{in}\rangle \;=\; \sum_{k=0}^{N-1} y_k|k\rangle,$$

where the $y_k$ are the DFT of the $x_j$. Equivalently, the action on a basis state is:

$$\text{QFT}\,|j\rangle \;=\; \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} e^{2\pi i j k / N}\,|k\rangle.$$

Deriving the circuit

Write $j$ as an $n$-bit binary string $j = j_{n-1} j_{n-2} \cdots j_0$ and $k$ similarly. Substitute into the phase $e^{2\pi i j k / 2^n}$ and expand. After some manipulation (see any intro QC textbook for full algebra) you get the product form:

$$\text{QFT}\,|j\rangle \;=\; \frac{1}{\sqrt{2^n}}\bigotimes_{\ell=0}^{n-1}\left(|0\rangle + e^{2\pi i \cdot 0.j_\ell j_{\ell-1} \cdots j_0}|1\rangle\right),$$

where $0.j_\ell j_{\ell-1} \cdots j_0$ denotes a binary fraction. This expression tells you exactly how to build the circuit qubit-by-qubit.

The circuit recipe

For $n$ qubits, the QFT circuit is:

1. For each qubit $q = n-1$ down to $q = 0$: a. Apply a Hadamard to qubit $q$. b. For each qubit $p$ from $q-1$ down to $0$, apply a controlled-$R_{q-p+1}$ gate with control qubit $p$ and target qubit $q$, where $R_k$ is the phase gate $\text{diag}(1, e^{2\pi i / 2^k})$.
2. Reverse the qubit order (SWAPs), because the product form outputs qubits in reversed significance.

For $n = 3$ this is:

q[2]: —H—R2—R3———————————SWAP(q[0], q[2])
           |   |
q[1]: ——————H—R2———
               |
q[0]: ——————————H——

Total gates: $\binom{n}{2}$ controlled-phase gates + $n$ Hadamards + $\lfloor n/2 \rfloor$ SWAPs = $O(n^2)$.

Concrete for $n = 3$:

OPENQASM 2.0;
include "qelib1.inc";

qreg q[3];
creg c[3];

// Some input — say, |1⟩ in the low qubit
x q[0];

// QFT on 3 qubits (q[2] is most significant)
h q[2];
cu1(pi/2) q[1], q[2];
cu1(pi/4) q[0], q[2];
h q[1];
cu1(pi/2) q[0], q[1];
h q[0];

// Bit-reversal SWAP
cx q[0], q[2];
cx q[2], q[0];
cx q[0], q[2];

measure q -> c;

→ Try “QFT (3 qubits)” in the playground — already in the examples dropdown.

QFT in Qiskit

Qiskit ships a QFT circuit-library primitive. For learning purposes, roll your own at least once:

import numpy as np
from qiskit import QuantumCircuit

def qft_circuit(n: int, do_swaps: bool = True) -> QuantumCircuit:
    qc = QuantumCircuit(n, name="QFT")
    for q in reversed(range(n)):
        qc.h(q)
        for p in reversed(range(q)):
            angle = np.pi / (2 ** (q - p))
            qc.cp(angle, p, q)
    if do_swaps:
        for i in range(n // 2):
            qc.swap(i, n - 1 - i)
    return qc

# Compare to Qiskit's built-in
from qiskit.circuit.library import QFT
from qiskit.quantum_info import Operator

for n in [2, 3, 4, 5]:
    ours = qft_circuit(n)
    theirs = QFT(n, do_swaps=True)
    print(f"n={n}: match = {np.allclose(Operator(ours).data, Operator(theirs).data)}")
# All True

Inverse QFT

The inverse QFT is the adjoint — reverse the circuit and negate every phase. Qiskit: QFT(n, inverse=True) or qc.inverse(). The IQFT is what actually appears as the final step of QPE, Shor, and most applications — QFT is typically used “in reverse” to convert a phase-encoded state back into a computational-basis readout.

Quantum Phase Estimation

Setup. You have:

• A unitary $U$ that acts on $m$ qubits.
• An eigenvector $|\psi\rangle$ of $U$ with eigenvalue $e^{2\pi i \varphi}$, where $\varphi \in [0, 1)$.
• The ability to apply $U^{2^k}$ as a controlled operation, for $k = 0, 1, 2, ..., n-1$.

Goal. Output an $n$-bit estimate of $\varphi$.

Circuit. Two registers:

1. $n$-qubit counting register, starting in $|0^n\rangle$.
2. $m$-qubit eigenstate register, holding $|\psi\rangle$.

Steps:

1. Hadamard the counting register: each qubit in $|+\rangle$.
2. For each counting qubit $k$ (from MSB to LSB), apply controlled-$U^{2^k}$ with the counting qubit as control and the eigenstate register as target.
3. Apply inverse QFT to the counting register.
4. Measure the counting register. The classical output, read as a fixed-point fraction, is an $n$-bit estimate of $\varphi$.

Why it works (the quick derivation)

After the controlled powers of $U$, using the identity $U^{2^k}|\psi\rangle = e^{2\pi i \cdot 2^k \varphi}|\psi\rangle$ and factoring out $|\psi\rangle$:

$$\frac{1}{\sqrt{2^n}}\sum_{j=0}^{2^n - 1}e^{2\pi i j \varphi}|j\rangle \otimes |\psi\rangle.$$

The state of the counting register is exactly the QFT of $|2^n \varphi\rangle$. Applying the inverse QFT recovers $|2^n \varphi\rangle$ — or, if $\varphi$ is not exactly an integer over $2^n$, a peaked distribution around the closest such integer.

Precision and number of qubits

With $n$ counting qubits you get $n$ bits of precision in $\varphi$, i.e., resolution $2^{-n}$. Want 4-digit precision? Use at least $\lceil \log_2(10^4) \rceil = 14$ counting qubits.

QPE in Qiskit: a minimal working example

Pick $U = S$ (the phase gate) with eigenvalue $e^{i\pi/2} = e^{2\pi i \cdot 1/4}$ on eigenstate $|1\rangle$. We expect $\varphi = 0.01_2 = 0.25$.

import numpy as np
from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

def qpe_circuit(unitary: QuantumCircuit, eigenstate_prep: QuantumCircuit,
                n_counting: int) -> QuantumCircuit:
    """QPE with a general controlled-unitary. `unitary` acts on `m` qubits."""
    m = unitary.num_qubits
    qc = QuantumCircuit(n_counting + m, n_counting)

    # 1. Prepare eigenstate on register [n_counting ... n_counting+m)
    eigen_qubits = list(range(n_counting, n_counting + m))
    qc.compose(eigenstate_prep, eigen_qubits, inplace=True)

    # 2. Hadamard the counting register
    qc.h(range(n_counting))

    # 3. Controlled powers of unitary
    for k in range(n_counting):
        power = 2 ** k
        cU = unitary.power(power).control(1)
        qc.compose(cU, [k] + eigen_qubits, inplace=True)

    # 4. Inverse QFT on counting register (with swaps)
    from qiskit.circuit.library import QFT
    qc.compose(QFT(n_counting, inverse=True, do_swaps=True), range(n_counting), inplace=True)

    # 5. Measure counting register
    qc.measure(range(n_counting), range(n_counting))
    return qc

# --- U = S gate, eigenvector |1⟩, eigenvalue e^(iπ/2) → φ = 0.25 ---
U = QuantumCircuit(1, name="S")
U.s(0)

prep = QuantumCircuit(1, name="prep")
prep.x(0)                # set eigenstate register to |1⟩

n_counting = 4
qc = qpe_circuit(U, prep, n_counting)

counts = AerSimulator().run(qc, shots=4096).result().get_counts()
best = max(counts.items(), key=lambda kv: kv[1])[0]
phi_estimate = int(best, 2) / 2**n_counting
print(f"Most common measurement: {best} → φ ≈ {phi_estimate}")
# Most common measurement: 0100 → φ ≈ 0.25

The estimate is exactly 0.25 because $\varphi = 1/4$ happens to be representable in $n = 4$ counting qubits. For phases that aren’t dyadic fractions, you see a peaked distribution — the closest representable fraction wins most shots, but there’s some leakage to neighbors.

QPE when $\varphi$ isn’t dyadic

Try $U = R_z(2\pi/7)$, eigenstate $|1\rangle$, so $\varphi = 1/7 \approx 0.1428$:

from qiskit.circuit.library import RZGate

U = QuantumCircuit(1, name="Rz(2π/7)")
U.p(2 * np.pi / 7, 0)    # P gate = Rz up to global phase

prep = QuantumCircuit(1); prep.x(0)

n_counting = 6  # 2^6 = 64 bins; 1/7 ≈ 0.1428 falls between bins 9 (0.1406) and 10 (0.1562)
qc = qpe_circuit(U, prep, n_counting)

counts = AerSimulator().run(qc, shots=8192).result().get_counts()
top = sorted(counts.items(), key=lambda kv: -kv[1])[:5]
for bits, cnt in top:
    phi = int(bits, 2) / 2 ** n_counting
    print(f"  {bits} → φ ≈ {phi:.4f}  ({cnt/8192:.1%})")
# Top outcomes peak near 0.1406 and 0.1562, with ~40% mass between them combined

This peakiness is the basis of Kitaev’s phase estimation — with $n$ counting qubits, the probability of getting an estimate within $2^{-n}$ of the true $\varphi$ is at least $4/\pi^2 \approx 0.405$, and grows rapidly with more qubits.

Why QPE is everywhere

Three big application areas:

1. Shor’s algorithm. $U$ is “multiply by $a$ mod $N$” on a register of $\lceil \log N \rceil$ qubits. The eigenvalues’ phases encode the multiplicative order of $a$ mod $N$ — and that’s what classical post-processing uses to factor $N$. We build this next tutorial.

2. Quantum chemistry and materials (HHL-free VQE alternative). For a Hamiltonian $H$, the unitary $e^{-iHt}$ has eigenvalues whose phases encode energies. QPE gives you ground-state energy directly if you can prepare a good approximate eigenstate.

3. Quantum counting. Variant of QPE applied to Grover’s iteration operator $G$; the phase of $G$ encodes the number $k$ of marked items. Counts marked items without finding them.

Exercises

1. Hand-compute a 2-qubit QFT

Write out the $4 \times 4$ matrix for QFT on $n = 2$ qubits. Verify it maps $|00\rangle \to \tfrac{1}{2}(|00\rangle + |01\rangle + |10\rangle + |11\rangle)$.

Show answer

$$\text{QFT}_2 = \tfrac{1}{2}\begin{pmatrix}1 & 1 & 1 & 1\\ 1 & i & -1 & -i\\ 1 & -1 & 1 & -1\\ 1 & -i & -1 & i\end{pmatrix}.$$

The first column is $(1, 1, 1, 1)/2$, so $\text{QFT}_2|00\rangle = \tfrac{1}{2}(|00\rangle + |01\rangle + |10\rangle + |11\rangle) = |++\rangle$. Makes sense: the Fourier transform of an impulse is a uniform distribution.

2. QPE precision

Estimate $\varphi = 1/3 = 0.\overline{01}_2$ (a non-terminating binary fraction) using QPE with 5 and 10 counting qubits. Compare how sharply the distribution peaks at the correct answer.

Hint

Use $U = R_z(2\pi/3)$ and eigenstate $|1\rangle$. With 5 qubits, bin width is $2^{-5} = 0.03125$; with 10 qubits, $2^{-10} \approx 0.001$. For each, plot the top-3 measurement outcomes and compare to $1/3 \approx 0.3333$.

3. QFT circuit gate count

For $n = 10$, exactly how many Hadamards and controlled-phase gates does the canonical QFT circuit use? What’s the depth?

Show answer

$n$ Hadamards = 10. $\binom{n}{2} = 45$ controlled-phase gates. Depth (before bit-reversal SWAPs): $n + (n-1) = 19$ layers. With SWAPs: $\sim 24$. The approximate QFT (dropping phase gates with angle below some threshold) reduces the count meaningfully for large $n$.

4. Build the eigenstate

For $U = S$, the only eigenstate with eigenvalue $e^{i\pi/2}$ is $|1\rangle$. What’s the eigenstate structure of $U = X$? What eigenvalue does $|+\rangle$ give? Run QPE on $U = X$ with $|+\rangle$ as eigenstate and confirm.

Show answer

$X$ has eigenstates $|+\rangle$ with eigenvalue $+1 = e^{2\pi i \cdot 0}$ and $|-\rangle$ with eigenvalue $-1 = e^{2\pi i \cdot 0.5}$. QPE with $|+\rangle$ should return $\varphi = 0$ (bits all zero). QPE with $|-\rangle$ returns $\varphi = 0.5$ (MSB = 1, rest zero).

What you should take away

• QFT in $O(n^2)$ gates vs classical $O(n \cdot 2^n)$. You can’t read all $2^n$ amplitudes, but you can use the Fourier-transformed state as the intermediate step of a larger algorithm.
• Circuit recipe: for each qubit, Hadamard + a cascade of controlled-phase gates from the higher-significance qubits, then bit-reversal SWAPs.
• Phase estimation: given $U$ and an eigenstate, recover the eigenvalue phase as a bit string. $n$ counting qubits give $n$ bits of precision.
• QPE is the workhorse inside Shor, HHL, VQE, and quantum counting. Mastering it is the gateway to the advanced-algorithm arc.

Next: Shor’s algorithm. Factoring large integers using QPE applied to modular exponentiation. The algorithm that gave post-quantum cryptography its reason to exist.

---

Weekly dispatch

Quantum, for people who already code.

One serious tutorial per week, plus the industry moves that actually matter. No hype, no hand-waving.

Email Subscribe

Free. Unsubscribe anytime. We will never sell your email.