Henry Yuen, University of Toronto
An outstanding open question in quantum information theory concerns the computational complexity of nonlocal games. in a nonlocal game, a classical verifier interacts with multiple players that cannot communicate, but are allowed to share entanglement. In a recent breakthrough result, Slofstra showed that the following problem is undecidable: given a nonlocal game, is there a quantum strategy for the players to win with probability 1?
In this work, we show that even the approximation problem for nonlocal games is extremely difficult. We prove that approximating the maximum winning probability to within additive error 1/f(n) is as hard as any problem solvable in time 2^O(f (n)), even using nondeterministic resources. Here, n is the size of the game, and f(n) is an arbitrary (time-constructible) function, such as an iterated exponential function. By contrast, the maximum winning probability for games with classical players can be exactly computed in nondeterministic exp(n) time. The high complexity of nonlocal games arises from the ability to encode arbitrarily complex computations into entangled states.
I will discuss some consequences of our result: (1) we give an alternate proof of Slofstra’s undecidability result; (2) we present polynomial-size quantum proof systems for nondeterministic 2^O(f (n)) time with completeness-soundness gap 1/f(n) for arbitrary f(n), and (3) we show that seemingly minor quantitative improvements to our result would provide a negative resolution to a multipartite version of Tsirelson's problem on the relation between the commuting operator and tensor product models for quantum correlations.
Joint work with Joe Fitzsimons, Zhengfeng Ji, and Thomas Vidick.