Clarifying Quantum Supremacy: better terms for milestones in quantum computation

It’s been an exciting few years for quantum computing. Several players have built and made available small quantum processors and there’s open source software to program them. Now everyone wants to know: when will quantum computers be better than regular computers? Talking about timeline is itself a fascinating conversation, but in this post I’m going to try and clarify what we mean by “better”.

This is important because “better” can mean different things to a theoretical computer scientist or an investor. Without a shared understanding of what “better” means, then talking about timeline is just confusing.

There are already a few concepts in the community such as quantum supremacy and quantum advantage. Unfortunately these terms are often used loosely in press and their definitions can be unclear. In an effort towards clarity, I suggest the following four milestones for quantum computer performance:

• Quantum Supremacy: This milestone consists of two results: (1) a mathematical proof that a given problem has a super-polynomial separation* between any possible quantum algorithm and any possible classical algorithm and (2) the exhibition of the solution of this problem by a quantum computer at a performance (size, speed, or efficiency) that is infeasible with any available classical computer. *Note that it suffices for such a proof to be relative to a widely believed assumption such as the polynomial hierarchy not collapsing.
• Weak Quantum Supremacy: The solution of any problem, using a quantum computer, faster, cheaper, or more efficiently than any available classical solution.
• Quantum Advantage: The solution of a valuable problem, using a quantum computer, faster, cheaper, or more efficiently than any available classical solution.
• Strong Quantum Advantage: Quantum Advantage accompanied with a proof — up to widely believed assumptions — that the problem has a super-polynomial separation between any quantum solution and any classical solution. Equivalently, quantum supremacy but for a commercially valuable problem.

These four milestones form the following taxonomy:

Taxonomy for milestones in quantum computing performance.

Hopefully this taxonomy will clarify which milestones matter for what. For example, quantum supremacy is talked about a lot. However, it is neither a necessary nor sufficient condition for a big commercial market for quantum computers. We can prove, for example, that an equivalent “GPU Supremacy” is impossible and yet this technology has a large market. That said, weak quantum supremacy is a first milestone towards the commercially relevant market after quantum advantage.

This is not to say that quantum supremacy and strong quantum advantage aren’t important. They are fundamental and say a lot about the nature of our universe. Personally, I agree with Scott Aaronson in saying that “a clear demonstration of quantum supremacy is at least as big a deal as (say) the discovery of the Higgs boson.”

One of the incredible things about quantum computing is that it is both a scientific endeavor and a technology. It is critical to clarify which kind of milestones we are talking about as the field develops.

It will be exciting to be part of our field’s march through them in the coming years!

Thanks to Scott Aaronson, Simon Benjamin, Josh Combes, Travis Humble, Richard Stebbing, and Guillaume Verdon for their comments on drafts of this post.