Approximating random quantum optimization problems
Benjamin Hsu, Chris R. Laumann, Andreas M. Läuchli, Roderich Moessner, S. L. Sondhi · Physical Review A · 2013
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'' 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 the structure of the solution space of random $k$-QSAT. Simulated annealing exhibits metastability in similar ``hard'' regions of parameter space; and (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.