Effect of quantum fluctuations on the coloring of random graphs

被引：1

作者：

Bapst, Victor ^{[1
]}

Semerjian, Guilhem

Zamponi, Francesco

机构：

[1] CNRS, Unite Mixte Rech UMR 8549, LPTENS, F-75231 Paris 05, France

来源：

PHYSICAL REVIEW A | 2013年 / 87卷 / 04期

关键词：

SPIN-GLASS MODEL; GIBBS-STATES; POTTS GLASS; TRANSITION; COMPLEXITY; MECHANICS; ENTROPY;

D O I：

10.1103/PhysRevA.87.042322

中图分类号：

O43 [光学];

学科分类号：

070207 ; 0803 ;

摘要：

We present a study of the coloring problem (antiferromagnetic Potts model) of random regular graphs, submitted to quantum fluctuations induced by a transverse field, using the quantum cavity method and quantum Monte Carlo simulations. We determine the order of the quantum phase transition encountered at low temperature as a function of the transverse field and discuss the structure of the quantum spin-glass phase. In particular, we conclude that the quantum adiabatic algorithm would fail to solve efficiently typical instances of these problems because of avoided level crossings within the quantum spin-glass phase, caused by a competition between energetic and entropic effects. DOI: 10.1103/PhysRevA.87.042322

引用

页数：23

共 75 条

[51] Chaotic temperature dependence in a model of spin glasses - A random-energy random-entropy model [J].

Krzakala, F ;

Martin, OC .

EUROPEAN PHYSICAL JOURNAL B, 2002, 28 (02) :199-208

[52] Potts glass on random graphs [J].

Krzakala, F. ;

Zdeborova, L. .

EPL, 2008, 81 (05)

[53] Gibbs states and the set of solutions of random constraint satisfaction problems [J].

Krzakala, Florent ;

Montanari, Andrea ;

Ricci-Tersenghi, Federico ;

Semerjian, Guilhem ;

Zdeborova, Lenka .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2007, 104 (25) :10318-10323

[54] Path-integral representation for quantum spin models: Application to the quantum cavity method and Monte Carlo simulations [J].

Krzakala, Florent ;

Rosso, Alberto ;

Semerjian, Guilhem ;

Zamponi, Francesco .

PHYSICAL REVIEW B, 2008, 78 (13)

[55] Cavity method for quantum spin glasses on the Bethe lattice [J].

Laumann, C. ;

Scardicchio, A. ;

Sondhi, S. L. .

PHYSICAL REVIEW B, 2008, 78 (13)

[56] Analytic and algorithmic solution of random satisfiability problems [J].

Mézard, M ;

Parisi, G ;

Zecchina, R .

SCIENCE, 2002, 297 (5582) :812-815

[57] The Bethe lattice spin glass revisited [J].

Mézard, M ;

Parisi, G .

EUROPEAN PHYSICAL JOURNAL B, 2001, 20 (02) :217-233

[58]

Mezard M., 2011, QUANTUM INF COMPUT, V11, P0638

[59]

Mezard Marc, 1987, Spin glass theory and beyond

[60]

MITCHELL D, 1992, AAAI-92 PROCEEDINGS : TENTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE, P459

← 1 2 3 4 5 6 7 8 →