QMATH-OpAlg Seminar: Computational complexity and the quantum value of non-local games
Title: Computational complexity and the quantum value of non-local games
Abstract: It is undecidable to compute the quantum value of a non-local game perfectly. But how difficult is it to approximate the value of a non-local game? We do not currently have any decidable upper bound on this task. For lower bounds, a result of Fitzsimmons, Ji, Vidick, and Yuen states that for any computable function f(n), computing the quantum value of a game to accuracy 1/f(n) requires time complexity NTIME(exp(f(n))). Here we show a similar result for approximating the commuting-operator value of a linear system non-local game. Interestingly, while we get a quantitatively worse lower bound of coNTIME(f(n)) for accuracy 1/f(n), our lower bound also extends to a lower bound on the time complexity of computing the approximately-commuting value of a non-local game. With an appropriate choice of parameters, this lower bound for the approximately-commuting value seems close to tight. I will also discuss connections with zero-knowledge proof systems.
Joint work with Matt Coudron.