Defining and detecting quantum speedup
Venue
Science, vol. 345 (2014), pp. 420-424
Publication Year
2014
Authors
Troels F. Rønnow, Zhihui Wang, Joshua Job, Sergio Boixo, Sergei V. Isakov, David Wecker, John M. Martinis, Daniel A. Lidar, Matthias Troyer
BibTeX
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. 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
