QUANTUM COMPUTING
Defining and detecting
quantum speedup
Troels F. Rønnow,1 Zhihui Wang,2,3 Joshua Job,3,4 Sergio Boixo,5,6 Sergei V. Isakov,7
David Wecker,8 John M. Martinis,9 Daniel A. Lidar,2,3,4,6,10 Matthias Troyer1*
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.
The 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 polynomial factors (4). Similarly, all proposed models
of quantum computation are polynomially equivalent, 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 detecting quantum speedup becomes more subtle.
Denoting the time used by a specific classical
device or algorithm to solve a problem of size N
SðNÞ ¼ CðNÞ
QðN Þ ð1Þ
for N → ?. Subtleties appear in the choice of
classical algorithms and in defining C(N) and
Q(N) if the runtime depends not just on the
size N of a problem but also on the specific
problem instance and in extrapolating to the
asymptotic limit.
Depending on our knowledge of classical al-
gorithms for a given problem, we may consider
four different types of quantum speedup. The
optimal scenario is one of a provable quantum
speedup, where there exists a proof that no clas-
sical algorithm can outperform a given quantum
algorithm. The best known example is Grover’s
search algorithm (5), which, in the query com-
plexity setting, exhibits a provable quadratic
speedup over the best possible classical algo-
rithm (6). A strong quantum speedup was de-
fined in (7) by using the performance of the
best classical algorithm for C(N), whether such
an algorithm is known or not. Unfortunately,
the performance of the best classical algorithm
is unknown for many interesting problems. In
the case of factoring, for example, a proof of a
classical super-polynomial lower bound is not
known. A less ambitious goal is therefore de-
sirable, and thus one usually defines quantum
speedup (without additional adjectives) by com-
paring it with the best available classical al-
gorithm instead of the best possible classical
algorithm.
A weaker scenario is one where a quantum
algorithm is designed to make use of quantum
effects, but it is not known whether these quantum effects provide an advantage over classical
algorithms or where a device is a putative or
candidate quantum information processor. To
capture this scenario, which is of central interest
1Theoretische Physik, ETH (Eidgenössische Technische
Hochschule) Zurich, 8093 Zurich, Switzerland. 2Department
of Chemistry, University of Southern California, Los Angeles,
CA 90089, USA. 3Center for Quantum Information Science
and Technology, University of Southern California, Los
Angeles, CA 90089, USA. 4Department of Physics, University
of Southern California, Los Angeles, CA 90089, USA.
5Google, 150 Main Street, Venice Beach, CA 90291, USA.
6Information Sciences Institute, University of Southern
California, Los Angeles, CA 90089, USA. 7Google,
Brandschenkestrasse 110, 8002 Zurich, Switzerland.
8Quantum Architectures and Computation Group, Microsoft
Research, Redmond, WA 98052, USA. 9Department of
Physics, University of California Santa Barbara, CA 93106–9530,
USA. 10Department of Electrical Engineering, University of
Southern California, Los Angeles, CA 90089, USA.
*Corresponding author. E-mail: troyer@phys.ethz.ch
A B
Fig. 1. Pitfalls when detecting speedup. (A) The typical (median) time to find a
ground state at least once with 99% probability for spin glasses with T1 couplings
using SQA at constant ta. The lower envelope of the curves at constant ta
corresponds to the total effort at topt a ðNÞ and can be used to infer the asymptotic
scaling. The initial, relatively flat slope at fixed N is due to suboptimal performance
at small N values and should therefore not be interpreted as speedup. Annealing
times are given in units of Monte Carlo steps (MCS), corresponding to one update
per spin. (B) The speedup of SQA over SA for two cases. If SQA is run suboptimally
at small sizes by choosing a fixed large ta = 10,000 MCS (dashed line), a speedup
is feigned. This is due to suboptimal performance on small sizes and not indicative
of the real asymptotic behavior when both codes are run optimally (solid line).
Error bars indicate statistical errors.
