The Man Who Saw Quantum Advantage First
The Longest Calculation: Quantum Computing, an Inside Story. Forthcoming Book. Episode IV
In a short story by Jorge Luis Borges, the universe is a library containing every possible book. Every arrangement of letters that could exist does exist, somewhere on its shelves. The library therefore contains the answer to every question ever asked. It is, for exactly that reason, useless. A library that contains everything offers no way to find anything. The difficulty is retrieval.
In 1990, a philosopher in Jerusalem named Itamar Pitowsky published a paper in Iyyun, a philosophical quarterly that no computer scientist has ever opened, asking what the physical universe permits a computer to do. The paper contained an observation so precise that the quantum computing community would spend the next decade rediscovering it without knowing he had been there first.
The observation was this. A quantum system can encode an enormous number of possible answers simultaneously. A hundred quantum bits can represent more states than there are atoms in the visible universe, all at once, all superimposed. Popular accounts of quantum computing stop here and declare victory: the machine tries every answer at the same time.
Pitowsky understood why this is wrong. When you measure a quantum system, the superposition collapses. You get one answer, drawn at random from a probability distribution. If the superposition is uniform, if every encoded answer is equally weighted, then the probability of getting the right one is identical to the probability of guessing it at random. A classical coin-flipper does just as well. The quantum parallelism, celebrated in a thousand press releases, has gained you exactly nothing.
This is devastating, and Pitowsky stated it with characteristic calm. Encoding is free. Nature hands it to you. The entire problem is retrieval, and retrieval means constructing a superposition whose probability distribution is skewed, concentrated on the correct answer with probability substantially above the classical baseline. The quantum advantage, if it exists, lives in the space between classical probability and quantum probability, in the fact that quantum probability obeys different rules, rules that permit distributions a classical system cannot reach.
Four years later, Peter Shor built an algorithm that factors large numbers exponentially faster than any known classical method. The algorithm works because Shor found a way to exploit the periodicity of modular arithmetic to construct precisely the kind of skewed superposition Pitowsky had described. The quantum Fourier transform builds a probability distribution that concentrates measurement outcomes on the answer. The insight Pitowsky had mapped in the abstract, Shor realized in the specific.
The community that formed around Shor’s algorithm traced its ancestry to Feynman and Deutsch. Pitowsky’s paper, which had identified the structure of the problem they were solving, was invisible. It had appeared in the wrong journal, from the wrong discipline, by a man the field classified as a philosopher rather than an engineer.
His office at the Hebrew University was on the second floor of the Rationality Center in Givat Ram, small and inviting, the door always open. He taught his classes with a deep voice that made mathematical logic sound like a conversation between friends. He died in 2010, at sixty, before the field had understood what he had given it. The calm sunshine of his mind is among the things I carry with me still.
