Quantum logic is undecidable

Tobias Fritz

Contact the author: Please use for correspondence this email.
Submission date: 20. Jul. 2016 (revised version: November 2016)
Pages: 12
Bibtex
MSC-Numbers: 03G12, 03B25, 46L99, 81P13
Keywords and phrases: Quantum logic, orthomodular lattices, Hilbert lattices, decidability, restricted word problem, residually finite-dimensional C*-algebras, quantum contextuality
Download full preprint: PDF (400 kB)

Abstract:
We investigate the first-order theory of closed subspaces of complex Hilbert spaces in the signature (∨,⊥,0), where ‘⊥’ is orthogonality. Our main result is that already its purely implicational fragment is undecidable: there is no algorithm to decide whether an implication between equations in the language of orthomodular lattices is valid in all complex Hilbert spaces. This is a simple corollary of a recent result of Slofstra in combinatorial group theory, and follows upon reinterpreting that result in terms of the hypergraph approach to contextuality.