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.
The topological physics of quantum Hall states is efficiently encoded in purely topological quantum field theories of the Chern-Simons type. The reliable inclusion of low-energy dynamical properties in a continuum description however typically requir
es proximity to a quantum critical point. We construct a field theory that describes the quantum transition from an isotropic to a nematic Laughlin liquid. The soft mode associated with this transition approached from the isotropic side is identified as the familiar intra-Landau level Girvin-MacDonald-Platzman mode. We obtain z=2 dynamic scaling at the critical point and a description of Goldstone and defect physics on the nematic side. Despite the very different physical motivation, our field theory is essentially identical to a recent geometric field theory for a Laughlin liquid proposed by Haldane.
