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$-body quantum satisfiability ($k$-QSAT) on large random graphs. As an approximation strategy, we optimize the solution space over ``classical'' p... View More