2 Search Results for "Slofstra, William"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.87
On the Complexity of Zero Gap MIP*

Authors: Hamoon Mousavi, Seyed Sajjad Nezhadi, and Henry Yuen

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{mousavi_et_al:LIPIcs.ICALP.2020.87,
  author =	{Mousavi, Hamoon and Nezhadi, Seyed Sajjad and Yuen, Henry},
  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 =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.87},
  URN =		{urn:nbn:de:0030-drops-124940},
  doi =		{10.4230/LIPIcs.ICALP.2020.87},
  annote =	{Keywords: Quantum Complexity, Multiprover Interactive Proofs, Computability Theory}
}
Document
DOI: 10.4230/LIPIcs.CCC.2019.25
Complexity Lower Bounds for Computing the Approximately-Commuting Operator Value of Non-Local Games to High Precision

Authors: Matthew Coudron and William Slofstra

Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{coudron_et_al:LIPIcs.CCC.2019.25,
  author =	{Coudron, Matthew and Slofstra, William},
  title =	{{Complexity Lower Bounds for Computing the Approximately-Commuting Operator Value of Non-Local Games to High Precision}},
  booktitle =	{34th Computational Complexity Conference (CCC 2019)},
  pages =	{25:1--25:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-116-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{137},
  editor =	{Shpilka, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.25},
  URN =		{urn:nbn:de:0030-drops-108478},
  doi =		{10.4230/LIPIcs.CCC.2019.25},
  annote =	{Keywords: Quantum complexity theory, Non-local game, Multi-prover interactive proof, Entanglement}
}
  • Refine by Author
  • 1 Coudron, Matthew
  • 1 Mousavi, Hamoon
  • 1 Nezhadi, Seyed Sajjad
  • 1 Slofstra, William
  • 1 Yuen, Henry

  • Refine by Classification
  • 2 Theory of computation → Quantum complexity theory
  • 1 Theory of computation → Computability
  • 1 Theory of computation → Interactive proof systems

  • Refine by Keyword
  • 1 Computability Theory
  • 1 Entanglement
  • 1 Multi-prover interactive proof
  • 1 Multiprover Interactive Proofs
  • 1 Non-local game
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2019
  • 1 2020

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 Imprint Privacy Contact