The effect of quantum fluctuations on the coloring of random graphs

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.

28 pages, 17 figures

References in corpus (14)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Mathematical Foundation of Quantum Annealing
• Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Simple Glass Models and their Quantum Annealing
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• On the path integral representation for quantum spin models and its application to the quantum cavity method and to Monte Carlo simulations
• Cavity method for quantum spin glasses on the Bethe lattice
• On quantum mean-field models and their quantum annealing
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
• Locked constraint satisfaction problems
• Potts Glass on Random Graphs
• Random subcubes as a toy model for constraint satisfaction problems
• A solvable model of quantum random optimization problems