Open Collections

Nonlocal games are harder to approximate than we thought!

Banff International Research Station for Mathematical Innovation and Discovery

One of the most confounding open problems in quantum computing is whether we can approximate the quantum value of a nonlocal game, and, if so, how quickly. So far, our progress has been dismal: in spite of decades of work on this problem, we still have not even devised a *finite* time algorithm to solve it! Recent results have hinted that this might not be due to a failing of our imagination, but rather that this problem might be intrinsically hard, even undecidable (which would imply the Connes embedding conjecture is false). Thomas Vidick showed that this problem is NP-hard, and, in follow-up work with Anand Natarajan, strengthened this lower bound to QMA-hard. In this talk, I will discuss joint work with Anand, incomparable to the QMA-hardness result, which strictly improves on Thomas' original NP-hardness result. In the language of computational complexity theory, we show that NEEXP is contained in MIP*. Our result crucially uses self-testing. in particular the quantum low-degree test introduced by Anand in his previous talk.

Mathematics; Functional analysis; Quantum theory

video/mp4

Author affiliation: Massachusetts Institute of Technology (MIT)

2020-01-13

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/73309

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/