On “Quantum Supremacy”

Edwin Pednault, John Gunnels, and Jay Gambetta:

Quantum computers are starting to approach the limit of classical simulation and it is important that we continue to benchmark progress and to ask how difficult they are to simulate. This is a fascinating scientific question.

Recent advances in quantum computing have resulted in two 53-qubit processors: one from our group in IBM and a device described in the leaked preprint from Google. In the preprint, it is argued that their device reached “quantum supremacy” and that “a state-of-the-art supercomputer would require approximately 10,000 years to perform the equivalent task.” We argue that an ideal simulation of the same task can be performed on a classical system in 2.5 days and with far greater fidelity. This is in fact a conservative, worst-case estimate, and we expect that with additional refinements the classical cost of the simulation can be further reduced.

Because the original meaning of the term “quantum supremacy,” as proposed by John Preskill in 2012, was to describe the point where quantum computers can do things that classical computers can’t, this threshold has not been met.
This particular notion of “quantum supremacy” is based on executing a random quantum circuit of a size infeasible for simulation with any available classical computer.

Specifically, the preprint shows a computational experiment over a 53-qubit quantum processor that implements an impressively large two-qubit gate quantum circuit of depth 20, with 430 two-qubit and 1,113 single-qubit gates, and with predicted total fidelity of 0.2%. Their classical simulation estimate of 10,000 years is based on the observation that the RAM memory requirement to store the full state vector in a Schrödinger-type simulation would be prohibitive, and thus one needs to resort to a Schrödinger-Feynman simulation that trades off space for time.

The concept of “quantum supremacy” showcases the resources unique to quantum computers, such as direct access to entanglement and superposition. However, classical computers have resources of their own such as a hierarchy of memories and high-precision computations in hardware, various software assets, and a vast knowledge base of algorithms, and it is important to leverage all such capabilities when comparing quantum to classical.