A milestone in quantum computing

Rajendra Kumar Bera

Catherine C. McGeoch, Pau Farré

We introduce quantum utility , a new approach to evaluating quantum performance that aims to capture the user experience by considering the overhead costs associated with a quantum computation. A demonstration of quantum utility by the quantum processing unit (QPU) shows that the QPU can outperform classical solvers at some tasks of interest to practitioners, when considering the costs of computational overheads. A milestone is a test of quantum utility that is restricted to a specific subset of overhead costs and input types. We illustrate this approach with a benchmark study of a D-Wave annealing-based QPU versus seven classical solvers for a variety of problems in heuristic optimization. We consider overhead costs that arise in standalone use of the D-Wave QPU (as opposed to a hybrid computation). We define three early milestones on the path to broad-scale quantum utility. Milestone 0 is the purely quantum computation with no overhead costs and is demonstrated implicitly by positive results on other milestones. We evaluate the performance of a D-Wave Advantage QPU with respect to milestones 1 and 2: For milestone 1, the QPU outperformed all classical solvers in 99% of our tests. For milestone 2, the QPU outperformed all classical solvers in 19% of our tests, and the scenarios in which the QPU found success correspond to cases where classical solvers most frequently failed. This approach of isolating subsets of overheads for separate analysis reveals distinct mechanisms in quantum versus classical performance, which explain the observed differences in patterns of success and failure. We present evidence-based arguments that these distinctions bode well for annealing quantum processors to support demonstrations of quantum utility on ever-expanding classes of inputs and with more challenging milestones in the very near future.

Catherine C. McGeoch, Pau Farré

We introduce quantum utility, a new approach to evaluating quantum performance that aims to capture the user experience by including overhead costs associated with the quantum computation. A demonstration of quantum utility by a quantum processing unit (QPU) shows that the QPU can outperform classical solvers at some tasks of interest to practitioners, when considering computational overheads. We consider overhead costs that arise in standalone use of the QPU (as opposed to a hybrid computation context). We define three early milestones on the path to broad-scale quantum utility that focus on restricted subsets of overheads: Milestone 0 considers pure anneal time (no overheads) and has been demonstrated in previous work; Milestone 1 includes overhead times to access the QPU (that is, programming and readout); and Milestone 2 incorporates an indirect cost associated with minor embedding. We evaluate the performance of a D-Wave Advantage QPU with respect to Milestones 1 and 2, using a testbed of 13 input classes and seven classical solvers implemented on CPUs and GPUs. For Milestone 1, the QPU outperformed all classical solvers in 99% of our tests. For Milestone 2, the QPU outperformed all classical solvers in 19% of our tests, and the scenarios in which the QPU found success correspond to cases where classical solvers most frequently failed. Analysis of test results on specific inputs reveals fundamentally distinct underlying mechanisms that explain the observed differences in quantum and classical performance profiles. We present evidence-based arguments that these distinctions bode well for future annealing quantum processors to support demonstrations of quantum utility on ever-expanding classes of inputs and for more challenging milestones.

Dominik Hangleiter

Quantum computational advantage was claimed for the first time in 2019 and several experiments since then have reinforced and strengthened the claim. At the same time, a new generation of quantum computing devices with 100 logical qubits is being built. This raises two questions: Has quantum advantage actually been achieved? And what should our next milestones be for the upcoming 100-logical-qubit era? In this perspective, I argue that, in fact, quantum advantage has been achieved. The status today is analogous to Bell-inequality violations in the 1980s where some loopholes remain open, specifically, scalability and verifiability. I then outline three milestones for the 100-logical-qubit era aiming to close those loopholes: demonstrate fault-tolerant quantum advantage, perform efficiently verifiable advantage using random circuits with symmetries, and eventually demonstrate classically verifiable advantage with applications to certified randomness. These milestones are also natural stepping stones towards running algorithms with cryptographic applications.

Sergio Boixo

Outperforming classical supercomputers in a well-defined computational task is an important milestone in the long-term quest for practical quantum computing. I will argue that this milestone has been reached for the task of random quantum circuit sampling. I will review recent advances in complexity theory and classical algorithms related to this experiment. BosonSampling is another important proposal for early beyond-classical demonstrations. I will review recent BosonSampling experiments and algorithms.