At the turn of the millennium, I read a Dr. Dobb’s article explaining why quantum computation was soooo different. It bundled reversibility, superposition, interference, entanglement, measurement, and complex amplitudes into one radical break with classical computation. Some items looked familiar from programming language semantics, but the package as a whole did not. So I began pulling it apart, one suspect at a time. Two early suspects were reversibility and the infinite precision of complex amplitudes. Reversibility fell first. It is completely classical, although working out the programming language story took years. The results included information effects, reversible languages, novel negative and fractional types, and a categorical model with a sound and complete equational theory for finite reversible programs. The continuum later proved innocent too. Finite precision is enough: a quantum computation that runs for T steps needs only O(log T) bits of precision in its transition amplitudes.

So we had to examine the remaining ingredients. Frustratingly, none was enough on its own. Entanglement cannot be the whole answer: the Gottesman-Knill theorem shows that circuits can create entangled states and still be simulated efficiently. Superposition, interference, and measurement also appear in classically tractable settings. We therefore started with our exact, discrete model of classical reversible computation, whose equations are sound and complete, and asked for the smallest quantum extension instead of assuming the entire Hilbert space model. The answer is small: add a square root of NOT, which lets us stop a reversible operation halfway; a finite clock of phases; and one equation relating them. The resulting exact language can approximate any unitary quantum computation.

This is still far from a full answer to the title question. The construction is not unique. Axioms based on cube roots, which slice operations into thirds rather than halves, produce another universal model incomparable with ours. More importantly, universal expressivity is not a classical versus quantum complexity separation. We have found one clean route from classical reversibility to quantum computation, not yet an explanation of quantum advantage.