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
Effect of quantum fluctuations on the coloring of random graphs / Bapst, V; Semerjian, G; Zamponi, F. - In: PHYSICAL REVIEW A. - ISSN 1050-2947. - 87:4(2013). [10.1103/PhysRevA.87.042322]
Effect of quantum fluctuations on the coloring of random graphs
Zamponi F
2013
Abstract
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.042322I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
