Classical and quantum satisfiability

Anderson de Araújo
(University of São Paulo)
Marcelo Finger
(University of São Paulo)

We present the linear algebraic definition of QSAT and propose a direct logical characterization of such a definition. We then prove that this logical version of QSAT is not an extension of classical satisfiability problem (SAT). This shows that QSAT does not allow a direct comparison between the complexity classes NP and QMA, for which SAT and QSAT are respectively complete.

In Simona Ronchi della Rocca and Elaine Pimentel: Proceedings 6th Workshop on Logical and Semantic Frameworks with Applications (LSFA 2011), Belo Horizonte, Brazil, 27 August 2011, Electronic Proceedings in Theoretical Computer Science 81, pp. 79–84.
Published: 24th March 2012.

ArXived at: https://dx.doi.org/10.4204/EPTCS.81.6 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org