Quantum proof systems -- how powerful are they?

More on Anindya De

Abstract: Interactive proof systems have been a central object of complexity theory for nearly forty. In the early 2000s, quantum information theorists asked what happens if quantum entanglement is introduced? Is it more or less powerful than its classical counterpart remained open for a while? For good reason. In 2008, quantum information theorists connected the power of quantum proof systems to one of the most famous open questions in operator theory -- the Connes embedding conjecture.

In the last decade,  Ji, Natarajan, Vidick, Wright and Yuen showed that such interactive proof systems can even capture undecidable problems such as the Halting problem. This in turn shows that the Connes embedding conjecture is false. In this talk, I will discuss the model of quantum proof systems and its connection with the so-called Tsirelson's problem which turns out to be equivalent to the Connes conjecture.

The talk will be very high level, discussing the meaning of quantum proof systems. There will be no discussion about the actual proof of Ji et al. -- primarily because the speaker does not know it.