2026-07-24T03:13:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12494 2024-03-06T10:50:17Z ddc:004 open_access

On the Complexity of Zero Gap MIP* Mousavi, Hamoon Nezhadi, Seyed Sajjad Yuen, Henry Quantum Complexity Multiprover Interactive Proofs Computability Theory 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hamoon Mousavi and Seyed Sajjad Nezhadi and Henry Yuen 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.87 urn:nbn:de:0030-drops-124940 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.87 eng https://creativecommons.org/licenses/by/3.0/legalcode