Quantum logic is undecidable

Abstract

We investigate the first-order theory of closed subspaces of complex Hilbert spaces in the signature $(\vee ,\perp ,0,1)$, where `$\perp$' is the orthogonality relation. Our main result is that already its quasi-identities are undecidable: there is no algorithm to decide whether an implication between equations and orthogonality relations implies another equation. This is a corollary of a recent result of Slofstra in combinatorial group theory. It follows upon reinterpreting that result in terms of the hypergraph approach to quantum contextuality, for which it constitutes a proof of the inverse sandwich conjecture. It can also be interpreted as stating that a certain quantum satisfiability problem is undecidable.

12 pages. v5: corrected the proofs of Lemma 15 and Remark 16 showing the impossibility of recursive axiomatization of quantum logic. Added acknowledgment for Andre Kornell

References in corpus (1)

• Perfect Commuting-Operator Strategies for Linear System Games

Cited by in corpus (7)

• Classical analogue of quantum superdense coding and communication advantage of a single quantum system
• Undecidability in Physics: a Review
• Many bounded versions of undecidable problems are NP-hard
• Magic squares: Latin, Semiclassical and Quantum
• Can quantum gravity be both consistent and complete?
• A natural deduction system for orthomodular logic
• No quantum solutions to linear constraint systems in odd dimension from Pauli group and diagonal Cliffords