Coudron, Matthew ;
Slofstra, William
Complexity Lower Bounds for Computing the ApproximatelyCommuting Operator Value of NonLocal Games to High Precision
Abstract
We study the problem of approximating the commutingoperator value of a twoplayer nonlocal game. It is wellknown that it is NPcomplete to decide whether the classical value of a nonlocal game is 1 or 1 epsilon, promised that one of the two is the case. Furthermore, as long as epsilon is small enough, this result does not depend on the gap epsilon. In contrast, a recent result of Fitzsimons, Ji, Vidick, and Yuen shows that the complexity of computing the quantum value grows without bound as the gap epsilon decreases. In this paper, we show that this also holds for the commutingoperator value of a game. Specifically, in the language of multiprover interactive proofs, we show that the power of MIP^{co}(2,1,1,s) (proofs with two provers, one round, completeness probability 1, soundness probability s, and commutingoperator strategies) can increase without bound as the gap 1s gets arbitrarily small.
Our results also extend naturally in two ways, to perfect zeroknowledge protocols, and to lower bounds on the complexity of computing the approximatelycommuting value of a game. Thus we get lower bounds on the complexity class PZKMIP^{co}_{delta}(2,1,1,s) of perfect zeroknowledge multiprover proofs with approximatelycommuting operator strategies, as the gap 1s gets arbitrarily small. While we do not know any computable time upper bound on the class MIP^{co}, a result of the first author and Vidick shows that for s = 11/poly(f(n)) and delta = 1/poly(f(n)), the class MIP^{co}_delta(2,1,1,s), with constant communication from the provers, is contained in TIME(exp(poly(f(n)))). We give a lower bound of coNTIME(f(n)) (ignoring constants inside the function) for this class, which is tight up to polynomial factors assuming the exponential time hypothesis.
BibTeX  Entry
@InProceedings{coudron_et_al:LIPIcs:2019:10847,
author = {Matthew Coudron and William Slofstra},
title = {{Complexity Lower Bounds for Computing the ApproximatelyCommuting Operator Value of NonLocal Games to High Precision}},
booktitle = {34th Computational Complexity Conference (CCC 2019)},
pages = {25:125:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771160},
ISSN = {18688969},
year = {2019},
volume = {137},
editor = {Amir Shpilka},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10847},
URN = {urn:nbn:de:0030drops108478},
doi = {10.4230/LIPIcs.CCC.2019.25},
annote = {Keywords: Quantum complexity theory, Nonlocal game, Multiprover interactive proof, Entanglement}
}
2019
Keywords: 

Quantum complexity theory, Nonlocal game, Multiprover interactive proof, Entanglement 
Seminar: 

34th Computational Complexity Conference (CCC 2019)

Issue date: 

2019 
Date of publication: 

2019 