QUANTUM COMPUTING Defining and detecting quantum speedup

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. T he interest in quantum computing origi-nates in the potential of a quantum comput-er to solve certain computational problems much faster than is possible classically. Ex-amples are the factoring of integers (1) and the simulation of quantum systems (2, 3). In these examples, a quantum algorithm is exponentially faster than the best known classical algorithm. According to the extended Church-Turing thesis, all classical computers are equivalent up to poly-nomial factors (4). Similarly, all proposedmodels of quantum computation are polynomially equiv-alent, so that a finding of exponential quantum speedup will be model-independent. In other cases, in particular on small devices or when the quantum speedup is polynomial, defining and de-tecting quantum speedup becomes more subtle. Denoting the time used by a specific classical device or algorithm to solve a problem of size N by C(N) and the time used on the quantum de-vice by Q(N), we define quantum speedup as the asymptotic behavior of the rati