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 Proofs with Competing Provers

Gus Gutoski, John Watrous

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

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•1 citation

Quantum Two Provers Interactive Proof Systems

Beverly Sackler, Alex Rapaport

•Jan 1, 2007•0 citations

Using Entanglement in Quantum Multi-Prover Interactive Proofs

Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto +1 more

arXiv:0711.3715•Computational Complexity•Jun 1, 2009•48 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•53 citations

On quantum interactive proofs with a laconic prover

Zihan Hu, Yupan Liu

Interactive proof systems with a laconic prover, studied by Goldreich, Vadhan, and Wigderson (CC, 2002), capture problems verifiable with logarithmic prover communication in the classical setting. For two-message quantum analogs, even a single-bit prover response contains quantum statistical zero-knowledge ($\sf QSZK$), introduced by Watrous (FOCS 2002). However, restricting the verifier's question to classical public coins collapses the corresponding class to $\sf BQP$, as shown by Beigi, Shor, and Watrous (ToC, 2011). We further study two-message quantum interactive proof systems with a laconic prover. To this end, we introduce the class ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$, where $\ell$ is the length of the prover's response, and establish: 1. A natural complete characterization of ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$ by Multi-State Distinguishability. In particular, Quantum State Distinguishability (QSD) is ${\sf QIP}_{\rm bit}$-complete. Since QSD is $\sf QSZK$-hard, our result places ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$, for $\ell\geq 2$, in a landscape "just above" $\sf QSZK$. 2. Easy regimes for ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$ collapsing to $\sf QSZK$. We prove that QSD$[a,b]$ (and thus ${\sf QIP}_{\rm bit}[a,b]$) is in $\sf QSZK$ when $a(n)-b(n)\geq 1/O(\log n)$, and combine this with an answer compression from ${\sf QIP}_{\ell\text{-}{\rm bit}}[2,c,s]$ to ${\sf QIP}_{\rm bit}$ to obtain another easy regime when $2c>(1+2^{\ell/2})s$. Remarkably, our improved polarization applies to SD and $\sf SZK$, resolving an open problem in Sahai and Vadhan (JACM, 2003). 3. Quantum public coins also make the interaction useless: ${\sf qc}\text{-}{\sf QAM}[O(\sqrt{\log{n}})]$ with constant gap is in $\sf BQP$, where ${\sf qc}\text{-}{\sf QAM}[\ell]$ is a subclass of ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$ in which the verifier's question is exactly halves of EPR pairs.

quant-pharXiv:2609.39495•Oct 1, 2026•0 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.
Interactive proof systems with a laconic prover, studied by Goldreich, Vadhan, and Wigderson (CC, 2002), capture problems verifiable with logarithmic prover communication in the classical setting. For two-message quantum analogs, even a single-bit prover response contains quantum statistical zero-knowledge (QSZK\sf QSZKQSZK), introduced by Watrous (FOCS 2002). However, restricting the verifier's question to classical public coins collapses the corresponding class to BQP\sf BQPBQP, as shown by Beigi, Shor, and Watrous (ToC, 2011). We further study two-message quantum interactive proof systems with a laconic prover. To this end, we introduce the class QIPℓ-bit(2){\sf QIP}_{\ell\text{-}{\rm bit}}(2)QIPℓ-bit​(2), where ℓ\ellℓ is the length of the prover's response, and establish: 1. A natural complete characterization of QIPℓ-bit(2){\sf QIP}_{\ell\text{-}{\rm bit}}(2)QIPℓ-bit​(2) by Multi-State Distinguishability. In particular, Quantum State Distinguishability (QSD) is QIPbit{\sf QIP}_{\rm bit}QIPbit​-complete. Since QSD is QSZK\sf QSZKQSZK-hard, our result places QIPℓ-bit(2){\sf QIP}_{\ell\text{-}{\rm bit}}(2)QIPℓ-bit​(2), for ℓ≥2\ell\geq 2ℓ≥2, in a landscape "just above" QSZK\sf QSZKQSZK. 2. Easy regimes for QIPℓ-bit(2){\sf QIP}_{\ell\text{-}{\rm bit}}(2)QIPℓ-bit​(2) collapsing to QSZK\sf QSZKQSZK. We prove that QSD[a,b][a,b][a,b] (and thus QIPbit[a,b]{\sf QIP}_{\rm bit}[a,b]QIPbit​[a,b]) is in QSZK\sf QSZKQSZK when a(n)−b(n)≥1/O(log⁡n)a(n)-b(n)\geq 1/O(\log n)a(n)−b(n)≥1/O(logn), and combine this with an answer compression from QIPℓ-bit[2,c,s]{\sf QIP}_{\ell\text{-}{\rm bit}}[2,c,s]QIPℓ-bit​[2,c,s] to QIPbit{\sf QIP}_{\rm bit}QIPbit​ to obtain another easy regime when 2c>(1+2ℓ/2)s2c>(1+2^{\ell/2})s2c>(1+2ℓ/2)s. Remarkably, our improved polarization applies to SD and SZK\sf SZKSZK, resolving an open problem in Sahai and Vadhan (JACM, 2003). 3. Quantum public coins also make the interaction useless: qc-QAM[O(log⁡n)]{\sf qc}\text{-}{\sf QAM}[O(\sqrt{\log{n}})]qc-QAM[O(logn​)] with constant gap is in BQP\sf BQPBQP, where qc-QAM[ℓ]{\sf qc}\text{-}{\sf QAM}[\ell]qc-QAM[ℓ] is a subclass of QIPℓ-bit(2){\sf QIP}_{\ell\text{-}{\rm bit}}(2)QIPℓ-bit​(2) in which the verifier's question is exactly halves of EPR pairs.