๐ต Before we begin โ what is a Fourier transform?
A Fourier transform answers a question about waves: "What frequencies make up this signal?" A piece of music is a complicated pressure wave โ but a Fourier transform breaks it into pure sine waves at different frequencies. Your ear does this automatically: you hear individual instruments, not one messy wave.
The classical Fast Fourier Transform (FFT) takes a signal with N points and computes all N frequency components in O(N log N) steps. This is one of the most important algorithms ever discovered โ it powers digital audio, radio, imaging, and even quantum chemistry.
The Quantum Fourier Transform (QFT) does the same thing on quantum amplitudes โ but in O(logยฒN) steps using only n = logโN qubits. For N = 2ยฒโฐ โ 1 million, classical FFT needs ~20 million operations. QFT needs only ~200. That's an exponential speedup โ and it's the engine inside Shor's algorithm, the most important quantum algorithm of all.
๐ Why QFT doesn't replace FFT
QFT is exponentially faster but has a catch: you can't directly read the output. Measuring the output qubits collapses the transformed state to a single sample, not all N values. The power of QFT is as a subroutine โ Shor's algorithm uses QFT to find the period of a function, which it can then read with one measurement. Understanding this subtle point is what separates real quantum intuition from "quantum computers are just faster."
The engine inside Shor's algorithm. See how QFT maps computational states to frequency states using phase wheels. Understand period finding, and why a sufficiently large fault-tolerant quantum computer running Shor's algorithm could factor the numbers RSA relies on.
๐ต Classical Fourier
๐ Phase Wheels
๐ก The QFT Circuit
๐ Period Finding
๐ Shor's Connection
๐ต
Fourier transform
Decomposes a signal into frequency components. Classical FFT: O(N log N). QFT: O(logยฒN). Exponential speedup.
๐
Phase representation
QFT maps each computational basis state to evenly spaced phases on the unit circle. Phase = frequency. The unit circle IS the frequency domain.
๐
Period finding
For f(x) = aหฃ mod N, QFT finds the period r in one quantum measurement. Classical: exponential time. Quantum: polynomial time.
๐
Shor's algorithm
RSA encryption relies on factoring being hard. Shor's algorithm uses QFT to factor in polynomial time โ on a quantum computer with enough error-corrected logical qubits, which does not yet exist at the scale RSA would require.
๐ต
Wizzy ยท Quantum Guide
Start with the classical Fourier intuition. Drag the frequency sliders to mix sine waves and watch the combined signal (bottom). Fourier's insight: any wave can be built from simple sine waves. The QFT does this for quantum amplitudes โ finding the "frequencies" hidden in a quantum state.
๐ From waves to quantum amplitudes
Classical Fourier: the input is a signal (list of amplitudes over time). The output is a frequency spectrum (which sine waves make it up). QFT: the input is a quantum state (list of complex amplitudes over basis states). The output is another quantum state where the amplitudes encode the frequencies. Same maths, quantum input.
The bottom chart is what the Fourier Transform "sees" โ the hidden frequency components. Mix different frequencies and watch the spectrum update. QFT does this for quantum states.
๐ต
Wizzy ยท Quantum Guide
Each qubit in QFT has a phase wheel โ an arrow on a unit circle. The angle is the phase; the length is the amplitude. QFT maps a computational basis state |kโฉ to a state where each qubit's phase wheel points in a direction that encodes the frequency. Watch the wheels rotate as you apply QFT gates.
๐ Phase = frequency on the unit circle
The unit circle is the "frequency domain" for quantum amplitudes. A state with phase e^(2ฯiยทk/N) completes exactly k full rotations as the basis state goes from 0 to N-1. Higher frequency = faster rotation = higher k. QFT maps "which state" to "how fast the phase rotates" โ exactly like classical Fourier maps time to frequency.
Step 2 โ Phase Wheels: Quantum Frequency
3
Drag the slider to choose input state |kโฉ. The phase wheels show the QFT output amplitudes. Higher k = faster phase rotation = higher frequency component.
๐ต
Wizzy ยท Quantum Guide
The QFT circuit for 3 qubits uses only n(n+1)/2 = 6 gates: one H gate and one or two controlled phase rotation gates per qubit. Press each step to see the phase wheels evolve gate by gate. Compare to classical FFT which needs NยทlogโN = 24 operations for N=8.
๐ Why QFT is exponentially faster
Classical FFT on N = 2โฟ points: O(N log N) = O(nยท2โฟ) operations. QFT on n qubits: O(nยฒ) gate operations. For n=50 qubits (N=2โตโฐ): FFT needs ~50ยท2โตโฐ โ 5ร10ยนโถ operations. QFT needs only 50ยฒ = 2500 gates. Exponential advantage โ but only as a subroutine (you can't read the full output directly).
Step 3 โ QFT Circuit (3 qubits)
// QFT circuit (3 qubits):
// q0: H โ R2 โ R3 โ (swap)
// q1: H โ R2 โ (swap)
// q2: H
Press to step through the circuit. Watch the phase arrows rotate on the unit circle.
Classical FFT (N=8)
24
NยทlogโN operations
Quantum QFT (n=3)
6
n(n+1)/2 gates
๐ต
Wizzy ยท Quantum Guide
The magic application: finding the period of a function. Choose a value of 'a' and watch f(x) = aหฃ mod 15 computed. The function is periodic โ it repeats with some period r. QFT detects this period in one quantum measurement. Classical computers need exponential time to do the same.
๐ Why period finding breaks RSA
RSA encryption is based on multiplying two large primes p and q to get N = pยทq. Factoring N back into p and q is classically hard. Shor showed: finding the period of f(x) = aหฃ mod N gives you a shortcut to finding p and q, and QFT can find that period exponentially faster than any known classical method โ provided the quantum computer running it has enough error-corrected logical qubits.
Step 4 โ Period Finding with QFT
f(x) = 2หฃ mod 15
QFT finds period r:
?
Select a value to find the period
The highlighted cells show where the function repeats. QFT detects this repetition by finding the dominant frequency in the output state.
๐ต
Wizzy ยท Quantum Guide
๐ You've understood the algorithm behind quantum-era cryptography concerns! Shor's algorithm = period finding (powered by QFT) + classical post-processing = factoring in polynomial time. A large enough fault-tolerant quantum computer running it could threaten today's RSA encryption โ but no such machine exists yet.
Shor's Algorithm โ How QFT Factors Numbers
1Choose N to factor (e.g. N=15=3ร5). Pick random a < N coprime to N.
2Prepare superposition over all x. Compute f(x)=aหฃ mod N in superposition. The quantum state now encodes the entire function.
3Apply QFT to the input register. The periodic structure of f(x) becomes a dominant frequency in the output state.
4Measure to get a multiple of 1/r (where r is the period). Classical post-processing extracts r from this measurement.
5Compute factors using r: gcd(aสณ/ยฒ ยฑ 1, N) gives the prime factors of N with high probability.
RSA Security Timeline
Classical computer
Factoring RSA-2048: infeasible with the best known classical algorithm (commonly cited estimates run to trillions of years)
Quantum computer (Shor)
Estimated at hours, on a machine with thousands of error-corrected logical qubits โ a scale not yet built (published estimates vary by assumptions)
Post-quantum cryptography: NIST (US National Institute of Standards) has already standardised quantum-resistant algorithms (CRYSTALS-Kyber, CRYSTALS-Dilithium) designed to be secure even against Shor's algorithm. The internet is already preparing for quantum computers.
๐ง What you actually learned today
Classical Fourier Transform: decomposes any signal into frequency components. QFT does the same for quantum amplitudes โ exponentially faster.
Phase wheels: each qubit's state is an arrow on the unit circle. Phase = rotation angle = frequency component.
QFT circuit: n(n+1)/2 gates for n qubits. Classical FFT needs NยทlogโN = nยท2โฟ operations โ exponentially more.
QFT cannot be read directly โ it's used as a subroutine, not as a standalone algorithm.
Shor's algorithm uses QFT for period finding, which enables polynomial-time factoring on a large enough fault-tolerant quantum computer โ a reason the world is preparing post-quantum cryptography now, even though no such machine exists yet.
๐ต
QFT Master Badge! Session 4 Complete!
You explored the algorithm behind long-term concerns about internet encryption โ and why the world is preparing post-quantum cryptography!
Optional. Stays on this device only โ not sent to WhizzStep.
๐ต WhizzStep Quantum Lab ยท Session 4
Activity completion card for
Student Name
has explored Quantum Algorithms โ Deutsch, Grover, and QFT/Shor
This records completion of a browser activity only. It is not an accredited certificate or proof of mastery.
QFT Master
Period Finding
Session 4 โ
๐ Quantum Vocabulary
QFT KEY
Quantum Fourier Transform. Maps basis states to frequency states. O(nยฒ) gates for n qubits vs O(nยท2โฟ) classically. Cannot be read directly.
Phase wheel NEW
A qubit's state represented as an arrow on the unit circle. The angle = phase. QFT makes the phases encode frequency information.
Like a clock hand โ but the angle is quantum information, not time.
Period finding KEY
Finding the period r of f(x) = aหฃ mod N. QFT finds r in polynomial time. Classical algorithms need exponential time.
Shor's algorithm KEY
Uses QFT for period finding to factor integers in polynomial time. Threatens RSA encryption which is based on factoring being hard.
Post-quantum crypto
Encryption systems designed to resist attacks from quantum computers. NIST standardised CRYSTALS-Kyber and Dilithium in 2024.
Phase estimation
A subroutine using QFT to estimate the phase of an eigenvalue of a unitary operator. Foundation of quantum chemistry simulation and Shor's algorithm.
Key Concepts from Q12
Exponential speedup
โก nยฒ vs nยท2โฟ gates
QFT on n qubits: n(n+1)/2 gates. Classical FFT on N=2โฟ points: Nยทlog N โ nยท2โฟ operations. For n=50: 1275 gates vs 50 quadrillion operations.
Subroutine caveat
๐ Can't read directly
Measuring QFT output collapses it to one sample. The speedup only works as a subroutine โ Shor reads a single period-related value and classical post-processing does the rest.
Cryptography
๐ RSA is a long-term concern
RSA-2048 is classically infeasible to factor, but could in principle be factored in hours by a large enough fault-tolerant quantum computer, which does not exist yet. This is why post-quantum cryptography standards were published in 2024.
Session 4 Complete
๐ Algorithms mastered
You now understand Deutsch (oracle queries), Grover (โN search), and QFT/Shor (exponential factoring). Sessions 5-8 cover hardware, cryptography, chemistry, and applications.
About this lab
Q-12Algorithmic IdeasClasses 8-1215 minApplied
Learning objective: Visualise the structure of the quantum Fourier transform and its role in selected quantum algorithms.
What this simplifies: This is a local browser simulation, not access to real quantum hardware.
Privacy: No learner input leaves the device.
Teacher prompt: Ask the class why this simulation might mislead someone who takes it too literally.
Reflect: What is one thing this activity showed you that you did not expect?
