Quantum supremacy denotes a demonstration in which a quantum device solves a problem that classical computers cannot solve in a reasonable time. Unlike practical quantum advantage, the demonstration need not solve a useful real-world problem; scientific merit is sufficient. section 1.3.2 section 1.2
Assess a supremacy claim by checking:
- Whether the best known classical algorithm requires an unreasonable amount of time for the same problem. section 1.3.2 section 9.8
- Whether the comparison includes practical performance, implementation overhead, execution costs, and the architecture of a future fault-tolerant computer—not asymptotic complexity alone. section 9.0 section 9.8
- Whether later improvements in classical algorithms overturn the claim; there is no permanent, clear-cut test. section 1.3.2
Early supremacy claims
Google and the University of Science and Technology of China published supremacy claims between 2019 and 2022. Other researchers later demonstrated efficient classical algorithms for the same problems, challenging those claims. These demonstrations addressed artificial problems rather than practical applications. section 1.3.2
Figure 1.2 The major milestones of quantum hardware development. The first two, showing the use of quantum mechanics to perform a computation and having a quantum computer solve an artificial problem that a classical computer cannot, have already been achieved. The next milestone, building a fault-tolerant quantum computer that can run long computations, is the current focus. The final goal is to build a quantum computer that can solve practical problems that a classical computer cannot.
Use the milestone diagram to distinguish artificial supremacy demonstrations from the later goal of practical quantum advantage. section 1.3.2
