  Alongside the effort underway to build quantum computers, it is important to
better understand which classes of problems they will find easy and which
others even they will find intractable. We study random ensembles of the
QMA$_1$-complete quantum satisfiability (QSAT) problem introduced by Bravyi.
QSAT appropriately generalizes the NP-complete classical satisfiability (SAT)
problem. We show that, as the density of clauses/projectors is varied, the
ensembles exhibit quantum phase transitions between phases that are satisfiable
and unsatisfiable. Remarkably, almost all instances of QSAT for any hypergraph
exhibit the same dimension of the satisfying manifold. This establishes the
QSAT decision problem as equivalent to a, potentially new, graph theoretic
problem and that the hardest typical instances are likely to be localized in a
bounded range of clause density.
