Happy Quantum Day, Quantum Computing Pioneer!
In 1990, Itamar Pitowsky (1950-2010) explicitly expressed for the first time the insight implicit in (Simon's and) Shor's algorithm.
In sec. 7 of that paper, published in a journal you probably never heard of, he demonstrated that naive quantum parallelism is useless; no better than a classical computer that guesses the result. The trick, he argued in a subsequent paper, is to efficiently devise "clever" quantum superpositions that would capitalize on the non-Boolean character of quantum probabilities, the engine behind today's "quantum advantage", so that the retrieval of the answer, probabilistic as it must be, can be done with probabilities that outperform a classical computer. That trick, however, is problem-specific; not any problem would do. Four years later (Simon and) Shor found such a problem: Factoring.
And the rest is history.
Together with other, more famous computer scientists, Itamar’s work on the foundations of quantum probabilities paved the way to quantum information theory and quantum computing. How good this work is? His book from 1989 was, for a while, beyond reach, because everyone who could steel it from their libraries did so (I didn’t, I actually bought it, I guess from someone who stole it).
Itamar, the Oracle from Givat Ram. The calm sunshine of his mind is something we all need more of these days.