Classical and quantum satisfiability
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 co...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2012-03-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1203.6161v1 |
| _version_ | 1818511474934415360 |
|---|---|
| author | Anderson de Araújo Marcelo Finger |
| author_facet | Anderson de Araújo Marcelo Finger |
| author_sort | Anderson de Araújo |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-10T23:33:45Z |
| format | Article |
| id | doaj.art-8edec572ee1d4dbeb465642b25d41bbc |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-12-10T23:33:45Z |
| publishDate | 2012-03-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-8edec572ee1d4dbeb465642b25d41bbc2022-12-22T01:29:16ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802012-03-0181Proc. LSFA 2011798410.4204/EPTCS.81.6Classical and quantum satisfiabilityAnderson de AraújoMarcelo FingerWe 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.http://arxiv.org/pdf/1203.6161v1 |
| spellingShingle | Anderson de Araújo Marcelo Finger Classical and quantum satisfiability Electronic Proceedings in Theoretical Computer Science |
| title | Classical and quantum satisfiability |
| title_full | Classical and quantum satisfiability |
| title_fullStr | Classical and quantum satisfiability |
| title_full_unstemmed | Classical and quantum satisfiability |
| title_short | Classical and quantum satisfiability |
| title_sort | classical and quantum satisfiability |
| url | http://arxiv.org/pdf/1203.6161v1 |
| work_keys_str_mv | AT andersondearaujo classicalandquantumsatisfiability AT marcelofinger classicalandquantumsatisfiability |