TY - ELEC
AU - John Wright
PY - 2019
TI - Nonlocal games are harder to approximate than we thought!
LA - eng
M3 - Moving Image
AB - 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.
N2 - 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.
UR - https://open.library.ubc.ca/collections/48630/items/1.0388287
ER - End of Reference