The New Quantum Era

Chapter 7. Shor and Everything After

This Is No Clockwork Universe

If the eternal dance of molecules Is too entangled for us mortal fools To follow, on what grounds should we complain? Who promised us that Nature’s arcane rules Would make sense to a merely human brain?

Peter Shor

Contemplating the years following Endicott, it can be difficult to understand what kept people engaged in the work in a field that had yet to prove if it would be good for anything. Deutsch’s quantum update to the Church-Turing thesis, as important an achievement as it was, did not provide any justification for the effort it would take to build a quantum computer. Classical computing is universal, meaning that it is theoretically possible to solve any problem that can be properly expressed. Quantum computers, thanks to Deutsch’s work, had theoretical proof that they were capable of exactly the same feat, no more and no less. In order to justify the investment required to build such an exotic machine, a promise of performance exceeding the capabilities of classical computers would be necessary.

It seems as though this question must have been preoccupying David Deutsch as well, because in 1992, he and his collaborator, Richard Jozsa, proposed an algorithm that provided the first provable quantum advantage over a classical computer. Provided a function hidden in a hypothetical black box, the algorithm would determine if the function’s output would be “constant” or “balanced.” A constant output function ...