  In this paper we show that the performance of the quantum adiabatic algorithm
is determined by phase transitions in underlying problem in the presence of
transverse magnetic field $\Gamma$. We show that the quantum version of random
Satisfiability problem with 3 bits in a clause (3-SAT) has a first-order
quantum phase transition. We analyze the phase diagram $\gamma=\gamma(\Gamma)$
where $\gamma$ is an average number of clauses per binary variable in 3-SAT.
The results are obtained in a closed form assuming replica symmetry and
neglecting time correlations at small values of the transverse field $\Gamma$.
In the limit of $\Gamma=0$ the value of $\gamma(0)\approx$ 5.18 corresponds to
that given by the replica symmetric treatment of a classical random 3-SAT
problem. We demonstrate the qualitative similarity between classical and
quantum versions of this problem.
