We report a cluster of results regarding the difficulty of finding approximate ground states to typical instances of the quantum satisfiability problem $k$-QSAT on large random graphs. As an approximation strategy, we optimize the solution space over
`classical product states, which in turn introduces a novel autonomous classical optimization problem, PSAT, over a space of continuous degrees of freedom rather than discrete bits. Our central results are: (i) The derivation of a set of bounds and approximations in various limits of the problem, several of which we believe may be amenable to a rigorous treatment. (ii) A demonstration that an approximation based on a greedy algorithm borrowed from the study of frustrated magnetism performs well over a wide range in parameter space, and its performance reflects structure of the solution space of random $k$-QSAT. Simulated annealing exhibits metastability in similar `hard regions of parameter space. (iii) A generalization of belief propagation algorithms introduced for classical problems to the case of continuous spins. This yields both approximate solutions, as well as insights into the free energy `landscape of the approximation problem, including a so-called dynamical transition near the satisfiability threshold. Taken together, these results allow us to elucidate the phase diagram of random $k$-QSAT in a two-dimensional energy-density--clause-density space.
