Defining and detecting quantum speedup

被引：393

作者：

Ronnow, Troels F. ^{[1
]}

Wang, Zhihui ^{[2
,3
]}

Job, Joshua ^{[3
,4
]}

Boixo, Sergio ^{[5
,6
]}

Isakov, Sergei V. ^{[7
]}

Wecker, David ^{[8
]}

Martinis, John M. ^{[9
]}

Lidar, Daniel A. ^{[2
,3
,4
,6
,10
]}

Troyer, Matthias ^{[1
]}

机构：

[1] ETH, CH-8093 Zurich, Switzerland

[2] Univ So Calif, Dept Chem, Los Angeles, CA 90089 USA

[3] Univ So Calif, Ctr Quantum Informat Sci & Technol, Los Angeles, CA 90089 USA

[4] Univ So Calif, Dept Phys, Los Angeles, CA 90089 USA

[5] Google, Venice Beach, CA 90291 USA

[6] Univ So Calif, Inst Informat Sci, Los Angeles, CA 90089 USA

[7] Google, CH-8002 Zurich, Switzerland

[8] Microsoft Res, Quantum Architectures & Computat Grp, Redmond, WA 98052 USA

[9] Univ Calif Santa Barbara, Dept Phys, Santa Barbara, CA 93106 USA

[10] Univ So Calif, Dept Elect Engn, Los Angeles, CA 90089 USA

来源：

SCIENCE | 2014年 / 345卷 / 6195期

基金：

瑞士国家科学基金会;

关键词：

D O I：

10.1126/science.1252319

中图分类号：

O [数理科学和化学]; P [天文学、地球科学]; Q [生物科学]; N [自然科学总论];

学科分类号：

07 ; 0710 ; 09 ;

摘要：

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.

引用

页码：420 / 424

页数：5

共 23 条

[1] ON THE COMPUTATIONAL-COMPLEXITY OF ISING SPIN-GLASS MODELS
BARAHONA, F
[J]. JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1982, 15 (10): : 3241 - 3253
[2] Strengths and weaknesses of quantum computing
Bennett, CH
Bernstein, E
Brassard, G
Vazirani, U
[J]. SIAM JOURNAL ON COMPUTING, 1997, 26 (05) : 1510 - 1523
[3] A scalable readout system for a superconducting adiabatic quantum optimization system
Berkley, A. J.
Johnson, M. W.
Bunyk, P.
Harris, R.
Johansson, J.
Lanting, T.
Ladizinsky, E.
Tolkacheva, E.
Amin, M. H. S.
Rose, G.
[J]. SUPERCONDUCTOR SCIENCE & TECHNOLOGY, 2010, 23 (10)
[4] Boixo S, 2014, NAT PHYS, V10, P218, DOI [10.1038/nphys2900, 10.1038/NPHYS2900]
[5] Quantum annealing of a disordered magnet
Brooke, J
Bitko, D
Rosenbaum, TF
Aeppli, G
[J]. SCIENCE, 1999, 284 (5415) : 779 - 781
[6] Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
Choi, Vicky
[J]. QUANTUM INFORMATION PROCESSING, 2011, 10 (03) : 343 - 353
[7] A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem
Farhi, E
Goldstone, J
Gutmann, S
Lapan, J
Lundgren, A
Preda, D
[J]. SCIENCE, 2001, 292 (5516) : 472 - 476
[8] SIMULATING PHYSICS WITH COMPUTERS
FEYNMAN, RP
[J]. INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS, 1982, 21 (6-7) : 467 - 488
[9] Quantum mechanics helps in searching for a needle in a haystack
Grover, LK
[J]. PHYSICAL REVIEW LETTERS, 1997, 79 (02) : 325 - 328
[10] Experimental investigation of an eight-qubit unit cell in a superconducting optimization processor
Harris, R.
Johnson, M. W.
Lanting, T.
Berkley, A. J.
Johansson, J.
Bunyk, P.
Tolkacheva, E.
Ladizinsky, E.
Ladizinsky, N.
Oh, T.
Cioata, F.
Perminov, I.
Spear, P.
Enderud, C.
Rich, C.
Uchaikin, S.
Thom, M. C.
Chapple, E. M.
Wang, J.
Wilson, B.
Amin, M. H. S.
Dickson, N.
Karimi, K.
Macready, B.
Truncik, C. J. S.
Rose, G.
[J]. PHYSICAL REVIEW B, 2010, 82 (02)

← 1 2 3 →