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 条

[61] ELEMENTARY GATES FOR QUANTUM COMPUTATION [J].

BARENCO, A ;

BENNETT, CH ;

CLEVE, R ;

DIVINCENZO, DP ;

MARGOLUS, N ;

SHOR, P ;

SLEATOR, T ;

SMOLIN, JA ;

WEINFURTER, H .

PHYSICAL REVIEW A, 1995, 52 (05) :3457-3467

[62] World line simulations of the bosonic Hubbard model in the ground state [J].

Batrouni, GG ;

Scalettar, RT .

COMPUTER PHYSICS COMMUNICATIONS, 1996, 97 (1-2) :63-81

[63] Simulations of discrete quantum systems in continuous Euclidean time [J].

Beard, BB ;

Wiese, UJ .

PHYSICAL REVIEW LETTERS, 1996, 77 (25) :5130-5133

[64] Universality of the REM for dynamics of mean-field spin glasses [J].

Ben Arous, Gerard ;

Bovier, Anton ;

Cerny, Jiri .

COMMUNICATIONS IN MATHEMATICAL PHYSICS, 2008, 282 (03) :663-695

[65] Strengths and weaknesses of quantum computing [J].

Bennett, CH ;

Bernstein, E ;

Brassard, G ;

Vazirani, U .

SIAM JOURNAL ON COMPUTING, 1997, 26 (05) :1510-1523

[66] Quantum complexity theory [J].

Bernstein, E ;

Vazirani, U .

SIAM JOURNAL ON COMPUTING, 1997, 26 (05) :1411-1473

[67] Theoretical perspective on the glass transition and amorphous materials [J].

Berthier, Ludovic ;

Biroli, Giulio .

REVIEWS OF MODERN PHYSICS, 2011, 83 (02) :587-645

[68] Coarse-grained belief propagation for simulation of interacting quantum systems at all temperatures [J].

Bilgin, Ersen ;

Poulin, David .

PHYSICAL REVIEW B, 2010, 81 (05)

[69] A variational description of the ground state structure in random satisfiability problems [J].

Biroli, G ;

Monasson, R ;

Weigt, M .

EUROPEAN PHYSICAL JOURNAL B, 2000, 14 (03) :551-568

[70] Quantum Thouless-Anderson-Palmer equations for glassy systems [J].

Biroli, G ;

Cugliandolo, LF .

PHYSICAL REVIEW B, 2001, 64 (01) :142061-1420615

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