Phase transitions in random quantum satisfiability

The potential power of quantum computers is a subject of great current interest and the raison d'etre for the intense effort and progress to build them. Naturally much theoretical interest has focused on algorithms that outperform their classical counterpart but recent developments in quantum complexity theory suggest that we already know problems, those shown to be QMA-complete, whose worst case instances would take a quantum computer exponentially long to solve. As in classical complexity theory the supposed difficulty of QMA complete problems follows from the existence of polynomial transformations relating any of the large class of QMA problems to instances of QMA-complete questions. This does not directly address the question of why this problem has hard instances and what features they posses. In this work we attempt to investigate the features of hard instances of a QMA complete problem introduced by S. Bravyi: quantum k-SAT. We use techniques of statistical physics of disordered systems in order to study a random ensemble of quantum k-SAT instances parametrized by clause density $\alpha$ in a program that is analogous to recent studies of classical random k-SAT. We establish a phase transition in satisfiability as a function of clause density and show that the problem almost always reduces to identifying a classical graph property.