Approximating random quantum optimization problems

Abstract

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.

14 pages, 9 figures

References in corpus (6)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Cavity method for quantum spin glasses on the Bethe lattice
• Locked constraint satisfaction problems
• On product, generic and random generic quantum satisfiability
• Approximation algorithms for QMA-complete problems
• AKLT Models with Quantum Spin Glass Ground States

Cited by in corpus (8)

• Quantum annealing: the fastest route to quantum computation?
• When a local Hamiltonian must be frustration-free
• Variational wavefunctions for Sachdev-Ye-Kitaev models
• Clustering in Hilbert space of a quantum optimization problem
• Reversible first-order transition in Pauli percolation
• Numerical optimization using flow equations
• Testing quantum satisfiability
• Classical-Quantum Mixing in the Random 2-Satisfiability Problem