PT  - JOURNAL ARTICLE
AU  - Rønnow, Troels F.
AU  - Wang, Zhihui
AU  - Job, Joshua
AU  - Boixo, Sergio
AU  - Isakov, Sergei V.
AU  - Wecker, David
AU  - Martinis, John M.
AU  - Lidar, Daniel A.
AU  - Troyer, Matthias
TI  - Defining and detecting quantum speedup
AID  - 10.1126/science.1252319
DP  - 2014 Jul 25
TA  - Science
PG  - 420--424
VI  - 345
IP  - 6195
4099  - http://science.sciencemag.org/content/345/6195/420.short
4100  - http://science.sciencemag.org/content/345/6195/420.full
SO  - Science2014 Jul 25; 345
AB  - 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. 420The 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.