Logical approach to quantum mechanics and contextuality

• Applicant: Dr. Jonni Virtema, Ph.D.
• Subject Area: Theoretical Computer Science
• Term: since 2019
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 432788559

Probabilistic team semantics has recently been recognised as a prospective setting to model properties of quantum mechanics. The objective of this project is to explore and develop this observation. One of the goals of the project is to characterise properties of quantum systems by logical languages in the same spirit as descriptive complexity theory does for complexity classes. We expect that our logical characterisations will clarify and give new insight about notions in quantum mechanics. We are interested in the intriguing question, when probabilistic notions used in quantum mechanics reduce to their possibilistic counterparts.Logics with probabilistic team semantics are intimately connected to complexity classes defined via the so-called Blum-Shub-Smale (BSS for short) machines. BSS machines are a model of computation over the real numbers. Simply put, a BSS machine can be seen as a Turing machine that can take real numbers as inputs and that can do arithmetic operations on real numbers in a unit step. Descriptive complexity theory of complexity classes over real numbers with respect to BSS machines was initiated by Grädel and Meer. They established that variants of existential second-order logic and fixed point logic, that can express arithmetic properties of real numbers, capture exactly the analogues of nondeterministic and deterministic polynomial time on the BSS model. An exciting result of Durand et al. connects logics with probabilistic team semantics to the logics of Grädel and Meer, and to the BSS model of computation. This connects directly properties of probabilistic hidden-variable models to the BSS model of computation.An intriguing open problem is whether the complexity classes defined via BSS machines collapse to the corresponding classes defined via Turing machines, when the input does not contain real numbers. We aim to develop logics using probabilistic team semantics for capturing complexity classes defined via the BSS model, and use the logical characterisations to establish a collapse or separation of the related complexity classes.Many decision problems related to probabilistic hidden-variable models have trivial complexity upper bounds in the BSS setting. Results here will yield nontrivial upper bounds in the classical setting (i.e., with respect to computation with Turing machines). Our work on descriptive complexity of computation over the real numbers might lead to solutions of famous open problems, such as whether a complexity class called "exists R" collapses to NP. In any case, we will contribute to the understanding of complexity classes defined via BSS machines, and to their connections to traditional complexity classes.

• DFG Programme: Research Grants
• International Connection: United Kingdom