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• 15 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•13 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•25 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•20 citations

On QMA Protocols with Two Short Quantum Proofs (New Trends in Algorithms and Theory of Computation)

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

The Power of Unentanglement

Scott Aaronson, Salman Beigi, Andrew Drucker +2 more

The class QMA(k), introduced by Kobayashi et al., consists of all languages that can be verified using k unentangled quantum proofs. Many of the simplest questions about this class have remained embarrassingly open: for example, can we give any evidence that k quantum proofs are more powerful than one? Can we show any upper bound on QMA(k), besides the trivial NEXP? Does QMA(k)=QMA(2) for kges2? Can QMA(k) protocols be amplified to exponentially small error? In this paper, we make progress on all of the above questions. *We give a protocol by which a verifier can be convinced that a 3SAT formula of size n is satisfiable, with constant soundness, given O tilde(radicn) unentangled quantum witnesses with O(log n) qubits each. Our protocol relies on Dinur's version of the PCP Theorem and is inherently non-relativizing. *We show that assuming the famous Additivity Conjecture from quantum information theory, any QMA(2) protocol can be amplified to exponentially small error, and QMA(k)=QMA(2) for all kges=2. *We give evidence that QMA(2) sube PSPACE, by showing that this would follow from "strong amplification" of QMA(2) protocols. *We prove the nonexistence of "perfect disentanglers" for simulating multiple Merlins with one.

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2008•27 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.
The class QMA(k), introduced by Kobayashi et al., consists of all languages that can be verified using k unentangled quantum proofs. Many of the simplest questions about this class have remained embarrassingly open: for example, can we give any evidence that k quantum proofs are more powerful than one? Can we show any upper bound on QMA(k), besides the trivial NEXP? Does QMA(k)=QMA(2) for kges2? Can QMA(k) protocols be amplified to exponentially small error? In this paper, we make progress on all of the above questions. *We give a protocol by which a verifier can be convinced that a 3SAT formula of size n is satisfiable, with constant soundness, given O tilde(radicn) unentangled quantum witnesses with O(log n) qubits each. Our protocol relies on Dinur's version of the PCP Theorem and is inherently non-relativizing. *We show that assuming the famous Additivity Conjecture from quantum information theory, any QMA(2) protocol can be amplified to exponentially small error, and QMA(k)=QMA(2) for all kges=2. *We give evidence that QMA(2) sube PSPACE, by showing that this would follow from "strong amplification" of QMA(2) protocols. *We prove the nonexistence of "perfect disentanglers" for simulating multiple Merlins with one.