Defining and detecting quantum speedup

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

626 citations recorded by the source corpus.

How to benchmark a quantum computer 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. Rønnow 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 What makes a quantum machine quantum? 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.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/d4836804ee59c483943cc8f5e1eb88b58e4f52fc

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

In Electrical and Electronic Engineering

Citations in the corpus

Quantum information processing with superconducting circuits: a review (2016, background): “In general, however, speedup of a computation is an asymptotic scaling property [109].”
Quantum algorithms: an overview (2015, neutral): “The key phrase here is \slowly enough"; for some instances of CSPs on n bits, the time required for this evolution might be exponential in n .”
Quantum machine learning (2016, neutral): “This is known as a quantum speedup [106].”
What is the Computational Value of Finite Range Tunneling (2015, background): “We note that for instances with more qubits, more quantum hardware resources are brought to bear and therefore a fair comparison needs to take this into account [12,15].”
Probing many-body dynamics on a 51-atom quantum simulator (2017, background): “perconducting [13] and optical [14] systems, but these realizations lack either coherence or quantum nonlinearity, which are essential for achieving full quantum speedup.”
A practical heuristic for finding graph minors (2014, methodology): “Experiments show the D-Wave machine at its current scale is competitive with the best classical algorithms for solving Ising models [17, 19, 16, 20].”
Quantum annealing for industry applications: introduction and review (2021, neutral): “While the question of whether QA can provide a quantum speed-up over classical approaches is still subject of a scientific debate (see, for example, [71, 109, 145] and references therein), there is ongoing dedicated effort to use QA hardware to solve application-motivated problems.”
Quantum Supremacy through the Quantum Approximate Optimization Algorithm (2016, methodology): “In fact this procedure can be viewed as a classical algorithm for finding the minimum of −C and is sometimes referred to as SQA for Simulated Quantum Annealing [8, 15,21,31].”
A fully programmable 100-spin coherent Ising machine with all-to-all connections (2016, background): “Benchmarking relatively small Ising problem instances is fraught with difficulty (12), and it is not even particularly obvious what benchmarks are appropriate in any given situation.”
Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer (2018, background): “Efforts to benchmark quantum annealers against classical counterparts such as simulated annealing (SA) [15] have abounded [14, 16–30].”
Quantum Computing in the NISQ era and beyond (2018, background): “But as of now we don’t have a convincing theoretical argument or persuasive experimental evidence indicating that quantum annealers can really speed up the time to solution compared to the best classical hardware running the best algorithms for the same problems [28, 29].”
Adiabatic Quantum Computing (2016, methodology): “Moreover, its role in (Boixo et al., 2016; Denchev et al., 2016) is limited to a prefactor, and does not translate into a scaling advantage, i.e., it does not qualify as a speedup according to the classification of (Rønnow et al., 2014).”
Experimental investigation of performance differences between coherent Ising machines and a quantum annealer (2018, background): “This makes clear that, as in quantum annealing, there is a tradeoff between success probability and annealing time [18].”