zbMATH — the first resource for mathematics

Quantum logic is undecidable. (English) Zbl 1473.03039
The main result of this paper is the following theorem.
Theorem. For a complex Hilbert space \(\mathcal{H}\), let \(\mathcal{C}\left( \mathcal{H}\right) \) denote the lattice of closed linear subspaces of \(\mathcal{H}\), let \(0,1\in\mathcal{C}\left( \mathcal{H}\right) \) stand for the zero and full subspaces, and let \(P_{1},P_{2},...\) be free variables taking values in \(\mathcal{C}\left( \mathcal{H}\right) \). Then there is no algorithm to decide whether a sentence of the form \[ \forall P_{1}...\forall P_{n}\left( E_{1}\wedge...\wedge E_{k}\rightarrow 0=1\right) \] holds for every \(\mathcal{H}\), where each \(E_{i}\) is a formula of one of the following two:
an equation of the form \[ P_{i_{1}}\vee...\vee P_{i_{k}}=1 \]
an orthogonality relation \[ P_{i_{1}}\perp P_{i_{2}} \] between two free variables.
That is to say, quantum logic is already undecidable even on quasi-identities [A. I. Mal’tsev, Алгебраические системы (Russian). Moskva: Izdat. ”Nauka” (1970; Zbl 0223.08001)]. The key ingredient leading to the above theorem is an undecidability result of W. Slofstra [J. Am. Math. Soc. 33, No. 1, 1–56 (2020; Zbl 07171891)] depending in turn on [R. Cleve et al., J. Math. Phys. 58, No. 1, 012202, 7 p. (2017; Zbl 1355.81048); R. Cleve and R. Mittal, Lect. Notes Comput. Sci. 8572, 320–331 (2014; Zbl 1364.91015)]. The author remarks the connection of Slofstra’s work [loc. cit.] to quantum logic through the hypergraph approach to contextuality [A. Acín et al., Commun. Math. Phys. 334, No. 2, 533–628 (2015; Zbl 1312.81010)].
It was shown in [L. Lipshitz, Trans. Am. Math. Soc. 193, 171–180 (1974; Zbl 0288.02026)] that the purely implicational fragment of the theory of all \(\mathcal{C}\left( \mathbb{C}^{n}\right) \) is undecidable. M. A. E. H. Sherif [Algebra Univers. 37, No. 1, 70–76 (1997; Zbl 0902.06012)] has shown that any first-order theory between orthomodular lattices and finite orthomodular lattices is undecidable, while C. Herrmann [J. Symb. Log. 75, No. 3, 1102–1110 (2010; Zbl 1205.06005)] has established that the equational theory of the orthomodular lattice of projections of a finite von Neumann algebra factor is decidable.

03G12 Quantum logic
03B25 Decidability of theories and sets of sentences
46L99 Selfadjoint operator algebras (\(C^*\)-algebras, von Neumann (\(W^*\)-) algebras, etc.)
81P10 Logical foundations of quantum mechanics; quantum logic (quantum-theoretic aspects)
81P13 Contextuality in quantum theory
Full Text: DOI arXiv
[1] Birkhoff, G.; von Neumann, J., The logic of quantum mechanics, Ann. Math., 37, 4, 823-843 (1936) · Zbl 0015.14603
[2] Engesser, K.; Gabbay, DM; Lehmann, D., Handbook of quantum logic and quantum structures—quantum logic (2009), London: Elsevier, London · Zbl 1184.81003
[3] Kalmbach, G., Orthomodular lattices. London Mathematical Society Monographs (1983), London: Academic Press Inc, London · Zbl 0512.06011
[4] Kalmbach, G., Measures and Hilbert lattices (1986), Singapore: World Scientific, Singapore
[5] Svozil, K., Quantum Logic. Springer Series in Discrete Mathematics and Theoretical Computer Science (1998), Berlin: Springer, Berlin
[6] Piron, C., Axiomatique quantique, Helv. Phys. Acta, 37, 439-468 (1964) · Zbl 0141.23204
[7] Amemiya, I., Araki, H.: A remark on Piron’s paper. Publ. Res. Inst. Math. Sci. Ser. A 2, 423-427 (1966/7) · Zbl 0177.16103
[8] Wilbur, WJ, On characterizing the standard quantum logics, Trans. Am. Math. Soc., 233, 265-282 (1977) · Zbl 0366.06019
[9] Solèr, MP, Characterization of Hilbert spaces by orthomodular spaces, Commun. Algebra, 23, 1, 219-243 (1995) · Zbl 0827.46019
[10] Stubbe, I., Van Steirteghem, B.: Propositional systems, Hilbert lattices and generalized Hilbert spaces. In: Handbook of Quantum Logic and Quantum Structures, pp. 477-523. Elsevier Sci. B. V., Amsterdam (2007). arXiv:0710.2098 · Zbl 1126.81009
[11] Megill, ND; Pavičić, M., Hilbert lattice equations, Ann. Henri Poincaré, 10, 7, 1335-1358 (2010) · Zbl 1213.81022
[12] Megill, N.: Quantum logic explorer home page. http://us.metamath.org/qlegif/mmql.html (2014)
[13] Mal’cev, A.I.: Algebraic systems. In: Smirnov, D., Taĭclin, M. (eds.) Posthumous Edition. Springer, New York (1973). Translated from the Russian by B. D. Seckler and A. P. Doohovskoy, Die Grundlehren der mathematischen Wissenschaften, Band 192
[14] Bravyi, S.: Efficient algorithm for a quantum analogue of 2-SAT. arXiv:quant-ph/0602108 · Zbl 1218.81032
[15] Liang, Y-C; Spekkens, RW; Wiseman, HM, Specker’s parable of the over-protective seer: a road to contextuality, nonlocality and complementarity, Phys. Rep., 506, 1-2, 1-39 (2011)
[16] Slofstra, W.: Tsirelson’s problem and an embedding theorem for groups arising from non-local games. J. Am. Math. Soc. Page to appear. arXiv:1606.03140 · Zbl 07171891
[17] Cleve, R.; Liu, L.; Slofstra, W., Perfect commuting-operator strategies for linear system games, J. Math. Phys., 58, 1, 012202 (2017) · Zbl 1355.81048
[18] Cleve, R., Mittal, R.: Characterization of binary constraint system games. In: Automata, Languages, and Programming, Lecture Notes in Computer Science, vol. 8572. Springer, Berlin (2014). arXiv:1209.2729 · Zbl 1364.91015
[19] Acín, A.; Fritz, T.; Leverrier, A.; Sainz, AB, A combinatorial approach to nonlocality and contextuality, Commun. Math. Phys., 334, 2, 533-628 (2015) · Zbl 1312.81010
[20] Lipshitz, L., The undecidability of the word problems for projective geometries and modular lattices, Trans. Am. Math. Soc., 193, 171-180 (1974) · Zbl 0288.02026
[21] Sherif, MAEH, Decision problem for orthomodular lattices, Algebra Universalis, 37, 1, 70-76 (1997) · Zbl 0902.06012
[22] Herrmann, C., On the equational theory of projection lattices of finite von Neumann factors, J. Symb. Log., 75, 3, 1102-1110 (2010) · Zbl 1205.06005
[23] Herrmann, C.; Ziegler, M., Computational complexity of quantum satisfiability, J. ACM, 63, 2, 19 (2016) · Zbl 1426.68123
[24] Atserias, A., Kolaitis, P.G., Severini, S.: Generalized satisfiability problems via operator assignments (2017). arXiv:1704.01736 · Zbl 06810944
[25] Fritz. T.: Curious properties of free hypergraph c*-algebras. J. Oper. Theory. Page to appear. arXiv:1808.09220 · Zbl 1463.46100
[26] Peres, A., Incompatible results of quantum measurements, Phys. Lett. A, 151, 3-4, 107-108 (1990)
[27] Mermin, ND, Simple unified form for the major no-hidden-variables theorems, Phys. Rev. Lett., 65, 3373 (1990) · Zbl 0971.81501
[28] Pedersen, GK, \(C^{\ast } \)-Algebras and their Automorphism Groups, London Mathematical Society Monographs (1979), Cambridge: Academic Press, Cambridge
[29] Fritz, T.; Netzer, T.; Thom, A., Can you compute the operator norm?, Proc. Am. Math. Soc., 142, 4265-4276 (2014) · Zbl 1304.43001
[30] Hodges, W., Model Theory, Encyclopedia of Mathematics and Its Applications (1993), Cambridge: Cambridge University Press, Cambridge
[31] Rédei, M., Quantum Logic in Algebraic Approach (1998), Dordrecht: Kluwer Academic Publishers, Dordrecht · Zbl 0910.03038
[32] Svozil, K., Randomness and Undecidability in Physics (1993), River Edge: World Scientific Publishing Co., Inc., River Edge · Zbl 0791.68084
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.