The effect of quantum fluctuations on the coloring of random graphs
arXiv:1302.6861 · doi:10.1103/PhysRevA.87.042322
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.
arXiv comment28 pages, 17 figures
References in corpus (44)
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Analytical Solution of the Off-Equilibrium Dynamics of a Long Range Spin-Glass Model
- The Bethe lattice spin glass revisited
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- The structural glass transition and the entropy of the metastable states
- Spin-Glass Theory for Pedestrians
- Mathematical Foundation of Quantum Annealing
- Phase Transitions in the Coloring of Random Graphs
- Anderson localization casts clouds over adiabatic quantum optimization
- Statistical mechanics of the random K-SAT model
- First order phase transition in the Quantum Adiabatic Algorithm
- 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
- First Order Quantum Phase Transition in Adiabatic Quantum Computation
- Polynomial iterative algorithms for coloring and analyzing random graphs
- Simple Glass Models and their Quantum Annealing
- The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
- First-order transitions and the performance of quantum algorithms in random optimization problems
- Adiabatic Quantum Computing for Random Satisfiability Problems
- Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
- The Quantum Spherical p-Spin-Glass Model
- 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
- Quantum TAP equations
- Locked constraint satisfaction problems
- Following Gibbs States Adiabatically - The Energy Landscape of Mean Field Glassy Systems
- Quantum phase transition in spin glasses with multi-spin interactions
- Quenched complexity of the p-spin spherical spin-glass with external magnetic field
- Chaotic temperature dependence in a model of spin glasses
- Potts Glass on Random Graphs
- Quiet Planting in the Locked Constraint Satisfaction Problems
- Algorithmic approach to adiabatic quantum optimization
- Random Graph Coloring - a Statistical Physics Approach
- Random subcubes as a toy model for constraint satisfaction problems
- Succinct quantum proofs for properties of finite groups
- A solvable model of quantum random optimization problems
- The quantum Biroli-Mézard model: glass transition and superfluidity in a quantum lattice glass model
- Elimination of Perturbative Crossings in Adiabatic Quantum Optimization
- A note on the Guerra and Talagrand theorems for Mean Field Spin Glasses: the simple case of spherical models