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

arXiv:1401.2910 · Science

Defining and detecting quantum speedup

Troels F. Rønnow, Zhihui Wang, Joshua Job, Sergio Boixo, Sergei V. Isakov, D. Wecker, John M. Martinis, Daniel A. Lidar, Matthias Troyer

Published Jun 20, 2014• 632 citations
arXivHTMLPDF

Abstract

The development of small-scale quantum devices raises the question of how to fairly assess and detect quantum speedup. Here, we show how to define and measure quantum speedup and how to avoid pitfalls that might mask or fake such a speedup. We illustrate our discussion with data from tests run on a D-Wave Two device with up to 503 qubits. By using random spin glass instances as a benchmark, we found no evidence of quantum speedup when the entire data set is considered and obtained inconclusive results when comparing subsets of instances on an instance-by-instance basis. Our results do not rule out the possibility of speedup for other classes of problems and illustrate the subtle nature of the quantum speedup question.

DOI
10.1126/science.1252319

Related papers

How to benchmark a quantum computer

Ian S. Osborne

Quantum Computing Quantum machines offer the possibility of performing certain computations much faster than their classical counterparts. However, how to define and measure quantum speedup is a topic of debate. Ronnow et al. describe methods for fairly evaluating the difference in computational power between classical and quantum processors. They define various types of quantum speedup and consider quantum processors that are designed to solve a specific class of problems. Science , this issue p. [420][1] [1]: /lookup/volpage/345/420?iss=6195

Science•Jul 24, 2014•0 citations

Defining Best Practices for Quantum Benchmarks

Mirko Amico, Helena Zhang, Petar Jurcevic +4 more

As quantum computers grow in size and scope, a question of great importance is how best to benchmark performance. Here we define a set of characteristics that any bench-mark should follow-randomized, well-defined, holistic, device independent-and make a distinction between benchmarks and diagnostics. We use Quantum Volume (QV) [1] as an example case for clear rules in benchmarking, illustrating the implications for using different success statistics, as in Ref. [2]. We discuss the is-sue of benchmark optimizations, detail when those optimizations are appropriate, and how they should be reported. Reporting the use of quantum error mitigation techniques is especially critical for interpreting benchmarking results, as their ability to yield highly accurate observables comes with exponential overhead, which is often omitted in performance evaluations. Finally, we use application-oriented and mirror benchmarking techniques to demonstrate some of the highlighted optimization principles, and introduce a scalable mirror quantum volume benchmark. We elucidate the importance of simple optimizations for improving benchmarking results, and note that such omissions can make a critical difference in comparisons. For example, when running mirror randomized benchmarking, we observe a reduction in error per qubit from 2 % to 1 % on a 26-qubit circuit with the inclusion of dynamical decoupling.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•16 citations

Defining Standard Strategies for Quantum Benchmarks

Mirko Amico, Helena Zhang, Petar Jurcevic +4 more

As quantum computers grow in size and scope, a question of great importance is how best to benchmark performance. Here we define a set of characteristics that any benchmark should follow -- randomized, well-defined, holistic, device independent -- and make a distinction between benchmarks and diagnostics. We use Quantum Volume (QV) [1] as an example case for clear rules in benchmarking, illustrating the implications for using different success statistics, as in Ref. [2]. We discuss the issue of benchmark optimizations, detail when those optimizations are appropriate, and how they should be reported. Reporting the use of quantum error mitigation techniques is especially critical for interpreting benchmarking results, as their ability to yield highly accurate observables comes with exponential overhead, which is often omitted in performance evaluations. Finally, we use application-oriented and mirror benchmarking techniques to demonstrate some of the highlighted optimization principles, and introduce a scalable mirror quantum volume benchmark. We elucidate the importance of simple optimizations for improving benchmarking results, and note that such omissions can make a critical difference in comparisons. For example, when running mirror randomized benchmarking, we observe a reduction in error per qubit from 2% to 1% on a 26-qubit circuit with the inclusion of dynamic decoupling.

arXiv:2303.02108•Mar 3, 2023•26 citations

Architectures for Quantum Simulation Showing a Quantum Speedup

Juan Bermejo-Vega, Dominik Hangleiter, Martin Schwarz +2 more

One of the main aims in the field of quantum simulation is to achieve a quantum speedup, often referred to as "quantum computational supremacy," referring to the experimental realization of a quantum device that computationally outperforms classical computers.In this work, we show that one can devise versatile and feasible schemes of two-dimensional, dynamical, quantum simulators showing such a quantum speedup, building on intermediate problems involving nonadaptive, measurement-based, quantum computation.In each of the schemes, an initial product state is prepared, potentially involving an element of randomness as in disordered models, followed by a short-time evolution under a basic translationally invariant Hamiltonian with simple nearest-neighbor interactions and a mere sampling measurement in a fixed basis.The correctness of the final-state preparation in each scheme is fully efficiently certifiable.We discuss experimental necessities and possible physical architectures, inspired by platforms of cold atoms in optical lattices and a number of others, as well as specific assumptions that enter the complexity-theoretic arguments.This work shows that benchmark settings exhibiting a quantum speedup may require little control, in contrast to universal quantum computing.Thus, our proposal puts a convincing experimental demonstration of a quantum speedup within reach in the near term.

arXiv:1703.00466•Physical Review X•Apr 9, 2018•122 citations

Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics versus quantum approaches

Salvatore Mandrà, Zheng Zhu, Wenlong Wang +2 more

To date, a conclusive detection of quantum speedup remains elusive. Recently, a team by Google Inc. [V. S. Denchev et al., Phys. Rev. X 6, 031015 (2016)] proposed a weak-strong cluster model tailored to have tall and narrow energy barriers separating local minima, with the aim to highlight the value of finite-range tunneling. More precisely, results from quantum Monte Carlo simulations as well as the D-Wave 2X quantum annealer scale considerably better than state-of-the-art simulated annealing simulations. Moreover, the D-Wave 2X quantum annealer is $\ensuremath{\sim}{10}^{8}$ times faster than simulated annealing on conventional computer hardware for problems with approximately ${10}^{3}$ variables. Here, an overview of different sequential, nontailored, as well as specialized tailored algorithms on the Google instances is given. We show that the quantum speedup is limited to sequential approaches and study the typical complexity of the benchmark problems using insights from the study of spin glasses.

arXiv:1604.01746•Physical Review A•Aug 29, 2016•112 citations

A Review and Collection of Metrics and Benchmarks for Quantum Computers: definitions, methodologies and software

Deep Lall, Abhishek Agarwal, Weixi Zhang +15 more

Quantum computers have the potential to provide an advantage over classical computers in a number of areas. Numerous metrics to benchmark the performance of quantum computers, ranging from their individual hardware components to entire applications, have been proposed over the years. Objective comparisons are further hampered in practice as different variations of the same metric are used, and the data disclosed together with a reported metric value is often not sufficient to reproduce the measurements. In this poster, we present our recent article, where we address these challenges by providing a review of metrics and benchmarks for quantum computers [1], including 1) a comprehensive collection of benchmarks allowing holistic comparisons of quantum computers, 2) a consistent format of the definitions across all metrics including a transparent description of the methodology and of the main assumptions and limitations, and 3) a reproducible approach by linking the metrics to open-source software used to evaluate them . We identify five areas where international standardization working groups could be established, namely: i) the identification and agreement on the categories of metrics that comprehensively benchmark device performance; ii) the identification and agreement on a set of well-established metrics that together comprehensively benchmark performance; iii) the identification of metrics specific to hardware platforms, including non-gate-based quantum computers; iv) inter-laboratory comparison studies to develop best practice guides for measurement methodology; and v) agreement on what data and software should be reported together with a metric value to ensure trust, transparency and reproducibility. We provide potential routes to advancing these areas. We expect that this work will accelerate the progress of quantum computing hardware towards quantum advantage. [1] D. Lall et al., A Review and Collection of Metrics and Benchmarks for Quantum Computers: Definitions, Methodologies and Software, arXiv:2502.06717.

arXiv:2502.06717•Jan 1, 2025•28 citations
The development of small-scale quantum devices raises the question of how to fairly assess and detect quantum speedup. Here, we show how to define and measure quantum speedup and how to avoid pitfalls that might mask or fake such a speedup. We illustrate our discussion with data from tests run on a D-Wave Two device with up to 503 qubits. By using random spin glass instances as a benchmark, we found no evidence of quantum speedup when the entire data set is considered and obtained inconclusive results when comparing subsets of instances on an instance-by-instance basis. Our results do not rule out the possibility of speedup for other classes of problems and illustrate the subtle nature of the quantum speedup question.
Quantum Computing Quantum machines offer the possibility of performing certain computations much faster than their classical counterparts. However, how to define and measure quantum speedup is a topic of debate. Ronnow et al. describe methods for fairly evaluating the difference in computational power between classical and quantum processors. They define various types of quantum speedup and consider quantum processors that are designed to solve a specific class of problems. Science , this issue p. [420][1] [1]: /lookup/volpage/345/420?iss=6195
As quantum computers grow in size and scope, a question of great importance is how best to benchmark performance. Here we define a set of characteristics that any bench-mark should follow-randomized, well-defined, holistic, device independent-and make a distinction between benchmarks and diagnostics. We use Quantum Volume (QV) [1] as an example case for clear rules in benchmarking, illustrating the implications for using different success statistics, as in Ref. [2]. We discuss the is-sue of benchmark optimizations, detail when those optimizations are appropriate, and how they should be reported. Reporting the use of quantum error mitigation techniques is especially critical for interpreting benchmarking results, as their ability to yield highly accurate observables comes with exponential overhead, which is often omitted in performance evaluations. Finally, we use application-oriented and mirror benchmarking techniques to demonstrate some of the highlighted optimization principles, and introduce a scalable mirror quantum volume benchmark. We elucidate the importance of simple optimizations for improving benchmarking results, and note that such omissions can make a critical difference in comparisons. For example, when running mirror randomized benchmarking, we observe a reduction in error per qubit from 2 % to 1 % on a 26-qubit circuit with the inclusion of dynamical decoupling.
As quantum computers grow in size and scope, a question of great importance is how best to benchmark performance. Here we define a set of characteristics that any benchmark should follow -- randomized, well-defined, holistic, device independent -- and make a distinction between benchmarks and diagnostics. We use Quantum Volume (QV) [1] as an example case for clear rules in benchmarking, illustrating the implications for using different success statistics, as in Ref. [2]. We discuss the issue of benchmark optimizations, detail when those optimizations are appropriate, and how they should be reported. Reporting the use of quantum error mitigation techniques is especially critical for interpreting benchmarking results, as their ability to yield highly accurate observables comes with exponential overhead, which is often omitted in performance evaluations. Finally, we use application-oriented and mirror benchmarking techniques to demonstrate some of the highlighted optimization principles, and introduce a scalable mirror quantum volume benchmark. We elucidate the importance of simple optimizations for improving benchmarking results, and note that such omissions can make a critical difference in comparisons. For example, when running mirror randomized benchmarking, we observe a reduction in error per qubit from 2% to 1% on a 26-qubit circuit with the inclusion of dynamic decoupling.
One of the main aims in the field of quantum simulation is to achieve a quantum speedup, often referred to as "quantum computational supremacy," referring to the experimental realization of a quantum device that computationally outperforms classical computers.In this work, we show that one can devise versatile and feasible schemes of two-dimensional, dynamical, quantum simulators showing such a quantum speedup, building on intermediate problems involving nonadaptive, measurement-based, quantum computation.In each of the schemes, an initial product state is prepared, potentially involving an element of randomness as in disordered models, followed by a short-time evolution under a basic translationally invariant Hamiltonian with simple nearest-neighbor interactions and a mere sampling measurement in a fixed basis.The correctness of the final-state preparation in each scheme is fully efficiently certifiable.We discuss experimental necessities and possible physical architectures, inspired by platforms of cold atoms in optical lattices and a number of others, as well as specific assumptions that enter the complexity-theoretic arguments.This work shows that benchmark settings exhibiting a quantum speedup may require little control, in contrast to universal quantum computing.Thus, our proposal puts a convincing experimental demonstration of a quantum speedup within reach in the near term.
To date, a conclusive detection of quantum speedup remains elusive. Recently, a team by Google Inc. [V. S. Denchev et al., Phys. Rev. X 6, 031015 (2016)] proposed a weak-strong cluster model tailored to have tall and narrow energy barriers separating local minima, with the aim to highlight the value of finite-range tunneling. More precisely, results from quantum Monte Carlo simulations as well as the D-Wave 2X quantum annealer scale considerably better than state-of-the-art simulated annealing simulations. Moreover, the D-Wave 2X quantum annealer is $\ensuremath{\sim}{10}^{8}$ times faster than simulated annealing on conventional computer hardware for problems with approximately 103{10}^{3}103 variables. Here, an overview of different sequential, nontailored, as well as specialized tailored algorithms on the Google instances is given. We show that the quantum speedup is limited to sequential approaches and study the typical complexity of the benchmark problems using insights from the study of spin glasses.
Quantum computers have the potential to provide an advantage over classical computers in a number of areas. Numerous metrics to benchmark the performance of quantum computers, ranging from their individual hardware components to entire applications, have been proposed over the years. Objective comparisons are further hampered in practice as different variations of the same metric are used, and the data disclosed together with a reported metric value is often not sufficient to reproduce the measurements. In this poster, we present our recent article, where we address these challenges by providing a review of metrics and benchmarks for quantum computers [1], including 1) a comprehensive collection of benchmarks allowing holistic comparisons of quantum computers, 2) a consistent format of the definitions across all metrics including a transparent description of the methodology and of the main assumptions and limitations, and 3) a reproducible approach by linking the metrics to open-source software used to evaluate them . We identify five areas where international standardization working groups could be established, namely: i) the identification and agreement on the categories of metrics that comprehensively benchmark device performance; ii) the identification and agreement on a set of well-established metrics that together comprehensively benchmark performance; iii) the identification of metrics specific to hardware platforms, including non-gate-based quantum computers; iv) inter-laboratory comparison studies to develop best practice guides for measurement methodology; and v) agreement on what data and software should be reported together with a metric value to ensure trust, transparency and reproducibility. We provide potential routes to advancing these areas. We expect that this work will accelerate the progress of quantum computing hardware towards quantum advantage. [1] D. Lall et al., A Review and Collection of Metrics and Benchmarks for Quantum Computers: Definitions, Methodologies and Software, arXiv:2502.06717.