In Search of Quantum Utility in Computation

Quantum supremacy has been claimed and attacked so many times in the last several years, it is hard to keep track of what we are supposed to think.

Here is the latest from the expert:

Speaking of making things common knowledge, several people asked me to blog about the recent IBM paper in Nature, “Evidence for the utility of quantum computing before fault tolerance.” So, uhh, consider it blogged about now! I was very happy to have the authors speak (by Zoom) in our UT Austin quantum computing group meeting. Much of the discussion focused on whether they were claiming a quantum advantage over classical, and how quantum computing could have “utility” if it doesn’t beat classical. Eventually I understood something like: no, they weren’t claiming a quantum advantage for their physics simulation, but they also hadn’t ruled out the possibility of quantum advantage (i.e., they didn’t know how to reproduce many of their data points in reasonable time on a classical computer), and they’d be happy if quantum advantage turned out to stand, but were also prepared for the possibility that it wouldn’t.

And I also understood: we’re now in an era where we’re going to see more and more of this stuff: call it the “pass the popcorn” era of potential quantum speedups for physical simulation problems. And I’m totally fine with it—as long as people communicate about it honestly, as these authors took pains to.

And then, a few days after our group meeting came three papers refuting the quantum speedup that was never claimed in the first place, by giving efficient classical simulations. And I was fine with that too.

Scott Aaronson was probably the biggest proponent of quantum supremacy. He endorsed Google's announcement in 2019. Now he seems resigned to the possibility that the present state of uncertainty could go on for years, with researchers claiming quantum supremacy, and skeptics replicating the results on classical computers.

Furthermore, he now admits the possibility that quantum computers could be built to have some utility, even if they are never shown to have any complexity advantage over classical computers.

I remain a skeptic. Just to fully explain my position, I accept quantum mechanics. I accept Feynman's argument that quantum mechanical predictions cannot be simulated efficiently on a classical computer.

This raises the possibility that a quantum system could be simulated on an analog quantum computer, and deliver an answer faster than digitally solving Schroedinger's equation. I accept that quantum computers could have some utility on such problems, and outperform digital simulations on a Turing machine.

What I do not accept is that quantum mechanics has some sort of magic for improving the asymptotic complexity performance of ordinary digital computers on certain math problems. Maybe it will be proved someday, but I doubt it. If so, it is decades away, and current public key cryptography will be safe for a long time.