Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM Transactions on Quantum Computing

Milestones on the Quantum Utility Highway: Quantum Annealing Case Study

Catherine C. McGeoch, Pau Farré

Published Sep 24, 2023• 6 citations
Publisher

Abstract

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.

DOI
10.1145/3625307

Related papers

Milestones on the Quantum Utility Highway

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.

arXiv:2305.00883•May 1, 2023•0 citations

Milestones on the Quantum Utility Highway

Catherine C. McGeoch, Pau Farré

We define the quantum utility performance metric and three milestones, which define quantum utility as measured in some limited context. Current and previous-generation annealing quantum systems can outperform classical solvers on a variety of input classes, on Milestones 0 and 1; our tests of Milestone 2 show positive results on a small set of inputs. Characterization of the input properties that drive these outcomes suggests that future tests will yield more widespread successes on these and more challenging milestones.

IEEE/ACM Symposium on Edge Computing (SEC)•Dec 1, 2022•8 citations

Quantum Supremacy vs. Quantum Utility - A Critical Evaluation

V N R Sai Krishna Kari, Shamim B, V T R Pavan Kumar M

Quantum computing has progressed from theoretical speculation to experimental realization, leading to milestone demonstrations that claim computational superiority over classical systems. Among these milestones, quantum supremacy experiments have attracted considerable attention by showcasing tasks that are infeasible for classical computation within reasonable time limits. However, the practical value of such demonstrations remains a subject of debate. This paper critically evaluates the distinction between quantum supremacy and quantum utility, emphasizing their conceptual differences, experimental foundations, and real-world relevance. By examining key experimental results, algorithmic developments, and benchmarking approaches, the study argues that quantum utility-defined by practical, application-oriented performance-provides a more meaningful metric for long-term progress. The paper highlights the limitations of supremacy-based demonstrations and discusses pathways toward achieving utility-driven quantum advantage in the near and long term.

Journal of Analytical and Applied Computer Sciences•Dec 31, 2025•0 citations

Benchmarking Quantum Annealers with Near-Optimal Minor-Embedded Instances

Valentin Gilbert, Julien Rodriguez, Stéphane Louise

Benchmarking Quantum Process Units (QPU) at an application level usually requires considering the whole programming stack of the quantum computer. One critical task is the minor-embedding (resp. transpilation) step, which involves space-time overheads for annealing-based (resp. gate-based) quantum computers. This paper establishes a new protocol to generate graph instances with their associated near-optimal minor-embedding mappings to D-Wave Quantum Annealers (QA). This set of favorable mappings is used to generate a wide diversity of optimization problem instances. We use this method to benchmark QA on large instances of unconstrained and constrained optimization problems and compare the performance of the QPU with efficient classical solvers. The benchmark aims to evaluate and quantify the key characteristics of instances that could benefit from the use of a quantum computer. In this context, existing QA seem best suited for unconstrained problems on instances with densities less than 10%. For constrained problems, the penalty terms used to encode the hard constraints restrict the performance of QA and suggest that these QPU will be less efficient on these problems of comparable size.

arXiv:2405.01378•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•3 citations

Quantum Annealing amid Local Ruggedness and Global Frustration

James A. King, Sheir Yarkoni, Jack Raymond +5 more

A recent Google study [Phys. Rev. X, 6:031015 (2016)] compared a D-Wave 2X quantum processing unit (QPU) to two classical Monte Carlo algorithms: simulated annealing (SA) and quantum Monte Carlo (QMC). The study showed the D-Wave 2X to be up to 100 million times faster than the classical algorithms. The Google inputs are designed to demonstrate the value of collective multiqubit tunneling, a resource available to D-Wave QPUs but not to simulated annealing. But the computational hardness in these inputs is highly localized in gadgets, with only a small amount of complexity coming from global interactions, meaning that the relevance to real-world problems is limited. In this study we provide a new synthetic problem class that addresses the limitations of the Google inputs while retaining their strengths. We use simple clusters instead of more complex gadgets and more emphasis is placed on creating computational hardness through frustrated global interactions like those seen in interesting real-world inputs. The logical problems used to generate these inputs can be solved in polynomial time [J. Phys. A, 15:10 (1982)]. However, for general heuristic algorithms that are unaware of the planted problem class, the frustration creates meaningful difficulty in a controlled environment ideal for study. We use these inputs to evaluate the new 2000-qubit D-Wave QPU. We include the HFS algorithm---the best performer in a broader analysis of Google inputs---and we include state-of-the-art GPU implementations of SA and QMC. The D-Wave QPU solidly outperforms the software solvers: when we consider pure annealing time (computation time), the D-Wave QPU reaches ground states up to 2600 times faster than the competition. In the task of zero-temperature Boltzmann sampling from challenging multimodal inputs, the D-Wave QPU holds a similar advantage as quantum sampling bias does not seem significant.

arXiv:1701.04579•Journal of the Physical Society of Japan•Feb 28, 2019•93 citations

Optimization Using Quantum Annealing: A Case Study in Logistics and Scheduling

Murali Krishna Pasupuleti

This study investigates the application of quantum annealing in solving logistics and scheduling problems, areas traditionally challenged by combinatorial complexity. Using a case study approach, quantum annealing was applied to optimize delivery routing and job-shop scheduling problems. The methodology incorporated D-Wave's quantum processing unit (QPU), and performance was benchmarked against classical simulated annealing. Results indicate a significant improvement in computational efficiency and solution optimality, particularly for mid-sized problem instances. The research identifies key parameters influencing performance and provides insights into hybrid quantum-classical integration. These findings contribute to the growing field of quantum computing applications in operations research. Keywords: Quantum annealing, logistics optimization, scheduling algorithms, quantum computing, operations research

International Journal of Academic and Industrial Research Innovations(IJAIRI)•Jun 27, 2025•0 citations
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.
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.
We define the quantum utility performance metric and three milestones, which define quantum utility as measured in some limited context. Current and previous-generation annealing quantum systems can outperform classical solvers on a variety of input classes, on Milestones 0 and 1; our tests of Milestone 2 show positive results on a small set of inputs. Characterization of the input properties that drive these outcomes suggests that future tests will yield more widespread successes on these and more challenging milestones.
Quantum computing has progressed from theoretical speculation to experimental realization, leading to milestone demonstrations that claim computational superiority over classical systems. Among these milestones, quantum supremacy experiments have attracted considerable attention by showcasing tasks that are infeasible for classical computation within reasonable time limits. However, the practical value of such demonstrations remains a subject of debate. This paper critically evaluates the distinction between quantum supremacy and quantum utility, emphasizing their conceptual differences, experimental foundations, and real-world relevance. By examining key experimental results, algorithmic developments, and benchmarking approaches, the study argues that quantum utility-defined by practical, application-oriented performance-provides a more meaningful metric for long-term progress. The paper highlights the limitations of supremacy-based demonstrations and discusses pathways toward achieving utility-driven quantum advantage in the near and long term.
Benchmarking Quantum Process Units (QPU) at an application level usually requires considering the whole programming stack of the quantum computer. One critical task is the minor-embedding (resp. transpilation) step, which involves space-time overheads for annealing-based (resp. gate-based) quantum computers. This paper establishes a new protocol to generate graph instances with their associated near-optimal minor-embedding mappings to D-Wave Quantum Annealers (QA). This set of favorable mappings is used to generate a wide diversity of optimization problem instances. We use this method to benchmark QA on large instances of unconstrained and constrained optimization problems and compare the performance of the QPU with efficient classical solvers. The benchmark aims to evaluate and quantify the key characteristics of instances that could benefit from the use of a quantum computer. In this context, existing QA seem best suited for unconstrained problems on instances with densities less than 10%. For constrained problems, the penalty terms used to encode the hard constraints restrict the performance of QA and suggest that these QPU will be less efficient on these problems of comparable size.
A recent Google study [Phys. Rev. X, 6:031015 (2016)] compared a D-Wave 2X quantum processing unit (QPU) to two classical Monte Carlo algorithms: simulated annealing (SA) and quantum Monte Carlo (QMC). The study showed the D-Wave 2X to be up to 100 million times faster than the classical algorithms. The Google inputs are designed to demonstrate the value of collective multiqubit tunneling, a resource available to D-Wave QPUs but not to simulated annealing. But the computational hardness in these inputs is highly localized in gadgets, with only a small amount of complexity coming from global interactions, meaning that the relevance to real-world problems is limited. In this study we provide a new synthetic problem class that addresses the limitations of the Google inputs while retaining their strengths. We use simple clusters instead of more complex gadgets and more emphasis is placed on creating computational hardness through frustrated global interactions like those seen in interesting real-world inputs. The logical problems used to generate these inputs can be solved in polynomial time [J. Phys. A, 15:10 (1982)]. However, for general heuristic algorithms that are unaware of the planted problem class, the frustration creates meaningful difficulty in a controlled environment ideal for study. We use these inputs to evaluate the new 2000-qubit D-Wave QPU. We include the HFS algorithm---the best performer in a broader analysis of Google inputs---and we include state-of-the-art GPU implementations of SA and QMC. The D-Wave QPU solidly outperforms the software solvers: when we consider pure annealing time (computation time), the D-Wave QPU reaches ground states up to 2600 times faster than the competition. In the task of zero-temperature Boltzmann sampling from challenging multimodal inputs, the D-Wave QPU holds a similar advantage as quantum sampling bias does not seem significant.
This study investigates the application of quantum annealing in solving logistics and scheduling problems, areas traditionally challenged by combinatorial complexity. Using a case study approach, quantum annealing was applied to optimize delivery routing and job-shop scheduling problems. The methodology incorporated D-Wave's quantum processing unit (QPU), and performance was benchmarked against classical simulated annealing. Results indicate a significant improvement in computational efficiency and solution optimality, particularly for mid-sized problem instances. The research identifies key parameters influencing performance and provides insights into hybrid quantum-classical integration. These findings contribute to the growing field of quantum computing applications in operations research. Keywords: Quantum annealing, logistics optimization, scheduling algorithms, quantum computing, operations research