TY - JOUR

T1 - Approximating random quantum optimization problems

AU - Hsu, B.

AU - Laumann, C. R.

AU - Läuchli, A. M.

AU - Moessner, R.

AU - Sondhi, Shivaji Lal

PY - 2013/6/25

Y1 - 2013/6/25

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84879489080&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84879489080&partnerID=8YFLogxK

U2 - 10.1103/PhysRevA.87.062334

DO - 10.1103/PhysRevA.87.062334

M3 - Article

AN - SCOPUS:84879489080

SN - 1050-2947

VL - 87

JO - Physical Review A - Atomic, Molecular, and Optical Physics

JF - Physical Review A - Atomic, Molecular, and Optical Physics

IS - 6

M1 - 062334

ER -