Quantum algorithms

Quantum Fourier transform

Encode a basis label into a pattern of phases and follow its circuit decomposition.

25 minIntermediate

Intuition

A Fourier transform changes the basis of a vector. The QFT uses normalized columns, which makes the transform unitary. Each computational basis input produces equal output magnitudes and a pattern of phases.

The output of a QFT on a basis state is therefore uniform under computational measurement. In an algorithm, the input structure and later measurements determine which phase information becomes observable.

Learning objectives

  • Read the positive-sign DFT convention
  • Connect controlled phases to binary digits
  • Explain output wire reversal

Interactive exploration

Use the controls to change the state and see its calculated readout. You can return to this experiment as you work through the derivation.

Sequence

Step 1 / 4

Basis input

A single computational basis amplitude is one.

BasisAmplitudeProbability
|00⟩0.0000%
|01⟩1.000100%
|10⟩0.0000%
|11⟩0.0000%

Mathematical foundation

For N = 2ⁿ, the QFT column indexed by x has phase 2πxy/N at row y. Different columns have inner product zero by the sum of a nontrivial geometric series.

FN∣x⟩=1N∑y=0N−1e2πixy/N∣y⟩F_N|x\rangle=\frac1{\sqrt N}\sum_{y=0}^{N-1}e^{2\pi ixy/N}|y\rangle

With y expressed in bits, the exponential factors by output wire. A Hadamard starts each phase pattern and controlled phase gates add contributions from lower-order input bits. The standard circuit reverses the output order with SWAP gates.

e2πixy/N=∏j=0n−1e2πixyj2j/Ne^{2\pi ixy/N}=\prod_{j=0}^{n-1} e^{2\pi i x y_j 2^j/N}

Worked example

For N = 4 and x = 1, successive output amplitudes have phase increments π/2, so the vector is (1, i, −1, −i)/2. Each outcome has probability one quarter.

F4∣01⟩=12(∣00⟩+i∣01⟩−∣10⟩−i∣11⟩)F_4|01\rangle=\tfrac12(|00\rangle+i|01\rangle-|10\rangle-i|11\rangle)

Guided experiment

Select two qubits and input |01⟩. Step past the wire reversal and compare every complex amplitude with the derived column.

Go to the controls
Compare with the expected result

The displayed probabilities hide the phase progression, which remains visible in the complex amplitudes.

Understanding check

1. For N = 4 and input x = 2, what is the amplitude at output y = 1?
2. What is the computational probability of any output of F₄|01⟩?

Next steps

Want to keep your results? Start your learning journey

Open Algorithm Visualizer