LIPIcs.ICALP.2020.87.pdf
- Filesize: 0.52 MB
- 12 pages
Document
On the Complexity of Zero Gap MIP*
Authors
-
Part of:
Volume:
47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-06-29
File
Document Identifiers
Acknowledgements
We thank Matt Coudron, Thomas Vidick, and especially William Slofstra for numerous helpful discussions. We also thank the reviewers of ICALP 2020 for suggestions to improve the presentation.
Cite AsGet BibTex
Hamoon Mousavi, Seyed Sajjad Nezhadi, and Henry Yuen. On the Complexity of Zero Gap MIP*. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 87:1-87:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.87
https://doi.org/10.4230/LIPIcs.ICALP.2020.87
Abstract
The class MIP^* is the set of languages decidable by multiprover interactive proofs with quantum entangled provers. It was recently shown by Ji, Natarajan, Vidick, Wright and Yuen that MIP^* is equal to RE, the set of recursively enumerable languages. In particular this shows that the complexity of approximating the quantum value of a non-local game G is equivalent to the complexity of the Halting problem.
In this paper we investigate the complexity of deciding whether the quantum value of a non-local game G is exactly 1. This problem corresponds to a complexity class that we call zero gap MIP^*, denoted by MIP₀^*, where there is no promise gap between the verifier’s acceptance probabilities in the YES and NO cases. We prove that MIP₀^* extends beyond the first level of the arithmetical hierarchy (which includes RE and its complement coRE), and in fact is equal to Π₂⁰, the class of languages that can be decided by quantified formulas of the form ∀ y ∃ z R(x,y,z).
Combined with the previously known result that MIP₀^{co} (the commuting operator variant of MIP₀^*) is equal to coRE, our result further highlights the fascinating connection between various models of quantum multiprover interactive proofs and different classes in computability theory.
Subject Classification
ACM Subject Classification
- Theory of computation → Interactive proof systems
- Theory of computation → Computability
- Theory of computation → Quantum complexity theory
Keywords
- Quantum Complexity
- Multiprover Interactive Proofs
- Computability Theory
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Michael Ben-Or, Shafi Goldwasser, Joe Kilian, and Avi Wigderson. Multi-prover interactive proofs: how to remove intractability assumptions. In Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 113-131, 1988.
-
Richard Cleve, Daniel Gottesman, and Hoi-Kwong Lo. How to share a quantum secret. Physical Review Letters, 83(3):648, 1999.
- Matthew Coudron and William Slofstra. Complexity lower bounds for computing the approximately-commuting operator value of non-local games to high precision. arXiv preprint, 2019. URL: http://arxiv.org/abs/1905.11635.
-
Andrew C Doherty, Yeong-Cherng Liang, Ben Toner, and Stephanie Wehner. The quantum moment problem and bounds on entangled multi-prover games. In 2008 23rd Annual IEEE Conference on Computational Complexity, pages 199-210. IEEE, 2008.
- Joseph Fitzsimons, Zhengfeng Ji, Thomas Vidick, and Henry Yuen. Quantum proof systems for iterated exponential time, and beyond. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 473–480, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3313276.3316343.
-
Tobias Fritz. Tsirelson’s problem and kirchberg’s conjecture. Reviews in Mathematical Physics, 24(05):1250012, 2012.
-
Isaac Goldbring. Enforceable operator algebras. Journal of the Institute of Mathematics of Jussieu, pages 1-33, 2017.
- Isaac Goldbring and Bradd Hart. A computability-theoretic reformulation of the connes embedding problem. arXiv preprint, 2013. URL: http://arxiv.org/abs/1308.2638.
- Gus Gutoski and John Watrous. Toward a general theory of quantum games. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC ’07, page 565–574, New York, NY, USA, 2007. Association for Computing Machinery. URL: https://doi.org/10.1145/1250790.1250873.
-
Zhengfeng Ji. Compression of quantum multi-prover interactive proofs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 289-302, 2017.
- Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP^* = RE. arXiv preprint, 2020. URL: http://arxiv.org/abs/2001.04383.
-
Marius Junge, Miguel Navascues, Carlos Palazuelos, David Perez-Garcia, Volkher B Scholz, and Reinhard F Werner. Connes' embedding problem and tsirelson’s problem. Journal of Mathematical Physics, 52(1):012102, 2011.
-
Anand Natarajan and John Wright. NEEXP ⊆ MIP^*. In IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 510-518, 2019.
-
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(7):073013, 2008.
-
Narutaka Ozawa. About the connes embedding conjecture, algebraic approaches. Jpn. J. Math., 8:147-183, 2013.
-
William Slofstra. The set of quantum correlations is not closed. In Forum of Mathematics, Pi, volume 7. Cambridge University Press, 2019.