05 / Algorithms · LESSON 13 / 27 · 20 MIN
The quantum Fourier transform.
Connect phase patterns, Fourier transforms and phase estimation.
QFT|x⟩ = Σₖ exp(2πixk/N)|k⟩ / √N
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
Checking your account…
