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

被引：105

作者：

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 [J].

ABOUCHACRA, R ;

ANDERSON, PW ;

THOULESS, DJ .

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) [J].

Achlioptas, D ;

Peres, Y .

JOURNAL OF THE AMERICAN MATHEMATICAL SOCIETY, 2004, 17 (04) :947-973

[3] Lower bounds for random 3-SAT via differential equations [J].

Achlioptas, D .

THEORETICAL COMPUTER SCIENCE, 2001, 265 (1-2) :159-185

[4] Algorithmic Barriers from Phase Transitions [J].

Achlioptas, Dimitris ;

Coja-Oghlan, Amin .

PROCEEDINGS OF THE 49TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2008, :793-+

[5] PRIMES is in P [J].

Agrawal, M ;

Kayal, N ;

Saxena, N .

ANNALS OF MATHEMATICS, 2004, 160 (02) :781-793

[6] Adiabatic quantum computation is equivalent to standard quantum computation [J].

Aharonov, Dorit ;

Van Dam, Wim ;

Kempe, Julia ;

Landau, Zeph ;

Lloyd, Seth ;

Regev, Oded .

SIAM JOURNAL ON COMPUTING, 2007, 37 (01) :166-194

[7] The Power of Quantum Systems on a Line [J].

Aharonov, Dorit ;

Gottesman, Daniel ;

Irani, Sandy ;

Kempe, Julia .

COMMUNICATIONS IN MATHEMATICAL PHYSICS, 2009, 287 (01) :41-65

[8] GEOMETRIC ASPECTS OF QUANTUM SPIN STATES [J].

AIZENMAN, M ;

NACHTERGAELE, B .

COMMUNICATIONS IN MATHEMATICAL PHYSICS, 1994, 164 (01) :17-63

[9] Circumspect descent prevails in solving random constraint satisfaction problems [J].

Alava, Mikko ;

Ardelius, John ;

Aurell, Erik ;

Kaski, Petteri ;

Krishnamurthy, Supriya ;

Orponen, Pekka ;

Seitz, Sakari .

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 [J].

Altshuler, Boris ;

Krovi, Hari ;

Roland, Jeremie .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2010, 107 (28) :12446-12450

← 1 2 3 4 5 6 7 8 9 10 →