GTIIT-STU optics seminar

Computability-Theoretic Perspectives on Quantum Foundations

By Prof. Santiago Figueira, Department of Computer Science, University of Buenos Aires, Argentina

In this talk, I will present some results that lie at the intersection of computability theory and the foundations of quantum mechanics. Although these areas originate from different motivations, they share a common theme: both impose principled limits on what kinds of structures, sequences, or objects can exist. Computability theory classifies which processes or descriptions can arise from algorithms, while quantum theory constrains what correlations and preparations are physically meaningful. When the two viewpoints are combined, new questions appear about how algorithmic structure interacts with fundamental quantum features. Before discussing the results, I will briefly introduce the logical and computational notions involved, focusing only on the essential ideas so that the tools are clear even to an audience without prior background in computability. I will then examine the consequences of using algorithmically generated pseudorandomness inside quantum experiments. While pseudorandomness is routinely used in practice, we show that it can lead to detectable deviations from the ideal behavior predicted by quantum theory. In Bell experiments, algorithmic patterns in the choice of measurements can be learned and exploited to simulate nonlocal correlations. I will also comment on a conceptual contribution of logic to the problem of mutually unbiased bases (MUBs): the existence of kMUBs in a given dimension can be expressed as a first-order statement over the reals. This places the problem within a decidable logical framework, even though the associated algorithms are far from practical for non–prime-power dimensions. The logical formulation also shows that the search for MUBs can be restricted to simpler real-closed fields without changing the underlying mathematical question. Together, these results show how algorithmic considerations—whether in the generation of randomness or in the logical structure of quantum constructions—interact with central notions in quantum theory. They offer new conceptual viewpoints rather than computational tools, revealing how foundational questions in physics can benefit from ideas rooted in computability and logic.