Document Open Access Logo

Complexity Lower Bounds for Computing the Approximately-Commuting Operator Value of Non-Local Games to High Precision

Authors Matthew Coudron , William Slofstra

PDF
Thumbnail PDF

File

LIPIcs.CCC.2019.25.pdf
  • Filesize: 0.52 MB
  • 20 pages

Document Identifiers

Author Details

Matthew Coudron
  • Institute for Quantum Computing, University of Waterloo, Waterloo, Canada
William Slofstra
  • Institute for Quantum Computing and Department of Pure Mathematics, University of Waterloo, Waterloo, Canada

Funding

  • Coudron, Matthew: Supported at the IQC by Canada’s NSERC and the Canadian Institute for Advanced Research (CIFAR), and through funding provided to IQC by the Government of Canada and the Province of Ontario.
  • Slofstra, William: Supported by NSERC DG 2018-03968.

Acknowledgements

We thank Zhengfeng Ji, Alex Bredariol Grilo, Anand Natarajan, Thomas Vidick, and Henry Yuen for helpful discussions.

Cite As Get BibTex

Matthew Coudron and William Slofstra. Complexity Lower Bounds for Computing the Approximately-Commuting Operator Value of Non-Local Games to High Precision. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 25:1-25:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.CCC.2019.25

Abstract

We study the problem of approximating the commuting-operator value of a two-player non-local game. It is well-known that it is NP-complete to decide whether the classical value of a non-local 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 commuting-operator value of a game. Specifically, in the language of multi-prover 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 commuting-operator strategies) can increase without bound as the gap 1-s gets arbitrarily small.
Our results also extend naturally in two ways, to perfect zero-knowledge protocols, and to lower bounds on the complexity of computing the approximately-commuting value of a game. Thus we get lower bounds on the complexity class PZK-MIP^{co}_{delta}(2,1,1,s) of perfect zero-knowledge multi-prover proofs with approximately-commuting operator strategies, as the gap 1-s 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 = 1-1/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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum complexity theory
Keywords
  • Quantum complexity theory
  • Non-local game
  • Multi-prover interactive proof
  • Entanglement

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof Verification and the Hardness of Approximation Problems. JACM, 45(3):501-555, 1998. Google Scholar
  2. Sanjeev Arora and Shmuel Safra. Probabilistic Checking of Proofs: A New Characterization of NP. JACM, 45(1):70-122, 1998. Google Scholar
  3. Richard Cleve, Li Liu, and William Slofstra. Perfect commuting-operator strategies for linear system games. Journal of Mathematical Physics, 2016. to appear (https://arxiv.org/abs/1606.02278).
  4. Richard Cleve and Rajat Mittal. Characterization of Binary Constraint System Games. In Automata, Languages, and Programming, number 8572 in Lecture Notes in Computer Science, pages 320-331. Springer Berlin Heidelberg, 2014. URL: http://arxiv.org/abs/1209.2729.
  5. Matthew Coudron and Thomas Vidick. Interactive proofs with approximately commuting provers. In International Colloquium on Automata, Languages, and Programming (ICALP 2015), pages 355-366, 2015. Google Scholar
  6. Andrew C. Doherty, Yeong-Cherng Liang, Benjamin Toner, and Stephanie Wehner. The Quantum Moment Problem and Bounds on Entangled Multi-prover Games. In Proc. 23rd IEEE Conf. on Computational Complexity (CCC'08), pages 199-210. IEEE Computer Society, 2008. Google Scholar
  7. J. Fitzsimons, Z. Ji, T. Vidick, and H. Yuen. Quantum proof systems for iterated exponential time, and beyond. preprint, 2018. URL: http://arxiv.org/abs/1805.12166.
  8. SM Gersten. Isoperimetric and isodiametric functions of finite presentations. In Graham A. Niblo and Martin A. Roller, editors, Geometric group theory: Proceedings of the Symposium held in Sussex 1991, Volume 1, volume 181 of London Mathematical Society Lecture Note Series 181, pages 79-97. Cambridge University Press, 1993. Google Scholar
  9. T. Ito, H. Kobayashi, D. Preda, X. Sun, and A C.-C. Yao. Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-prover Interactive Proof Systems. In 23rd Annual IEEE Conference on Computational Complexity (CCC 2008), 2008. Google Scholar
  10. Tsuyoshi Ito and Thomas Vidick. A multi-prover interactive proof for NEXP sound against entangled provers. In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pages 243-252. IEEE, 2012. Google Scholar
  11. Zhengfeng Ji. Compression of Quantum Multi-prover Interactive Proofs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 289-302, New York, NY, USA, 2017. ACM. Google Scholar
  12. R.C. Lyndon and P.E. Schupp. Combinatorial Group Theory. Classics in Mathematics. Springer, 1977. Google Scholar
  13. Miguel Navascués, Stefano Pironio, and Antonio Acín. Bounding the Set of Quantum Correlations. Phys. Rev. Lett., 98:010401, January 2007. URL: https://doi.org/10.1103/PhysRevLett.98.010401.
  14. Miguel Navascués, Stefano Pironio, and Antonio Acín. A Convergent Hierarchy of Semidefinite Programs Characterizing the Set of Quantum Correlations. New Journal of Physics, 10(073013), 2008. URL: http://arxiv.org/abs/0803.4290v1.
  15. Narutaka Ozawa. Tsirelson’s problem and asymptotically commuting unitary matrices. Journal of Mathematical Physics, 54(3):032202, 2013. Google Scholar
  16. Mark V. Sapir, Jean-Camille Birget, and Eliyahu Rips. Isoperimetric and Isodiametric Functions of Groups. Annals of Mathematics, 156(2):345-466, 2002. Google Scholar
  17. William Slofstra. Tsirelson’s problem and an embedding theorem for groups arising from non-local games. CoRR, 2016. preprint. URL: http://arxiv.org/abs/1606.03140.
  18. William Slofstra and Thomas Vidick. Entanglement in non-local games and the hyperlinear profile of groups. Annales Henri Poincare, 19(10):2979-3005, 2018. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact