of q% of the instances, then we should consider
the qth quantile in the scaling plots shown in
Fig. 2. The appropriate speedup quantity is
then the ratio of these quantiles (RofQ). Denoting a quantile q of a random variable X by
[X]q, we define this as
SRofQ q ðN Þ ¼ ½TSA ðN Þ;q ½TDW ðN Þ;q 1 N ð4Þ
Plotting this quantity for the DW2 versus SA in
Fig. 3, A and B, we found no evidence for a limited quantum speedup in the interesting regime
of large N and large q (almost all instances). That
is, although for all quantiles and for both ranges
the initial slope was positive, when N and q became large enough we observed a turnaround
and eventually a negative slope. Although we
observed a positive slope for quantiles smaller
than the median, this is of limited interest because we have not been able to identify a priori
which instances will be easy. Taking into account that because of the fixed suboptimal annealing times the speedup defined in Eq. 4 is
an upper bound, we conclude that there is no
evidence of a speedup over SA for this particular
benchmark.
SRof Q q ðNÞ measures the speedup while comparing different sets of instances for DW and SA,
each determined by the respective quantile. Now
we consider instead whether there is a speedup
for a (potentially small) subset of the same problem instances. To this end, we study the scaling
of the ratios of the time to solution for individual
instances and display in Fig. 3, C and D, the
scaling of various quantiles of the ratio (QofR)
SQofR q ðNÞ ¼ TSAðNÞ TDWðNÞ ; ;q 1 N ð5Þ
For r = 7, all the quantiles bend down for suf-
ficiently large N, so that there is no evidence of a
limited quantum speedup. There does seem to be
an indication of such a speedup compared to SA
in the low quantiles for r = 1, that is, for those
instances whose speedup ratio was high.
However, the instances contributing here are
not run at topt a , and more work is needed to es-
tablish that the potential r = 1 speedup result
persists for those instances for which one can
be sure that ta is optimal.
Next we consider the distribution of solution
times at a fixed problem size. This does not address the speedup question, because no scaling
can be extracted, but illuminates instead the
question of correlation between the performance
of the DW2 and SA. To this end, we performed
individual comparisons for each instance and
show in Fig. 4, A and B, the time to solution for
the same instances for the DW2 and SA. We observed a wide scatter [in agreement with the
DW1 results of (20)] and found that, although
the DW2 is sometimes up to 10 times faster in
pure annealing time, there are many cases where
it is ≥100 times slower.
It is not yet known whether a quantum annealer
or even a perfectly coherent adiabatic quantum
optimizer can exhibit (limited) quantum speed-
up at all, although there are promising indi-
cations from theory (27), simulation (13), and
experiments on spin glass materials (9). Experi-
mental tests are thus important. There are sev-
eral candidate explanations for the absence of
a clear quantum speedup in our tests. Perhaps
quantum annealing simply does not provide any
advantages over simulated (quantum) annealing
or other classical algorithms for the problem class
we have studied (28), or perhaps the noisy imple-
mentation in the DW2 cannot realize quantum
speedup and is thus not better than classical de-
vices. Alternatively, a speedup might be masked
by calibration errors, improvements might arise
from error correction (29), or other problem classes
might exhibit a speedup. Future studies will probe
these alternatives and aim to determine whether
one can find a class of problem instances for
which an unambiguous speedup over classical
hardware can be observed.
Although we used specific processors and
algorithms for illustration, the considerations
about a reliable determination of quantum speedup presented here are general. For any speedup analysis, use of the same scaling of hardware
resources for both quantum and classical devices
is required to disentangle parallel and quantum
speedup. And, for any quantum algorithm where
the runtime must be determined experimentally, a careful extrapolation to large problem
sizes is important to avoid mistaking inefficiencies at small problem sizes for signs of quantum
speedup.
REFERENCES AND NOTES
1. P. W. Shor, in Proceedings 35th Annual Symposium on
Foundations of Computer Science (IEEE, New York, 1994),
pp. 124–134.
2. R. Feynman, Int. J. Theor. Phys. 21, 467–488 (1982).
3. S. Lloyd, Science 273, 1073–1078 (1996).
4. I. Parberry, SIGACT News 18, 54–67 (1986).
5. L. K. Grover, Phys. Rev. Lett. 79, 325–328 (1997).
6. C. Bennett, E. Bernstein, G. Brassard, U. Vazirani, SIAM J.
Comput. 26, 1510–1523 (1997).
7. A. Papageorgiou, J. F. Traub, Phys. Rev. A 88, 022316
(2013).
8. T. Kadowaki, H. Nishimori, Phys. Rev. E 58, 5355–5363
(1998).
9. J. Brooke, D. Bitko, T. F. Rosenbaum, G. Aeppli, Science 284,
779–781 (1999).
10. E. Farhi et al., Science 292, 472–475 (2001).
11. S. Kirkpatrick, C. D. Gelatt Jr., M. P. Vecchi, Science 220,
671–680 (1983).
12. R. Martoňák, G. E. Santoro, E. Tosatti, Phys. Rev. B 66, 094203
(2002).
13. G. E. Santoro, R. Martonák, E. Tosatti, R. Car, Science 295,
2427–2430 (2002).
14. See supplementary materials on Science Online. The
supplementary materials provide details about the classical
simulation algorithms, the DW2 device, the procedure used to
determine annealing times, and additional data on scaling
with problem size.
15. F. Barahona, J. Phys. Math. Gen. 15, 3241–3253 (1982).
16. R. Harris et al., Phys. Rev. B 82, 024511 (2010).
17. M. W. Johnson et al., Supercond. Sci. Technol. 23, 065004
(2010).
18. A. J. Berkley et al., Supercond. Sci. Technol. 23, 105014
(2010).
19. M. W. Johnson et al., Nature
473, 194–198 (2011).
20. S. Boixo et al., Nat. Phys. 10, 218–224 (2014).
21. S. Boixo, T. Albash, F. M. Spedalieri, N. Chancellor, D. A. Lidar,
http://arxiv.org/abs/1212.1739 (2012).
22. W. Vinci, T. Albash, A. Mishra, P. A. Warburton, D. A. Lidar,
http://arxiv.org/abs/1403.4228 (2014).
23. J. A. Smolin, G. Smith, http://arxiv.org/abs/1305.4904
(2013).
24. L. Wang et al., http://arxiv.org/abs/1305.5837 (2013).
25. S. W. Shin, G. Smith, J. A. Smolin, U. Vazirani, http://arxiv.org/
abs/1401.7087 (2014).
26. V. Choi, Quantum Inf. Process. 10, 343–353 (2011).
27. R. D. Somma, D. Nagaj, M. Kieferová, Phys. Rev. Lett. 109,
050501 (2012).
28. H. G. Katzgraber, F. Hamze, R. S. Andrist, Phys. Rev. X 4,
021008 (2014).
29. K. L. Pudenz, T. Albash, D. A. Lidar, Nat. Commun. 5, 3243
(2014).
30. S. Isakov, I. Zintchenko, T. Rønnow, M. Troyer, http://arxiv.org/
abs/1401.1084 (2014).
ACKNOWLEDGMENTS
We thank N. Allen, M. Amin, E. Farhi, M. Mohseni, H. Neven,
and C. McGeoch for useful discussions and comments and
I. Zintchenko for providing the an_ss_ge_nf_bp simulated annealing
code before publication of the code with (30). This project was
supported by the Swiss National Science Foundation through the
SCIENCE
sciencemag.org 25 JULY 2014 • VOL 345 ISSUE 6195 423
AB
Fig. 4. Instance-by-instance comparison of annealing times. Shown are scatter plots of the pure
annealing time for the DW2 compared with SA using an average over 16 gauges [see (14)] on the DW2
for (A) r = 1 and (B) r = 7. The color scale indicates the number of instances in each square. Instances
below the diagonal red line are faster on the DW2; those above are faster using SA. Instances for which
the DW2 did not find the solution with 10,000 repetitions per gauge are shown at the top of the frame
(no such instances were found for SA).
