On product, generic and random generic quantum satisfiability

Abstract

We report a cluster of results on k-QSAT, the problem of quantum satisfiability for k-qubit projectors which generalizes classical satisfiability with k-bit clauses to the quantum setting. First we define the NP-complete problem of product satisfiability and give a geometrical criterion for deciding when a QSAT interaction graph is product satisfiable with positive probability. We show that the same criterion suffices to establish quantum satisfiability for all projectors. Second, we apply these results to the random graph ensemble with generic projectors and obtain improved lower bounds on the location of the SAT--unSAT transition. Third, we present numerical results on random, generic satisfiability which provide estimates for the location of the transition for k=3 and k=4 and mild evidence for the existence of a phase which is satisfiable by entangled states alone.

9 pages, 5 figures, 1 table. Updated to more closely match published version. New proof in appendix

Cited by in corpus (26)

• Hamiltonian complexity
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Quantum annealing: the fastest route to quantum computation?
• An introduction to quantum annealing
• Correlation Length versus Gap in Frustration-Free Systems
• Quantum Max-flow/Min-cut
• A Quantum Lovasz Local Lemma
• When a local Hamiltonian must be frustration-free
• Approximation algorithms for QMA-complete problems
• Complete Characterization of the Ground Space Structure of Two-Body Frustration-Free Hamiltonians for Qubits
• Quantum 3-SAT is QMA1-complete
• Continuum limits of homogeneous binary trees and the Thompson group
• On the quantum spin glass transition on the Bethe lattice
• Exact renormalization in quantum spin chains
• Clustering in Hilbert space of a quantum optimization problem
• Optimal control of a quantum sensor: A fast algorithm based on an analytic solution
• Approximating random quantum optimization problems
• A Novel Perspective on Ideal Chern Bands with Strong Short-Range Repulsion: Applications to Correlated Metals, Superconductivity, and Topological Order
• Adversarial Satisfiability Problem
• The 7 faces of quantum NP
• Approximation, Proof Systems, and Correlations in a Quantum World
• Statistical mechanics of classical and quantum computational complexity
• Quantum Lovász Local Lemma: Shearer's Bound is Tight
• The SAT-UNSAT transition in the adversarial SAT problem
• Classical-Quantum Mixing in the Random 2-Satisfiability Problem
• Testing quantum satisfiability