THIS EVENT HAS BEEN CANCELLED

Milestones on the Road from Operator Algebras to Computation Complexity

Mary Beth Ruskai, Ph.D.

University of Vermont

Abstract

In January, 2020 a group of 5 quantum computer scientists announced that there are non-local quantum games for which the problem of determining its entanglement value can be reduced to the Halting Problem and is, hence, undecidable. This immediately implied a resolution of the Connes Embedding Problem for von Neumann algebras, which has been an open question for over 40 years. During this time, there have been numerous reformulations of Connes' problem in many different areas of mathematics so that this stunning result in complexity theory has far-ranging implications.

This talk will describe part of the route through quantum information theory in terms of Tsirelson's problem, Bell inequalities, quantum entanglement and non-local games which can be recast into the language of interactive proof systems. No prior knowledge of quantum theory is assumed; results will be illustrated with one or two simple examples of non-local games.

arxiv:2002.04381 MIP* = RE by Li,Natarajan, Vidick, Wright and Yuen https://arxiv.org/abs/2001.04383

Thomas Vidick has a very readable introduction (written before the problem had been resolved) in the Nov. AMS Notices pp. 1681--1627. https://www.ams.org/journals/notices/201910/rnoti-p1618.pdf