Classical-quantum mixing in the random 2-satisfiability problem

Ionut Dragos Potirniche, C. R. Laumann, Shivaji Lal Sondhi

Research output: Contribution to journalArticlepeer-review


Classical satisfiability (SAT) and quantum satisfiability (QSAT) are complete problems for the complexity classes NP and QMA, respectively, and they are believed to be intractable for both classical and quantum computers. Statistical ensembles of instances of these problems have been studied previously in an attempt to elucidate their typical, as opposed to worst-case, behavior. In this paper, we introduce a statistical ensemble that interpolates between classical and quantum. For the simplest 2-SAT-2-QSAT ensemble, we find the exact boundary that separates SAT and UNSAT instances. We do so by establishing coincident lower and upper bounds, in the limit of large instances, on the extent of the UNSAT and SAT regions, respectively.

Original languageEnglish (US)
Article number040301
JournalPhysical Review A - Atomic, Molecular, and Optical Physics
Issue number4
StatePublished - Oct 1 2015

All Science Journal Classification (ASJC) codes

  • Atomic and Molecular Physics, and Optics


Dive into the research topics of 'Classical-quantum mixing in the random 2-satisfiability problem'. Together they form a unique fingerprint.

Cite this