Published:
[Erscheinungsort nicht ermittelbar]: Banff International Research Station (BIRS) for Mathematical Innovation and Discovery, 2019
Published in:The Many Faceted Connes Embedding Problem (19w5163) ; (Jan. 2019)
Extent:
1 Online-Ressource (298 MB, 00:43:23:20)
Language:
English
DOI:
10.5446/57934
Identifier:
Origination:
Footnote:
Audiovisuelles Material
Description:
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