The classical statistical mechanical approach to complexity theory proceeds from the study of ensembles of computationally intractable optimization problems as a species of unusual disordered magnetic systems. Over the last thirty years, researchers have used this approach to supplement worst-case hardness results encoded by complexity theory with detailed information about thermodynamic and dynamic phase transitions in the structure of typical cases. This exchange of ideas between classical statistical mechanics and computer science enabled the development of important heuristic algorithms such as simulated annealing and survey propagation and further refined our understanding of glassiness and critical slowing in physical disordered systems.

In this thesis, we map out an analogous program in the quantum context. The question is simple: what can quantum statistical mechanics reveal about the difficulty of solving hard quantum optimization problems? Or more directly, what makes those problems hard even for quantum computers? In this pursuit, we introduce the study of ensembles of optimization problems whose complexity status is intrinsically quantum mechanical (Part I) and develop techniques to study quantum spin glasses and the transverse field adiabatic algorithm applied to classically hard random optimization problems (Part II). In particular, we introduce the study of random quantum satisfiability (QSAT) and identify the coarse aspects of its phase diagram, including a new form of entanglement transition. We generalize the cavity method to the study of quantum models and use it to study the transverse field Ising glass and frustrated AKLT models on the Bethe lattice. We further apply the cavity method to extract Griffiths-McCoy singularities in a diluted (classical) ferromagnet and finally observe that there are no Goldstone bosons on the Bethe lattice.