Quantum Lab Session 4 Simulation Q12
๐ŸŽต 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."
๐ŸŽต Quantum Fourier Transform ยท Session 4 ยท Q12

Quantum Fourier Transform

The engine inside Shor's algorithm. See how QFT maps computational states to frequency states using phase wheels. Understand period finding โ€” and why quantum computers can break RSA encryption.

๐ŸŽต 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 uses QFT to factor in polynomial time. Threatens all RSA-encrypted communication.

๐ŸŽต
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.

Step 1 โ€” Mixing Frequencies (Classical Intuition)

Frequency 1
Amplitude: 5
Frequency 3
Amplitude: 0
Frequency 5
Amplitude: 0
Frequency spectrum (what Fourier reveals)
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 finds that period exponentially faster than any classical method. RSA security evaporates.

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 engine that will eventually break internet encryption! Shor's algorithm = period finding (powered by QFT) + classical post-processing = factoring in polynomial time. A sufficiently large quantum computer running Shor's algorithm would make RSA-2048 encryption obsolete in hours.

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: ~300 trillion years with best known algorithm
Quantum computer (Shor)
Factoring RSA-2048: ~8 hours with ~4000 error-corrected logical qubits
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 โ€” threatening RSA encryption worldwide.
๐ŸŽต

QFT Master Badge! Session 4 Complete!

You understood the algorithm that threatens internet encryption โ€” and why the world is preparing for quantum computers!

๐ŸŽต WhizzStep Quantum Lab ยท Session 4
This certifies that
Student Name
has mastered Quantum Algorithms โ€” Deutsch, Grover, and QFT/Shor
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 threatened

RSA-2048 takes 300 trillion years classically but ~8 hours with a large quantum computer. 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.