Maps the computational basis to the Fourier (frequency) basis. Subroutine of QPE and Shor.
On n qubits, QFT|x⟩ = 2⁻ⁿ/² Σ_k exp(2πi x k / 2ⁿ) |k⟩. The circuit is H on each wire from MSB to LSB, with controlled phases CP(π/2^{k−1}) from lower wires, then SWAP to reverse wire order.
Qubi CP angles are π-multiples: CP [j,i] 0.5 is a π/2 controlled phase. Applied to |000⟩ the QFT is a uniform superposition.
How it works
-
1
MSB Hadamard and phases
H 2, then CP from q1 (angle 1/2) and q0 (angle 1/4) onto q2.
-
2
Middle wire
H 1, then CP [0,1] 0.5.
-
3
LSB and reverse
H 0, then SWAP [0,2] so the Fourier bit order matches the usual convention.
H 2 CP [1,2] 0.5 CP [0,2] 0.25 H 1 CP [0,1] 0.5 H 0 SWAP [0,2]
Function form: QFT(0..2)
State. QFT|000⟩ = |+⟩⊗³ = 2⁻³/² Σ_x |x⟩
Each of the 8 computational basis states has probability 1/8.
| Basis | Amplitude | Probability |
|---|---|---|
|000⟩ ... |111⟩ |
1/√8 each |
Notes
- Classical FFT is O(n 2ⁿ) on the same 2ⁿ amplitudes. QFT is O(n²) gates.
- IQFT is the exact adjoint (see Inverse QFT).
Change parameters
The write-up above is for the default circuit. Use this control to generate other variants and load them in the simulator.