The quantum adiabatic algorithm applied to random optimization problems: The quantum spin glass perspective

被引：98
作者：
Bapst, V. [1 ]
Foini, L. [2 ]
Krzakala, F. [3 ]
Semerjian, G. [1 ]
Zamponi, F. [1 ]
机构：
[1] Ecole Normale Super, UMR CNRS 8549, LPT, F-75005 Paris, France
[2] Univ Paris 06, LPTHE, F-75252 Paris 05, France
[3] ESPCI ParisTech, CNRS UMR Gulliver 7083, F-75005 Paris, France
来源：
PHYSICS REPORTS-REVIEW SECTION OF PHYSICS LETTERS | 2013年 / 523卷 / 03期
关键词：
Quantum spin glasses; Quantum annealing; Quantum adiabatic algorithm; Computational complexity; MEAN-FIELD THEORY; RANDOM K-SAT; TRANSVERSE-FIELD; PHASE-TRANSITION; SOLVABLE MODEL; STATISTICAL-MECHANICS; CRITICAL-BEHAVIOR; HUBBARD-MODEL; GIBBS-STATES; POTTS GLASS;
D O I：
10.1016/j.physrep.2012.10.002
中图分类号：
O4 [物理学];
学科分类号：
0702 ;
摘要：
Among various algorithms designed to exploit the specific properties of quantum computers with respect to classical ones, the quantum adiabatic algorithm is a versatile proposition to find the minimal value of an arbitrary cost function (ground state energy). Random optimization problems provide a natural testbed to compare its efficiency with that of classical algorithms. These problems correspond to mean field spin glasses that have been extensively studied in the classical case. This paper reviews recent analytical works that extended these studies to incorporate the effect of quantum fluctuations, and presents also some original results in this direction. (c) 2012 Elsevier B.V. All rights reserved.
引用
收藏
页码：127 / 205
页数：79
相关论文
共 288 条
  • [1] SELF-CONSISTENT THEORY OF LOCALIZATION
    ABOUCHACRA, R
    ANDERSON, PW
    THOULESS, DJ
    [J]. JOURNAL OF PHYSICS C-SOLID STATE PHYSICS, 1973, 6 (10): : 1734 - 1752
  • [2] The threshold for random k-SAT is 2k log 2-O(k)
    Achlioptas, D
    Peres, Y
    [J]. JOURNAL OF THE AMERICAN MATHEMATICAL SOCIETY, 2004, 17 (04) : 947 - 973
  • [3] Lower bounds for random 3-SAT via differential equations
    Achlioptas, D
    [J]. THEORETICAL COMPUTER SCIENCE, 2001, 265 (1-2) : 159 - 185
  • [4] Algorithmic Barriers from Phase Transitions
    Achlioptas, Dimitris
    Coja-Oghlan, Amin
    [J]. PROCEEDINGS OF THE 49TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2008, : 793 - +
  • [5] PRIMES is in P
    Agrawal, M
    Kayal, N
    Saxena, N
    [J]. ANNALS OF MATHEMATICS, 2004, 160 (02) : 781 - 793
  • [6] Adiabatic quantum computation is equivalent to standard quantum computation
    Aharonov, Dorit
    Van Dam, Wim
    Kempe, Julia
    Landau, Zeph
    Lloyd, Seth
    Regev, Oded
    [J]. SIAM JOURNAL ON COMPUTING, 2007, 37 (01) : 166 - 194
  • [7] The Power of Quantum Systems on a Line
    Aharonov, Dorit
    Gottesman, Daniel
    Irani, Sandy
    Kempe, Julia
    [J]. COMMUNICATIONS IN MATHEMATICAL PHYSICS, 2009, 287 (01) : 41 - 65
  • [8] GEOMETRIC ASPECTS OF QUANTUM SPIN STATES
    AIZENMAN, M
    NACHTERGAELE, B
    [J]. COMMUNICATIONS IN MATHEMATICAL PHYSICS, 1994, 164 (01) : 17 - 63
  • [9] Circumspect descent prevails in solving random constraint satisfaction problems
    Alava, Mikko
    Ardelius, John
    Aurell, Erik
    Kaski, Petteri
    Krishnamurthy, Supriya
    Orponen, Pekka
    Seitz, Sakari
    [J]. PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2008, 105 (40) : 15253 - 15257
  • [10] Anderson localization makes adiabatic quantum optimization fail
    Altshuler, Boris
    Krovi, Hari
    Roland, Jeremie
    [J]. PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2010, 107 (28) : 12446 - 12450
12345678910