A Short History of Rocks: or, How to Invent Quantum Computing

This essay gives a short, informal account of the development of digital logic from the Pleistocene to the Manhattan Project, the introduction of reversible circuits, and Richard Feynman's allied proposal for quantum computing. We argue that Feynman's state-based analogy is not the only way to arrive at quantum computing, nor indeed the simplest. To illustrate, we imagine an alternate timeline in which John von Neumann skipped Operation Crossroads to debug a military computer, got tickled by the problem, and discovered a completely different picture of quantum computing -- in 1946. Feynman suggested we "quantize" state, and turn classically reversible circuits into quantum reversible, unitary ones. In contrast, we speculate that von Neumann, with his background in functional analysis and quantum logic, would seek to "quantize" the operators of Boolean algebra, and with tools made available in 1946 could successfully do so. This leads to a simpler, more flexible circuit calculus and beautiful parallels to classical logic, as we detail in a forthcoming companion paper.