Computational Complexity of Quantum Satisfiability

DOI10.1145/2869073zbMath1426.68123arXiv1004.1696OpenAlexW2346855750WikidataQ66459637 ScholiaQ66459637MaRDI QIDQ3177775

Martin Ziegler, Christian Herrmann

Publication date: 2 August 2018

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

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) Logical foundations of quantum mechanics; quantum logic (quantum-theoretic aspects) (81P10) 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)

Related Items (5)

Quantum logic is undecidable ⋮ Bit-complexity of classical solutions of linear evolutionary systems of partial differential equations ⋮ Definable relations in finite-dimensional subspace lattices with involution ⋮ Definable relations in finite dimensional subspace lattices with involution. II. Quantifier-free and homogeneous descriptions ⋮ On the complexity of equational decision problems for finite height complemented and orthocomplemented modular lattices

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