### Computational Complexity of Quantum SatisfiabilityComputational Complexity of Quantum Satisfiability

Access Restriction
Subscribed

 Author Herrmann, Christian ♦ Ziegler, Martin Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2016 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Blum-Shub-Smale model ♦ Quantum logic ♦ Computational complexity ♦ Existential theory of the reals ♦ Satisfiability Abstract We connect both discrete and algebraic complexity theory with the satisfiability problem in certain non-Boolean lattices. Specifically, quantum logic was introduced in 1936 by Garrett Birkhoff and John von Neumann as a framework for capturing the logical peculiarities of quantum observables: in the 1D case it coincides with Boolean propositional logic but, starting with dimension two, violates the distributive law. We introduce the weak and strong satisfiability problem for quantum logic propositional formulae. It turns out that in dimension two, both are also $\textit{NP}--complete.$ For higher-dimensional spaces $ℝ^{d}$ and $ℂ^{d}$ with $\textit{d}$ ≥ 3 fixed, on the other hand, we show both problems to be complete for the nondeterministic Blum-Shub-Smale (BSS) model of real computation. This provides a unified view on both Turing and real BSS complexity theory, and extends the (still relatively scarce) list of problems established $NP_{ℝ}--complete$ with one, perhaps, closest in spirit to the classical Cook-Levin Theorem. More precisely, strong satisfiability of ∧ ∨ ∧ --terms is complete, while that of ∧ ∨--terms (i.e., those in conjunctive form) can be decided in polynomial time in dimensions $\textit{d}≥$ 2. The decidability of the infinite-dimensional case being still open, we proceed to investigate the case of indefinite finite dimensions. Here, weak satisfiability still belongs to $NP_{R}$ and strong satisfiability is still hard; the latter, in fact, turns out as polynomial-time equivalent to the feasibility of noncommutative integer polynomial equations over matrix rings. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2016-05-04 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 63 Issue Number 2 Page Count 31 Starting Page 1 Ending Page 31

#### Open content in new tab

Source: ACM Digital Library