Category: transform | Difficulty: intermediate | Qubits: 4 | Gates: 16 | Depth: 8
The Quantum Fourier Transform is the quantum analogue of the discrete Fourier transform and is a key subroutine in Shor's algorithm, QPE, and many other quantum algorithms. For n qubits it produces an exponential speedup over the classical FFT: O(n²) gates vs O(n·2ⁿ) classical operations. The circuit applies Hadamard + controlled phase rotations in a butterfly pattern, followed by a bit-reversal swap network.
Fourier-transformed basis state; depends on input state
The OpenQASM 2.0 circuit is in circuit.qasm.
OPENQASM 2.0;
include "qelib1.inc";
// 4-qubit Quantum Fourier Transform
qreg q[4];
creg c[4];
// QFT butterfly pattern
h q[0];
cu1(1.5707963267948966) q[1],q[0];
cu1(0.7853981633974483) q[2],q[0];
cu1(0.3926990816987242) q[3],q[0];
h q[1];
cu1(1.5707963267948966) q[2],q[1];
cu1(0.7853981633974483) q[3],q[1];
h q[2];
cu1(1.5707963267948966) q[3],q[2];
h q[3];
// Bit-reversal: swap to restore natural qubit order
swap q[0],q[3];
swap q[1],q[2];
measure q[0] -> c[0];
measure q[1] -> c[1];
measure q[2] -> c[2];
measure q[3] -> c[3];
qft fourier-transform subroutine shor phase-estimation
MIT — part of the OpenQC Algorithm Catalog.