Product, generic, and random generic quantum satisfiability

C. R. Laumann, A. M. Läuchli, R. Moessner, A. Scardicchio, Shivaji Lal Sondhi

Research output: Contribution to journalArticle

24 Scopus citations

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.

Original languageEnglish (US)
Article number062345
JournalPhysical Review A - Atomic, Molecular, and Optical Physics
Volume81
Issue number6
DOIs
StatePublished - Jun 28 2010

All Science Journal Classification (ASJC) codes

  • Atomic and Molecular Physics, and Optics

Fingerprint Dive into the research topics of 'Product, generic, and random generic quantum satisfiability'. Together they form a unique fingerprint.

  • Cite this