  We present a study of the phase diagram of a random optimization problem in
presence of quantum fluctuations. Our main result is the characterization of
the nature of the phase transition, which we find to be a first-order quantum
phase transition. We provide evidence that the gap vanishes exponentially with
the system size at the transition. This indicates that the Quantum Adiabatic
Algorithm requires a time growing exponentially with system size to find the
ground state of this problem.
