License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2020.87
URN: urn:nbn:de:0030-drops-124940
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12494/
Mousavi, Hamoon ;
Nezhadi, Seyed Sajjad ;
Yuen, Henry
On the Complexity of Zero Gap MIP*
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.
BibTeX - Entry
@InProceedings{mousavi_et_al:LIPIcs:2020:12494,
author = {Hamoon Mousavi and Seyed Sajjad Nezhadi and Henry Yuen},
title = {{On the Complexity of Zero Gap MIP*}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {87:1--87:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-138-2},
ISSN = {1868-8969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12494},
URN = {urn:nbn:de:0030-drops-124940},
doi = {10.4230/LIPIcs.ICALP.2020.87},
annote = {Keywords: Quantum Complexity, Multiprover Interactive Proofs, Computability Theory}
}
Keywords: |
|
Quantum Complexity, Multiprover Interactive Proofs, Computability Theory |
Collection: |
|
47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) |
Issue Date: |
|
2020 |
Date of publication: |
|
29.06.2020 |