“Quantum Supremacy” is a term that was coined in 2012 by John Preskill, Richard P. Feynman Professor of Theoretical Physics at the California Institute of Technology (Caltech). It refers to the demonstration of quantum computation that solves a problem that cannot be solved classically in any realistic timeframe. The only requirement to satisfy this term is the demonstration of a superpolynomial speedup over all possible classical approaches to solving the problem.
Because there is no qualitative requirement, the term can apply to demonstrations with problems that have no real-world applicability, as well as with results that have not had either quantum error correction (QEC) or quantum error mitigation (EM) applied. Its use requires neither commercial viability nor fault-tolerant quantum computing (FTQC), therefore these demonstrations are primarily academic endeavors for the Noisy Intermediate-Scale Quantum (NISQ) era.
These experiments are important, however, because they demonstrate the potential of quantum computers to solve classically intractable problems. The end goal, of course, is to eventually solve useful such problems with tolerable error rates, but skepticism would understandably be high if this couldn’t be experimentally demonstrated at all. In other words, solving classically intractable non-useful problems builds confidence that classically intractable useful problems can be found that can be solved as well.
A BBVA article titled “What is quantum supremacy?” tells the story of the famous experiment by Google, NASA, and Oak Ridge National Laboratory. It also discusses misunderstandings of the term, as well as the need for patience in realizing large-scale, error-corrected, useful applications.
The term “quantum supremacy” needs to be distinguished from two other terms: “quantum advantage” and “quantum utility.” For quantum computing supremacy means that classical solutions are infeasible, advantage means that the quantum solution is either faster or more accurate than classical solutions, and utility means that there is no particular advantage to using the quantum solution, but it works. Essentially, the industry came to realize that quantum computers can be useful without meeting the threshold of classical intractability, and additional terms were consequently coined.
If we are to ask how many qubits for quantum supremacy to be achieved, the question does not have one answer. A standard baseline is at least 50 qubits, which is beyond the capabilities of the most powerful quantum computer simulators. However, some problems can be solved more efficiently than others and will require more qubits to meet the threshold. An IEEE Spectrum article titled “How Many Qubits Are Needed for Quantum Supremacy? Whether Google achieved quantum supremacy depends on perspective” offers up some estimates of the various qubit counts that might be required to achieve “supremacy” for several different problems.
Quantum supremacy means that the limits of classical computation have been surpassed. There is insufficient processing power or memory, even within high-performance computing (HPC) environments, to solve the problem within a reasonable timeframe.
Quantum supremacy does not require these problems to be useful in any way, but what if useful quantum supremacy could be achieved? Some of the implications of this might include:
The exciting distinction of useful quantum supremacy is that we don’t currently know any other ways to solve these problems efficiently. Approximation pushes classical computation a little further, but may not always be useful. Useful quantum supremacy would mean that the impossible with classical computing literally becomes possible with quantum computing.
For more information on the differences between quantum computing and classical computing, in general, a CBInsights article titled “Quantum Computing Vs. Classical Computing In One Graphic” offers a helpful, high-level infographic.
.svg){kind=small}
