Computational Complexity of Quantum Satisfiability

DOI10.1145/2869073zbMATH Open1426.68123DBLPjournals/jacm/Herrmann016arXiv1004.1696OpenAlexW2346855750WikidataQ66459637 ScholiaQ66459637MaRDI QIDQ3177775FDOQ3177775

Martin Ziegler, Christian Herrmann

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Abstract: Quantum logic was introduced in 1936 by Garrett Birkhoff and John von Neumann as a framework for capturing the logical peculiarities of quantum observables. It generalizes, and on 1-dimensional Hilbert space coincides with, Boolean propositional logic. We introduce the weak and strong satisfiability problem for quantum logic terms. It turns out that in dimension two both are also NP-complete. For higher-dimensional spaces R^d and C^d with d>2 fixed, on the other hand, we show both problems to be complete for the nondeterministic Blum-Shub-Smale model of real computation. This provides a unified view on both Turing and real BSS complexity theory; and extends the still relatively scarce family of NP_R-complete problems with one perhaps closest in spirit to the classical Cook-Levin Theorem. Our investigations on the dimensions a term is weakly/strongly satisfiable in lead to satisfiability problems in indefinite finite and finally in infinite dimension. Here, strong satisfiability turns out as polynomial-time equivalent to the feasibility of noncommutative integer polynomial equations

Full work available at URL: https://arxiv.org/abs/1004.1696

zbMATH Keywords

computational complexityquantum logicsatisfiabilityBlum-Shub-Smale modelexistential theory of the reals

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12) Computation over the reals, computable analysis (03D78) Logical foundations of quantum mechanics; quantum logic (quantum-theoretic aspects) (81P10)

Cited In (9)

• Definable relations in finite-dimensional subspace lattices with involution
• A SCHEMATIC DEFINITION OF QUANTUM POLYNOMIAL TIME COMPUTABILITY
• Title not available (Why is that?)
• Bit-complexity of classical solutions of linear evolutionary systems of partial differential equations
• Theory and Applications of Models of Computation
• Quantum logic is undecidable
• Classical vs quantum satisfiability in linear constraint systems modulo an integer
• On the complexity of equational decision problems for finite height complemented and orthocomplemented modular lattices
• Definable relations in finite dimensional subspace lattices with involution. II. Quantifier-free and homogeneous descriptions

   Recommendations

• Quantum Complexity Theory 👍 👎
• Computational complexity of the quantum separability problem 👍 👎
• On quantum complexity 👍 👎
• Quantum Computability 👍 👎
• Complexity Bounds of Constant-Space Quantum Computation 👍 👎
• Title not available (Why is that?) 👍 👎
• Quantum implicit computational complexity 👍 👎
• Qubit complexity of continuous problems 👍 👎
• Title not available (Why is that?) 👍 👎
• On exact quantum query complexity 👍 👎

This page was built for publication: Computational Complexity of Quantum Satisfiability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177775)