Shor's Algorithm for Quantum Computing - Computerphile

Technological concepts & how Shor’s algorithm breaks RSA (high level)

• Threat model: Shor’s algorithm can efficiently factor large integers (in theory with sufficiently large/functional quantum hardware), which would break RSA, a widely used public-key cryptography scheme for digital signatures and certificates.

• RSA dependency on factorization: RSA’s security relies on the public value [ N = P \cdot Q ] where (P) and (Q) are secret primes. If an attacker can find (P) and (Q), they can derive the private key and forge server identities / spoof websites.

• Why factoring is hard classically: Factoring large semiprimes (e.g., ~2000-bit primes, ~4000-bit (N)) takes extremely long on classical computers—effectively infeasible for realistic key sizes.

Shor’s key reframing: factoring → period finding

Instead of directly factoring (N), Shor’s algorithm:

1. Picks a random integer (a) (typically (2 \le a \le N-1)).
2. Uses modular exponentiation to define a repeating function:
   • Compute values of (a^r \bmod N) until the pattern cycles.
3. Finds the period (r) of this repeating behavior.

Pen-and-paper style example (illustrative)

• Uses (N=15) and (a=2).
• Shows the sequence (2^k \bmod 15) repeating with period (r=4).

From period to factors

Shor then uses modular arithmetic conditions such as:

• If [ a^r \equiv 1 \pmod N ] then (typically) values like (a^{r/2} \pm 1) can share factors with (N).

Using a difference-of-squares idea:

• [ a^r - 1 = (a^{r/2}-1)(a^{r/2}+1) ]

Then compute:

• [ \gcd(a^{r/2} \pm 1, N) ] to extract (P) or (Q) (with some failure cases, e.g., if the period is odd or the gcd doesn’t yield nontrivial factors).

Efficiency insight

The speedup comes from using a quantum computer to find the period of the modular exponentiation function, rather than brute-forcing factor candidates.

Quantum mechanism: Fourier transform, interference, and extracting frequency/period

Central quantum step (conceptual)

The algorithm uses a Quantum Fourier Transform (QFT) (framed in the subtitles via “Furia/Fourier”) to detect the period by mapping it into a frequency spectrum.

Fourier intuition via wave decomposition

• Any repeating pattern can be expressed as a sum of sine/cosines (frequencies + phases).
• The phase alignment is crucial: correct constructive interference reveals the underlying periodicity as a peak in the spectrum.

Period detection as a “frequency peak”

• For the small (N=15) example, the Fourier analysis produces a spectrum where the first strong peak corresponds to the period.
• For large (N), manually “eyeballing” peaks fails classically, but the QFT concentrates probability around frequencies encoding the repeat period.

Interference analogy (constructive vs destructive)

• Demonstrates constructive vs destructive interference by shifting phase of two waves.
• Emphasizes that controlling phase is the fundamental mechanism behind the quantum speedup—no “parallel universe magic,” just interference.

Qubit implementation (trapped-ion example)

Physical realization described: trapped ions

• A charged atom in a trap (high vacuum, low temperature).
• Uses two internal energy states as qubit basis states (\lvert 0\rangle) and (\lvert 1\rangle).
• Microwave pulses (few GHz) control probability amplitudes, creating superposition.
• Laser readout counts photons to measure the state; measurement collapses the wavefunction.
• Notes quantum computation is probabilistic/statistical, requiring repeated runs and averaging.

Phase-space / vector picture (“phaser” analogy)

• Represents the quantum state as a rotating vector (“phaser”).
• Probability corresponds to the squared amplitude (arrow length squared).

How interference connects to computation

• By evolving/controlling relative phases, the algorithm makes amplitudes add or cancel.
• This is tied back to the modular exponentiation + Fourier transform pipeline: the QFT stage is where interference reveals the period.

Practicality and engineering challenges

• Current limitation: Quantum computers today are too noisy to factor RSA-sized numbers.
• Need for error correction: Requires many physical qubits per logical qubit; even factoring 15 is still nontrivial in practice.
• Time horizon uncertainty: Could be possible in years to decades, but exact feasibility is unknown.
• Key engineering requirement: Maintain coherence—prevent the environment from disturbing phases (otherwise interference patterns “wash out” and quantumness is lost).
• Security implication: Once scalable fault-tolerant quantum computers exist, RSA and similar schemes become vulnerable.

Main speakers / sources (as referenced in subtitles)

• Mike — pen-and-paper / classical explanation of period finding and the RSA-factorization link
• Phil — quantum perspective / QFT & quantum implementation discussion
• Sean — quantum mechanics/waves/Fourier intuition; leads into trapped-ion and interference-to-qubit explanation