Title: The Computability of Quantum Games

Abstract: 
Quantum entanglement -- the phenomenon where distant
particles can be correlated in ways that cannot be explained by
classical physics -- has mystified scientists since the 1930s, when
quantum theory was beginning to emerge. Since then, investigation into
fundamental questions about quantum entanglement has continually
propelled seismic shifts in our understanding of nature. Examples
include Einstein, Podolsky and Rosen's famous 1935 paper about the
incompleteness of quantum mechanics, and John Bell's refutation of
EPR's argument, 29 years later, via an experiment to demonstrate the
non-classicality of quantum entanglement.

More recently, the field of quantum computing has motivated
researchers to study entanglement in information processing contexts.
One question of deep interest concerns the computability of quantum
games, which are abstractions of Bell's experiments. The question is
simple: is there an algorithm to compute the optimal winning
probability of a quantum game -- or at least, approximate it?

In a paper with Ji, Natarajan, Vidick, and Wright, we showed that
there does _not_ exist such an algorithm. Through a series of
remarkable connections established by prior work, this uncomputability
result yields negative answers to Tsirelson's problem, a question in
mathematical physics, as well as Connes' embedding problem, a major
question in functional analysis.

In this talk, I will give an overview of how these questions from
disparate fields -- quantum physics, pure mathematics, complexity
theory -- all connect together. Time permitting, I will also discuss
work with Mousavi and Nezhadi on how different versions of the quantum
games computability problem appear to neatly line up with different
levels of the arithmetical hierarchy.

No physics background required.