Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1309.0429 · Information Processing Letters

Constant-space quantum interactive proofs against multiple provers

Tomoyuki Yamakami

Published Jun 4, 2014• 6 citations
arXivHTMLPDF
DOI
10.1016/j.ipl.2014.05.012

Related papers

Quantum Interactive Oracle Proofs

Baocheng Sun, Thomas Vidick

We initiate the study of quantum Interactive Oracle Proofs (qIOPs), a generalization of both quantum Probabilistically Checkable Proofs and quantum Interactive Proofs, as well as a quantum analogue of classical Interactive Oracle Proofs. In the model of quantum Interactive Oracle Proofs, we allow multiple rounds of quantum interaction between the quantum prover and the quantum verifier, but the verifier has limited access to quantum resources. This includes both queries to the prover's messages and the complexity of the quantum circuits applied by the verifier. The question of whether QMA admits a quantum interactive oracle proof system is a relaxation of the quantum PCP Conjecture. We show the following two main constructions of qIOPs, both of which are unconditional: - We construct a qIOP for QMA in which the verifier shares polynomially many EPR pairs with the prover at the start of the protocol and reads only a constant number of qubits from the prover's messages. - We provide a stronger construction of qIOP for QMA in which the verifier not only reads a constant number of qubits but also operates on a constant number of qubits overall, including those in their private registers. However, in this stronger setting, the communication complexity becomes exponential. This leaves open the question of whether strong qIOPs for QMA, with polynomial communication complexity, exist. As a key component of our construction, we introduce a novel single prover many-qubits test, which may be of independent interest.

cs.CCCross-listedarXiv:2601.12874•Jan 20, 2026•0 citations

Quantum Interactive Proofs with Competing Provers

Gus Gutoski, John Watrous

arXiv:cs/0412102•Lecture notes in computer science•Jan 1, 2005•15 citations

Quantum Two Provers Interactive Proof Systems

Beverly Sackler, Alex Rapaport

•Jan 1, 2007•0 citations

PSPACE has constant-round quantum interactive proof systems

John Watrous

We introduce quantum interactive proof systems, which are interactive proof systems in which the prover and verifier may perform quantum computations and exchange quantum messages. It is proved that every language in PSPACE has a quantum interactive proof system that requires a total of only three messages to be sent between the prover and verifier and has exponentially small (one-sided) probability of error. It follows that quantum interactive proof systems are strictly more powerful than classical interactive proof systems in the constant-round case unless the polynomial time hierarchy collapses to the second level.

Annual Symposium on Foundations of Computer Science•Jan 20, 2003•54 citations

Parallelization, amplification, and exponential time simulation of quantum interactive proof systems

Alexei Kitaev, John Watrous

In this paper we consider quantum interactive proof systems, which are interactive proof systems in which the prover and verier may perform quantum computations and exchange quantum information. We prove that any polynomial-round quantum interactive proof system with two-sided bounded error can be parallelized to a quantum interactive proof system with exponentially small one-sided error in which the prover and verier exchange only 3 messages. This yields a simplied proof that PSPACE has 3-message quantum interactive proof systems. We also prove that any language having a quantum interactive proof system can be decided in deterministic exponential time, implying that single-prover quantum interactive proof systems are strictly less powerful than multiple-prover classical interactive proof systems unless EXP = NEXP. 1. INTRODUCTION Interactive proof systems were introduced by Babai [3] and Goldwasser, Micali, and Racko [17] in 1985. In the same year, Deutsch [10] gave the rst for...

ACM Symposium on Theory of Computing (STOC)•May 1, 2000•215 citations

Using Entanglement in Quantum Multi-Prover Interactive Proofs

Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto +1 more

Computational Complexity•Jun 1, 2009•38 citations
We initiate the study of quantum Interactive Oracle Proofs (qIOPs), a generalization of both quantum Probabilistically Checkable Proofs and quantum Interactive Proofs, as well as a quantum analogue of classical Interactive Oracle Proofs. In the model of quantum Interactive Oracle Proofs, we allow multiple rounds of quantum interaction between the quantum prover and the quantum verifier, but the verifier has limited access to quantum resources. This includes both queries to the prover's messages and the complexity of the quantum circuits applied by the verifier. The question of whether QMA admits a quantum interactive oracle proof system is a relaxation of the quantum PCP Conjecture. We show the following two main constructions of qIOPs, both of which are unconditional: - We construct a qIOP for QMA in which the verifier shares polynomially many EPR pairs with the prover at the start of the protocol and reads only a constant number of qubits from the prover's messages. - We provide a stronger construction of qIOP for QMA in which the verifier not only reads a constant number of qubits but also operates on a constant number of qubits overall, including those in their private registers. However, in this stronger setting, the communication complexity becomes exponential. This leaves open the question of whether strong qIOPs for QMA, with polynomial communication complexity, exist. As a key component of our construction, we introduce a novel single prover many-qubits test, which may be of independent interest.
We introduce quantum interactive proof systems, which are interactive proof systems in which the prover and verifier may perform quantum computations and exchange quantum messages. It is proved that every language in PSPACE has a quantum interactive proof system that requires a total of only three messages to be sent between the prover and verifier and has exponentially small (one-sided) probability of error. It follows that quantum interactive proof systems are strictly more powerful than classical interactive proof systems in the constant-round case unless the polynomial time hierarchy collapses to the second level.
In this paper we consider quantum interactive proof systems, which are interactive proof systems in which the prover and verier may perform quantum computations and exchange quantum information. We prove that any polynomial-round quantum interactive proof system with two-sided bounded error can be parallelized to a quantum interactive proof system with exponentially small one-sided error in which the prover and verier exchange only 3 messages. This yields a simplied proof that PSPACE has 3-message quantum interactive proof systems. We also prove that any language having a quantum interactive proof system can be decided in deterministic exponential time, implying that single-prover quantum interactive proof systems are strictly less powerful than multiple-prover classical interactive proof systems unless EXP = NEXP. 1. INTRODUCTION Interactive proof systems were introduced by Babai [3] and Goldwasser, Micali, and Racko [17] in 1985. In the same year, Deutsch [10] gave the rst for...