  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.
