vi. Quantum Computing Basics

Conceptual, not a course: enough to understand why Shor’s and Grover’s algorithms are the two quantum results that actually matter for competitive programmers (one threatens the cryptography other notes rely on, the other gives a provable speed limit on complete search). No quantum circuit will ever run on a judge; this is background, not technique.

The model, briefly

A classical bit is 0 or 1. A qubit is a unit vector $\alpha |0⟩+\beta |1⟩$ with $|\alpha {|}^2+|\beta {|}^2=1$; measuring it collapses to $0$ with probability $|\alpha {|}^2$, $1$ with probability $|\beta {|}^2$, destroying the superposition. $n$ qubits hold a superposition over all $2^n$ basis states simultaneously — this is the source of every “quantum speedup” claim, and also the source of most quantum-computing hype: you cannot simply read out an exponential amount of information, because measurement collapses to one basis state. Every useful quantum algorithm has to engineer interference (amplitudes that cancel for wrong answers and reinforce for right ones) so that measurement is likely to land on something useful.

Quantum gates are unitary (reversible) transformations on the amplitude vector — contrast with classical logic gates like AND/OR, which are not reversible (you can’t recover the inputs from the output). This reversibility is why quantum circuits are built from gates like Hadamard (creates superposition), CNOT (entanglement) and phase rotations, rather than classical Boolean gates directly.

Grover’s algorithm: quadratic speedup for unstructured search

Problem: given a black-box function $f:\{0,\dots ,N-1\}\to \{0,1\}$ with exactly one $x^{\ast }$ satisfying $f(x^{\ast })=1$, find $x^{\ast }$. Classically this needs $\Theta (N)$ queries in the worst case — no cleverness helps without structure, which is exactly the setting of unstructured backtracking before any pruning is possible.

Grover’s algorithm finds it in $O(\sqrt{N})$ queries, by repeatedly applying an “oracle + diffusion” step that rotates the amplitude vector slightly toward $|x^{\ast }⟩$; after $\approx \frac{\pi }{4}\sqrt{N}$ iterations, measuring yields $x^{\ast }$ with probability close to 1.

Proof sketch: why $O(\sqrt{N})$ iterations suffice (geometric picture)

Represent the state as a vector in the 2D plane spanned by $|x^{\ast }⟩$ (the target) and the uniform superposition over the rest, starting at angle $\theta$ from the “non-target” axis with $\sin \theta =1/\sqrt{N}$ (the initial uniform superposition’s overlap with the target). Each Grover iteration is a fixed rotation by $2\theta$ toward the target (reflection through “non-target”, then reflection through the initial state composes to a rotation, a standard two-reflections-equal-a-rotation fact). Reaching angle $\approx \pi /2$ (measurement overwhelmingly likely to give $x^{\ast }$) takes $\approx \frac{\pi /2}{2\theta }$ iterations; since $\theta \approx \sin \theta =1/\sqrt{N}$ for small $\theta$, that’s $\approx \frac{\pi }{4}\sqrt{N}$ iterations. $■$ (Full treatment needs the explicit unitary matrices; this is the standard “two reflections” argument used in every quantum computing course, included here for the shape of the idea, not as original work.)

This quadratic speedup is provably optimal (the BBBV lower bound: no quantum algorithm solves unstructured search in fewer than $\Omega (\sqrt{N})$ queries) — unlike Shor’s algorithm below, Grover’s isn’t just “the best known,” it’s a proven floor. Practical takeaway for a competitive programmer: Grover’s algorithm is the formal reason “quantum computers will just brute-force NP-hard problems” is wrong — $\sqrt{2^n}=2^{n/2}$ is still exponential, only the exponent is halved, the same way meet-in-the-middle halves a classical exponent.

Shor’s algorithm: why it breaks RSA

Factoring $n=pq$ reduces to finding the period of $f(x)=a^x\mathrm{mod}n$ for a random $a$ (once the period $r$ is known, $\gcd (a^{r/2}\pm 1,n)$ usually reveals a factor, assuming $r$ is even and $a^{r/2}\not\equiv -1$ — both hold with probability $\ge 1/2$ for random $a$, so a few retries succeed with overwhelming probability).

Classically, finding this period needs exponential time (essentially as hard as factoring itself — no classical shortcut is known). Quantumly, period-finding is efficient: put the exponent register in superposition over all $x$, compute $a^x\mathrm{mod}n$ into a second register (entangling the two), then apply the quantum Fourier transform to the exponent register — since $f$ is periodic with period $r$, the QFT concentrates amplitude on multiples of $N/r$ (the quantum analogue of how an ordinary Fourier transform of a periodic signal concentrates on multiples of the fundamental frequency), and measuring recovers $r$ (or a value close enough to extract it via continued fractions) with high probability, in $O((\log n{)}^3)$ time.

The same period-finding machine also solves discrete log, which is why Shor’s algorithm threatens both RSA and Diffie–Hellman at once: both their hardness assumptions reduce to a period-finding problem that is classically hard but quantumly easy. This is not a proof that $\mathrm{P}=\mathrm{NP}$ or that quantum computers solve NP-hard problems in general — factoring is not known (or believed) to be NP-hard, and Shor’s algorithm is highly specific to the algebraic structure of modular exponentiation. It does not speed up NP-complete problems the way Grover’s algorithm’s quadratic speedup applies generically.

Where quantum computing is and isn’t relevant to CP

Claim	True?
Quantum computers will make $O(2^n)$ backtracking into $O(1)$	no — Grover gives $O(\sqrt{2^n})$, still exponential
Quantum computers will break RSA/Diffie–Hellman once large enough	yes, via Shor’s algorithm (requires a fault-tolerant machine far beyond current hardware)
Quantum computers prove $\mathrm{P}=\mathrm{NP}$	no — believed false; $\mathrm{BQP}$ (quantum poly-time) is not known or believed to contain all of NP
A CP judge will ever run quantum code	no, not in any foreseeable contest format
Understanding this helps explain a note elsewhere in this repo	yes — specifically why [[24-beyond-cp/05-cryptography-fundamentals

Related notes

• Cryptography Fundamentals — what Shor’s algorithm threatens, and why.
• Complexity Theory and NP-Hardness — where $\mathrm{BQP}$ sits relative to P, NP and PSPACE (believed $\mathrm{P}\subseteq \mathrm{BQP}\subseteq \mathrm{PSPACE}$, with $\mathrm{BQP}$ vs $\mathrm{NP}$ unresolved either direction).
• Backtracking and Pruning — the classical unstructured-search setting Grover’s algorithm applies to.