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:1108.2098 · Chicago Journal of Theoretical Computer Science

Improved Soundness for QMA with Multiple Provers

Alessandro Chiesa, Michael A. Forbes

Published Jan 1, 2013• 20 citations
arXivHTMLPDF

Abstract

We present three contributions to the understanding of QMA with multiple provers:• We give a tight soundness analysis of the protocol of [Blier and Tapp, ICQNM '09], yielding a soundness gap Ω(N -2 ).Our improvement is achieved without the use of an instance with a constant soundness gap (i.e., without using a "PCP").• We give a tight soundness analysis of the protocol of [Chen and Drucker, ArXiV '10], thereby improving their result from a "monolithic" protocol where Θ( √ N) provers are needed in order to have any soundness gap, to a protocol with a smooth trade-off between the number of provers κ and a soundness gap Ω(κ 2 N -1 ), as long as κ ∈ Ω(log N). (And, when κ ∈ Θ( √ N), we recover the original parameters of Chen and Drucker.)• We make progress towards an open question of [Aaronson et al., ToC '09] about what kinds of NP-complete problems are amenable to "sublinear" multiple-prover QMA protocols, by observing that a large class of such examples can easily be derived from results already in the PCP literature -namely, at least the languages recognized by a non-deterministic RAMs in quasilinear time.

DOI
10.4086/cjtcs.2013.001

Related papers

Multi-Prover Quantum Merlin-Arthur Proof Systems with Small Gap

Attila Pereszlényi

This paper studies multiple-proof quantum Merlin-Arthur (QMA) proof systems in the setting when the completeness-soundness gap is small. Small means that we only lower-bound the gap with an inverse-exponential function of the input length, or with an even smaller function. Using the protocol of Blier and Tapp [arXiv:0709.0738], we show that in this case the proof system has the same expressive power as non-deterministic exponential time (NEXP). Since single-proof QMA proof systems, with the same bound on the gap, have expressive power at most exponential time (EXP), we get a separation between single and multi-prover proof systems in the 'small-gap setting', under the assumption that EXP is not equal to NEXP. This implies, among others, the nonexistence of certain operators called disentanglers (defined by Aaronson et al. [arXiv:0804.0802]), with good approximation parameters. We also show that in this setting the proof system has the same expressive power if we restrict the verifier to be able to perform only Bell-measurements, i.e., using a BellQMA verifier. This is not known to hold in the usual setting, when the gap is bounded by an inverse-polynomial function of the input length. To show this we use the protocol of Chen and Drucker [arXiv:1011.0716]. The only caveat here is that we need at least a linear amount of proofs to achieve the power of NEXP, while in the previous setting two proofs were enough. We also study the case when the proof-lengths are only logarithmic in the input length and observe that in some cases the expressive power decreases. However, we show that it doesn't decrease further if we make the proof lengths to be even shorter.

arXiv:1205.2761•May 12, 2012•27 citations

On QMA protocols with two short quantum proofs

Francois Le Gall, Shota Nakagawa, Harumichi Nishimura

This paper gives a QMA (Quantum Merlin-Arthur) protocol for 3-SAT with two logarithmic-size quantum proofs (that are not entangled with each other) such that the gap between the completeness and the soundness is $\Omega(\frac{1}{n\polylog{n}})$. This improves the best completeness/soundness gaps known for NP-complete problems in this setting.

arXiv:1108.4306•Quantum Information and Computation•Jul 1, 2012•36 citations

Quantum Multi Prover Interactive Proofs with Communicating Provers

Michael Ben-Or, Avinatan Hassidim, Haran Pilpel

Multi Prover Interactive Proof systems (MIPs)were first presented in a cryptographic context, but ever since they were used in various fields. Understanding the power of MIPs in the quantum context raises many open problems, as there are several interesting models to consider. For example, one can study the question when the provers share entanglement or not, and the communication between the verifier and the provers is quantum or classical. While there are several partial results on the subject, so far no one presented an efficient scheme for recognizing NEXP (or NP with logarithmic communication), except for [KM03], in the case there is no entanglement (and of course no communication between the provers). We introduce another variant of Quantum MIP, where the provers do not share entanglement, the communication between the verifier and the provers is quantum, but the provers are unlimited in the classical communication between them. At first, this model may seem very weak, as provers who exchange information seem to be equivalent in power to a simple prover. This in fact is not the case - we show that any language in NEXP can be recognized in this model efficiently, with just two provers and two rounds of communication, with a constant completeness-soundness gap.

arXiv:0806.3982•Jun 24, 2008•8 citations

Short Multi-Prover Quantum Proofs for SAT without Entangled Measurements

Jing Chen, Andrew Drucker

BellQMA protocols are a subclass of multi-prover quantum Merlin-Arthur protocols in which the verifier is restricted to perform nonadaptive,unentangled measurements on the quantum states received from each Merlin. In this paper, we prove that m-clause 3-SAT instances have BellQMA proofs of satisfiability with constant soundness gap, in which O(sqrt(m)polylog(m)) Merlins each send O(log m) qubits to Arthur. Our result answers a question of Aaronson et al., who gave a protocol with similar parameters that used entangled measurements; the analysis of our protocol is significantly simpler than that of Aaronson et al. Our result also complements recent work of Brandao, Christandl, and Yard, who showed upper bounds on the power of multiprover quantum proofs with unentangled but adaptive (LOCC) measurements.

arXiv:1011.0716•Nov 2, 2010•43 citations

2011年度冬のLAシンポジウム On QMA Protocols with Two Short Quantum Proofs (アルゴリズムと計算理論の新展開 : RIMS研究集会報告集)

François Le Gall, Shota Nakagawa, Harumichi Nishimura

This paper gives $a$ .QMA (Quantum Merlin-Arthur) protocol for 3-SAT with two logarith- mic-size quantum proofs (that are not entangled with each other) such that the gap between the completeness and the soundness is $\Omega(\frac{1}{npoly\log(n)})$ .This improves the best completeness/soundness gaps known for NP-complete problems in this setting.

数理解析研究所講究録•Jun 1, 2012•1 citation

Multi-Prover Interactive Proof Systems with Leakage

Vahid R. Asadi, Atsuya Hasegawa, François Le Gall

It is known that there exist multi-prover interactive protocols ($\mathsf{MIP}$ protocols) for the complexity class $\mathsf{NEXP}$, succinct $\mathsf{MIP}$ protocols for $\mathsf{NP}$ and multi-prover interactive protocols with shared entanglement ($\mathsf{MIP}^\ast$ protocols) for $\mathsf{RE}$. This extraordinary power of multi-prover interactive proof systems comes from the assumption that provers do not communicate with each other during the protocols. If they are allowed to communicate freely, the setting is the same as in the single-prover case, and the computational power of the system becomes significantly weaker. In this paper, we investigate for the first time the setting where communication (i.e., leakage of information) between provers is allowed but bounded. We introduce two techniques to approach this question and show that multi-prover interactive proof systems are robust against some amount of leakage. Our first technique is based on parallel repetition theorems. We apply it to show that for any polynomial $p$, we can construct two-prover one-round $\mathsf{MIP}$ and $\mathsf{MIP}^\ast$ protocols for $\mathsf{NEXP}$ and $\mathsf{RE}$, respectively, that are robust against $p(n)$ bits of leakage. We further derive our second technique to convert any low-soundness PCP construction to a two-prover one-round $\mathsf{MIP}$ protocol for $\mathsf{NP}$ robust against leakage. We also discuss the relation between robustness against leakage in multi-prover interactive proof systems and the Sliding Scale Conjecture in the PCP literature.

quant-pharXiv:2605.09872•Leibniz international proceedings in informatics•May 12, 2026•0 citations
We present three contributions to the understanding of QMA with multiple provers:• We give a tight soundness analysis of the protocol of [Blier and Tapp, ICQNM '09], yielding a soundness gap Ω(N -2 ).Our improvement is achieved without the use of an instance with a constant soundness gap (i.e., without using a "PCP").• We give a tight soundness analysis of the protocol of [Chen and Drucker, ArXiV '10], thereby improving their result from a "monolithic" protocol where Θ( √ N) provers are needed in order to have any soundness gap, to a protocol with a smooth trade-off between the number of provers κ and a soundness gap Ω(κ 2 N -1 ), as long as κ ∈ Ω(log N). (And, when κ ∈ Θ( √ N), we recover the original parameters of Chen and Drucker.)• We make progress towards an open question of [Aaronson et al., ToC '09] about what kinds of NP-complete problems are amenable to "sublinear" multiple-prover QMA protocols, by observing that a large class of such examples can easily be derived from results already in the PCP literature -namely, at least the languages recognized by a non-deterministic RAMs in quasilinear time.
This paper studies multiple-proof quantum Merlin-Arthur (QMA) proof systems in the setting when the completeness-soundness gap is small. Small means that we only lower-bound the gap with an inverse-exponential function of the input length, or with an even smaller function. Using the protocol of Blier and Tapp [arXiv:0709.0738], we show that in this case the proof system has the same expressive power as non-deterministic exponential time (NEXP). Since single-proof QMA proof systems, with the same bound on the gap, have expressive power at most exponential time (EXP), we get a separation between single and multi-prover proof systems in the 'small-gap setting', under the assumption that EXP is not equal to NEXP. This implies, among others, the nonexistence of certain operators called disentanglers (defined by Aaronson et al. [arXiv:0804.0802]), with good approximation parameters. We also show that in this setting the proof system has the same expressive power if we restrict the verifier to be able to perform only Bell-measurements, i.e., using a BellQMA verifier. This is not known to hold in the usual setting, when the gap is bounded by an inverse-polynomial function of the input length. To show this we use the protocol of Chen and Drucker [arXiv:1011.0716]. The only caveat here is that we need at least a linear amount of proofs to achieve the power of NEXP, while in the previous setting two proofs were enough. We also study the case when the proof-lengths are only logarithmic in the input length and observe that in some cases the expressive power decreases. However, we show that it doesn't decrease further if we make the proof lengths to be even shorter.
Multi Prover Interactive Proof systems (MIPs)were first presented in a cryptographic context, but ever since they were used in various fields. Understanding the power of MIPs in the quantum context raises many open problems, as there are several interesting models to consider. For example, one can study the question when the provers share entanglement or not, and the communication between the verifier and the provers is quantum or classical. While there are several partial results on the subject, so far no one presented an efficient scheme for recognizing NEXP (or NP with logarithmic communication), except for [KM03], in the case there is no entanglement (and of course no communication between the provers). We introduce another variant of Quantum MIP, where the provers do not share entanglement, the communication between the verifier and the provers is quantum, but the provers are unlimited in the classical communication between them. At first, this model may seem very weak, as provers who exchange information seem to be equivalent in power to a simple prover. This in fact is not the case - we show that any language in NEXP can be recognized in this model efficiently, with just two provers and two rounds of communication, with a constant completeness-soundness gap.
BellQMA protocols are a subclass of multi-prover quantum Merlin-Arthur protocols in which the verifier is restricted to perform nonadaptive,unentangled measurements on the quantum states received from each Merlin. In this paper, we prove that m-clause 3-SAT instances have BellQMA proofs of satisfiability with constant soundness gap, in which O(sqrt(m)polylog(m)) Merlins each send O(log m) qubits to Arthur. Our result answers a question of Aaronson et al., who gave a protocol with similar parameters that used entangled measurements; the analysis of our protocol is significantly simpler than that of Aaronson et al. Our result also complements recent work of Brandao, Christandl, and Yard, who showed upper bounds on the power of multiprover quantum proofs with unentangled but adaptive (LOCC) measurements.
This paper gives aaa .QMA (Quantum Merlin-Arthur) protocol for 3-SAT with two logarith- mic-size quantum proofs (that are not entangled with each other) such that the gap between the completeness and the soundness is Ω(1npolylog⁡(n))\Omega(\frac{1}{npoly\log(n)})Ω(npolylog(n)1​) .This improves the best completeness/soundness gaps known for NP-complete problems in this setting.
It is known that there exist multi-prover interactive protocols (MIP\mathsf{MIP}MIP protocols) for the complexity class NEXP\mathsf{NEXP}NEXP, succinct MIP\mathsf{MIP}MIP protocols for NP\mathsf{NP}NP and multi-prover interactive protocols with shared entanglement (MIP∗\mathsf{MIP}^\astMIP∗ protocols) for RE\mathsf{RE}RE. This extraordinary power of multi-prover interactive proof systems comes from the assumption that provers do not communicate with each other during the protocols. If they are allowed to communicate freely, the setting is the same as in the single-prover case, and the computational power of the system becomes significantly weaker. In this paper, we investigate for the first time the setting where communication (i.e., leakage of information) between provers is allowed but bounded. We introduce two techniques to approach this question and show that multi-prover interactive proof systems are robust against some amount of leakage. Our first technique is based on parallel repetition theorems. We apply it to show that for any polynomial ppp, we can construct two-prover one-round MIP\mathsf{MIP}MIP and MIP∗\mathsf{MIP}^\astMIP∗ protocols for NEXP\mathsf{NEXP}NEXP and RE\mathsf{RE}RE, respectively, that are robust against p(n)p(n)p(n) bits of leakage. We further derive our second technique to convert any low-soundness PCP construction to a two-prover one-round MIP\mathsf{MIP}MIP protocol for NP\mathsf{NP}NP robust against leakage. We also discuss the relation between robustness against leakage in multi-prover interactive proof systems and the Sliding Scale Conjecture in the PCP literature.