/ quantum courseBack to lab
PATHWAY PROGRESS0/27 passed

05 / Algorithms · LESSON 13 / 27 · 20 MIN

The quantum Fourier transform.

Connect phase patterns, Fourier transforms and phase estimation.

A change of basis

For N=2ⁿ, the QFT maps basis state |x⟩ to equal magnitudes with a structured phase pattern. It is unitary. QFT|0⟩ is the uniform superposition, and inverse QFT recovers |0⟩ from that state.

Phases contain the structure

For N=4 and x=1, the amplitudes are [1,i,−1,−i]/2. Each measurement probability is 1/4, even though the phases differ. Controlled phase rotations and Hadamards implement the transform; wire reversal must be accounted for.

Phase estimation and limits

If U|ψ⟩=e²πⁱφ|ψ⟩, controlled powers of U encode φ on a counting register and inverse QFT concentrates outcomes near its binary estimate. Finite register size gives finite precision. Shor uses related period-finding ideas, not an instant attack on every cipher.

CHECK YOUR UNDERSTANDING

Lesson quiz

Answer all 2 questions correctly. Unlimited retries.

0/2 answered

1. What are QFT|0⟩ probabilities for N=4?
2. Phase estimation estimates…

Checking your account…