Approximating random quantum optimization problems

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 introdu... View More