Quantum Phase Transition and complexity of adiabatic quantum algorithm for Constraint Satisfaction problem

We study the dynamics of adiabatic quantum computation (AQC) for solving the problem of satisfiability of randomly chosen clauses, each with 3 Boolean variables (3sat). We map this problem to that of a diluted long-range spin glass in traverse magnetic field and derive a self-consistent equation for the order parameter. We show the existence of the first-order quantum phase transition and investigate analytically and numerically the phase diagram on the plane: strength of the transverse field $\Gamma$ vs the ratio $\gamma$=M/N of a number of clauses M to a number of variables N. We show that the phase transition line approaches $\Gamma$=0 at the point of a classical replica symmetry breaking transition $\gamma_{RSB}$. We discuss the implications of the quantum phase transition for the complexity of the AQC for the 3sat.