Introduction

What makes a quantum computer different?

Not that it “tries every answer at once”. A quantum computer manipulates vectors of complex amplitudes and makes them interfere, so that the paths to the wrong answers cancel out. This site builds that idea from scratch, theorem by theorem: from the classical bit to Shor's algorithm and error correction.

Start at the beginning →See the timeline

From 0 and 1 to superposition

A classical bit is a point at one of the two ends of a segment. A qubit is a point anywhere on a sphere. Between the two lies a single mathematical change: probabilities, which add up to 1 in the 1-norm, are replaced by amplitudes, whose squares add up to 1 in the 2-norm. Everything else (interference, entanglement, quantum algorithms and the difficulty of building the machines) follows from that change and from linear algebra. Here is the chain:

1. 00 Bit 1937 – 1980 From bits to vectors Before the qubit there was the bit. Rewriting classical computation as linear algebra (bits as vectors, logic gates as matrices, randomness as probability vectors) reveals exactly what quantum mechanics changes: one norm for another.
   • Universality of NAND
   • Landauer's principle
   • Reversible universality (Toffoli)
   • Isometries of ${\ell }_p$
2. 01 Qubit 1900 – 1973 A unit vector in a complex space A qubit is not “0 and 1 at the same time”. It is a unit vector in ${ℂ}^2$, whose components are complex amplitudes; their squared moduli give the probabilities of each outcome. Geometrically, every qubit is a point on a sphere.
   • Born rule
   • Invisibility of global phase
   • Bloch sphere
   • Holevo bound
3. 02 Superposition 1801 – 2001 Amplitudes that cancel out Probabilities only add up; amplitudes can cancel. That single difference, interference, is the source of all quantum advantage. A coin tossed twice is still random; a “quantum coin” tossed twice gives a certain answer.
   • Linearity and unitarity
   • Interference term
   • Hadamard squared is the identity
   • Mach–Zehnder interferometer
4. 03 Measurement 1922 – 1982 Asking a question changes the answer Measuring is the only moment when a quantum computer hands over classical information, and the only non-reversible step. Observables are Hermitian matrices, outcomes are their eigenvalues, and two incompatible questions cannot both have sharp answers.
   • Spectral theorem
   • Robertson's uncertainty relation
   • Density matrices
   • No-cloning theorem
5. 04 Entanglement 1935 – 2022 Correlations no hidden variable can explain Two qubits do not live in a plane but in a four-dimensional space built with the tensor product, and most of its states cannot be described qubit by qubit. Einstein called it “spooky action at a distance”; Bell turned it into an inequality that experiments violate.
   • Product criterion
   • Schmidt decomposition
   • CHSH inequality
   • Tsirelson bound
   • No-signalling
6. 05 Circuits 1985 – 1998 Programming with unitary matrices A quantum gate is a unitary matrix and a circuit is a product of them. A few gates are enough to approximate any computation, and some very powerful-looking circuits can be simulated classically. The boundary between the two is the theory of quantum complexity.
   • Characterization of unitaries
   • Euler decomposition (ZYZ)
   • Universality of CNOT + 1 qubit
   • Solovay–Kitaev
   • Gottesman–Knill
7. 06 Fourier 1807 – 1998 Finding hidden periods Fourier taught us to break any signal into frequencies. Its quantum version acts on $2^n$ amplitudes with only about $n^2$ gates, exponentially fewer than the fast classical algorithm. Coupled with interference, it turns hidden periodicity into peaks that can be measured.
   • Unitarity of the QFT
   • Product representation
   • Fourier transform of periodic states
   • Phase estimation
8. 07 Shor 300 BC – 2025 Factoring by finding a period The security of most of the internet rests on one assumption: that factoring large numbers is hard. In 1994 Peter Shor showed that a quantum computer could do it in polynomial time, by turning factoring into finding the period of a function and the period into a Fourier peak.
   • Euler's theorem
   • Reduction from factoring to order finding
   • Quantum order finding
   • Legendre's theorem (continued fractions)
9. 08 Grover 1996 – 2002 Searching with rotations To find a marked item among $N$ with no structure to help, any classical algorithm needs about $N$ attempts. Lov Grover found a quantum algorithm that needs only about $\sqrt{N}$, by rotating a vector a little at a time in a two-dimensional plane. And it is provably impossible to do better.
   • Two reflections make a rotation
   • Optimal number of iterations
   • Lower bound $\mathrm{\Omega }(\sqrt{N})$ (BBBV)
   • Amplitude amplification
10. 09 Correction 1995 – 2024 Protecting what cannot be copied Qubits are fragile: any interaction with the environment degrades their superpositions. For years it seemed impossible to protect them, because they cannot be copied or looked at. Quantum error-correcting codes and the threshold theorem showed how, and in 2024 an experiment crossed the threshold for the first time.
    • Kraus representation
    • Discretization of errors
    • Knill–Laflamme conditions
    • Threshold theorem

Concepts and their mathematics

Quantum computing mixes mathematics, physics and computer science. This table summarizes what each concept owes to which branch of mathematics:

How to read this site

The emphasis is on the mathematical theory: each chapter states its results as theorems, and most come with a proof, folded so as not to interrupt the reading. Linear algebra (vectors, matrices, eigenvalues) is the only real prerequisite; the companion site Math of AI has a chapter on it. The figures are interactive and simulate the quantum states exactly in your browser, with no servers and no trackers.

Chapter 00: From bits to vectors →