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

NP vs QMA_log(2)

Salman Beigi

Published Oct 28, 2008• 11 citations
OpenAlex

Abstract

Although it is believed unlikely that $\NP$-hard problems admit efficient quantum algorithms, it has been shown that a quantum verifier can solve $\NP$-complete problems given a short quantum proof; more precisely, $\NP\subseteq \QMA_{\log}(2)$ where $\QMA_{\log}(2)$ denotes the class of quantum Merlin-Arthur games in which there are two unentangled provers who send two logarithmic size quantum witnesses to the verifier. The inclusion $\NP\subseteq \QMA_{\log}(2)$ has been proved by Blier and Tapp by stating a quantum Merlin-Arthur protocol for 3-coloring with perfect completeness and gap $\frac{1}{24n^6}$. Moreover, Aaronson {\it et al.} have shown the above inclusion with a constant gap by considering $\widetilde{O}(\sqrt{n})$ witnesses of logarithmic size. However, we still do not know if $\QMA_{\log}(2)$ with a constant gap contains $\NP$. In this paper, we show that 3-SAT admits a $\QMA_{\log}(2)$ protocol with the gap $\frac{1}{n^{3+\epsilon}}$ for every constant $\epsilon>0$.

Related papers

NP vs QMA_\log(2)

Salman Beigi

Although it is believed unlikely that $\NP$-hard problems admit efficient quantum algorithms, it has been shown that a quantum verifier can solve NP-complete problems given a "short" quantum proof; more precisely, NP\subseteq QMA_{\log}(2) where QMA_{\log}(2) denotes the class of quantum Merlin-Arthur games in which there are two unentangled provers who send two logarithmic size quantum witnesses to the verifier. The inclusion NP\subseteq QMA_{\log}(2) has been proved by Blier and Tapp by stating a quantum Merlin-Arthur protocol for 3-coloring with perfect completeness and gap 1/24n^6. Moreover, Aaronson et al. have shown the above inclusion with a constant gap by considering $\widetilde{O}(\sqrt{n})$ witnesses of logarithmic size. However, we still do not know if QMA_{\log}(2) with a constant gap contains NP. In this paper, we show that 3-SAT admits a QMA_{\log}(2) protocol with the gap 1/n^{3+\epsilon}} for every constant \epsilon>0.

arXiv:0810.5109•Quantum Information and Computation•Jan 1, 2010•36 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

On the Satisfiability of Quantum Circuits of Small Treewidth

Mateus de Oliveira Oliveira

It has been known for almost three decades that many $\mathrm{NP}$-hard optimization problems can be solved in polynomial time when restricted to structures of constant treewidth. In this work we provide the first extension of such results to the quantum setting. We show that given a quantum circuit $C$ with $n$ uninitialized inputs, $\mathit{poly}(n)$ gates, and treewidth $t$, one can compute in time $(\frac{n}{\delta})^{\exp(O(t))}$ a classical assignment $y\in \{0,1\}^n$ that maximizes the acceptance probability of $C$ up to a $\delta$ additive factor. In particular, our algorithm runs in polynomial time if $t$ is constant and $1/poly(n) < \delta < 1$. For unrestricted values of $t$, this problem is known to be complete for the complexity class $\mathrm{QCMA}$, a quantum generalization of MA. In contrast, we show that the same problem is $\mathrm{NP}$-complete if $t=O(\log n)$ even when $\delta$ is constant. On the other hand, we show that given a $n$-input quantum circuit $C$ of treewidth $t=O(\log n)$, and a constant $\delta<1/2$, it is $\mathrm{QMA}$-complete to determine whether there exists a quantum state $\mid\!\varphi\rangle \in (\mathbb{C}^d)^{\otimes n}$ such that the acceptance probability of $C\mid\!\varphi\rangle$ is greater than $1-\delta$, or whether for every such state $\mid\!\varphi\rangle$, the acceptance probability of $C\mid\!\varphi\rangle$ is less than $\delta$. As a consequence, under the widely believed assumption that $\mathrm{QMA} \neq \mathrm{NP}$, we have that quantum witnesses are strictly more powerful than classical witnesses with respect to Merlin-Arthur protocols in which the verifier is a quantum circuit of logarithmic treewidth.

•Apr 22, 2014•0 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

QMA(2) with Limited Shared Entanglement

Alex Della Schiava, Ranitha Mataraarachchi

In $\mathsf{QMA}(2)$, two computationally unbounded provers submit unentangled quantum witnesses to a polynomial-time quantum verifier. We ask whether allowing limited shared entanglement between the two provers changes the power of $\mathsf{QMA}(2)$. To this end, we formalize $\mathsf{QMA}(2;h)$, a variant in which the provers initially share $h$ EPR pairs, as suggested by Aaronson, Beigi, Drucker, Fefferman, and Shor (ToC~2009). We show that polynomially many shared EPR pairs give the provers no cheating advantage: $\mathsf{QMA}(2)\subseteq\mathsf{QMA}(2;h)$ for $h=\operatorname{poly}(n)$. For logarithmically many pairs, the power of $\mathsf{QMA}(2)$ remains unchanged, strengthening this inclusion to $\mathsf{QMA}(2)=\mathsf{QMA}(2;h)$ for $h=O(\log n)$. Finally, we introduce a variant that also allows classical communication between the provers when preparing the witnesses. This setting is particularly revealing for logarithmic-size witnesses: assuming $\mathsf{NP}\nsubseteq\mathsf{BQP}$, we show that superlogarithmically many shared EPR pairs strictly reduce the model's computational power.

quant-pharXiv:2609.39668•Oct 1, 2026•0 citations

All languages in NP have very short quantum proofs

Hugue Blier, Alain Tapp

In this note we show that all languages in NP have very short (logarithmic size) quantum proofs which can be verified provided that two unentangled copies are given. We thus introduce a new complexity class QMAlog(2) and show that NP ⊆ QMAlog(2). This gives a new perspective when compared to the previously known result QMAlog = BQP. 1

•Sep 5, 2007•10 citations
Although it is believed unlikely that \NP\NP\NP-hard problems admit efficient quantum algorithms, it has been shown that a quantum verifier can solve \NP\NP\NP-complete problems given a short quantum proof; more precisely, \NP⊆\QMAlog⁡(2)\NP\subseteq \QMA_{\log}(2)\NP⊆\QMAlog​(2) where \QMAlog⁡(2)\QMA_{\log}(2)\QMAlog​(2) denotes the class of quantum Merlin-Arthur games in which there are two unentangled provers who send two logarithmic size quantum witnesses to the verifier. The inclusion \NP⊆\QMAlog⁡(2)\NP\subseteq \QMA_{\log}(2)\NP⊆\QMAlog​(2) has been proved by Blier and Tapp by stating a quantum Merlin-Arthur protocol for 3-coloring with perfect completeness and gap 124n6\frac{1}{24n^6}24n61​. Moreover, Aaronson {\it et al.} have shown the above inclusion with a constant gap by considering O~(n)\widetilde{O}(\sqrt{n})O(n​) witnesses of logarithmic size. However, we still do not know if \QMAlog⁡(2)\QMA_{\log}(2)\QMAlog​(2) with a constant gap contains \NP\NP\NP. In this paper, we show that 3-SAT admits a \QMAlog⁡(2)\QMA_{\log}(2)\QMAlog​(2) protocol with the gap 1n3+ϵ\frac{1}{n^{3+\epsilon}}n3+ϵ1​ for every constant ϵ>0\epsilon>0ϵ>0.
Although it is believed unlikely that $\NP$-hard problems admit efficient quantum algorithms, it has been shown that a quantum verifier can solve NP-complete problems given a "short" quantum proof; more precisely, NP\subseteq QMA_{\log}(2) where QMA_{\log}(2) denotes the class of quantum Merlin-Arthur games in which there are two unentangled provers who send two logarithmic size quantum witnesses to the verifier. The inclusion NP\subseteq QMA_{\log}(2) has been proved by Blier and Tapp by stating a quantum Merlin-Arthur protocol for 3-coloring with perfect completeness and gap 1/24n^6. Moreover, Aaronson et al. have shown the above inclusion with a constant gap by considering O~(n)\widetilde{O}(\sqrt{n})O(n​) witnesses of logarithmic size. However, we still do not know if QMA_{\log}(2) with a constant gap contains NP. In this paper, we show that 3-SAT admits a QMA_{\log}(2) protocol with the gap 1/n^{3+\epsilon}} for every constant \epsilon>0.
It has been known for almost three decades that many NP\mathrm{NP}NP-hard optimization problems can be solved in polynomial time when restricted to structures of constant treewidth. In this work we provide the first extension of such results to the quantum setting. We show that given a quantum circuit CCC with nnn uninitialized inputs, poly(n)\mathit{poly}(n)poly(n) gates, and treewidth ttt, one can compute in time (nδ)exp⁡(O(t))(\frac{n}{\delta})^{\exp(O(t))}(δn​)exp(O(t)) a classical assignment y∈{0,1}ny\in \{0,1\}^ny∈{0,1}n that maximizes the acceptance probability of CCC up to a δ\deltaδ additive factor. In particular, our algorithm runs in polynomial time if ttt is constant and 1/poly(n)<δ<11/poly(n) < \delta < 11/poly(n)<δ<1. For unrestricted values of ttt, this problem is known to be complete for the complexity class QCMA\mathrm{QCMA}QCMA, a quantum generalization of MA. In contrast, we show that the same problem is NP\mathrm{NP}NP-complete if t=O(log⁡n)t=O(\log n)t=O(logn) even when δ\deltaδ is constant. On the other hand, we show that given a nnn-input quantum circuit CCC of treewidth t=O(log⁡n)t=O(\log n)t=O(logn), and a constant δ<1/2\delta<1/2δ<1/2, it is QMA\mathrm{QMA}QMA-complete to determine whether there exists a quantum state ∣ ⁣φ⟩∈(Cd)⊗n\mid\!\varphi\rangle \in (\mathbb{C}^d)^{\otimes n}∣φ⟩∈(Cd)⊗n such that the acceptance probability of C∣ ⁣φ⟩C\mid\!\varphi\rangleC∣φ⟩ is greater than 1−δ1-\delta1−δ, or whether for every such state ∣ ⁣φ⟩\mid\!\varphi\rangle∣φ⟩, the acceptance probability of C∣ ⁣φ⟩C\mid\!\varphi\rangleC∣φ⟩ is less than δ\deltaδ. As a consequence, under the widely believed assumption that QMA≠NP\mathrm{QMA} \neq \mathrm{NP}QMA=NP, we have that quantum witnesses are strictly more powerful than classical witnesses with respect to Merlin-Arthur protocols in which the verifier is a quantum circuit of logarithmic treewidth.
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.
In QMA(2)\mathsf{QMA}(2)QMA(2), two computationally unbounded provers submit unentangled quantum witnesses to a polynomial-time quantum verifier. We ask whether allowing limited shared entanglement between the two provers changes the power of QMA(2)\mathsf{QMA}(2)QMA(2). To this end, we formalize QMA(2;h)\mathsf{QMA}(2;h)QMA(2;h), a variant in which the provers initially share hhh EPR pairs, as suggested by Aaronson, Beigi, Drucker, Fefferman, and Shor (ToC~2009). We show that polynomially many shared EPR pairs give the provers no cheating advantage: QMA(2)⊆QMA(2;h)\mathsf{QMA}(2)\subseteq\mathsf{QMA}(2;h)QMA(2)⊆QMA(2;h) for h=poly⁡(n)h=\operatorname{poly}(n)h=poly(n). For logarithmically many pairs, the power of QMA(2)\mathsf{QMA}(2)QMA(2) remains unchanged, strengthening this inclusion to QMA(2)=QMA(2;h)\mathsf{QMA}(2)=\mathsf{QMA}(2;h)QMA(2)=QMA(2;h) for h=O(log⁡n)h=O(\log n)h=O(logn). Finally, we introduce a variant that also allows classical communication between the provers when preparing the witnesses. This setting is particularly revealing for logarithmic-size witnesses: assuming NP⊈BQP\mathsf{NP}\nsubseteq\mathsf{BQP}NP⊈BQP, we show that superlogarithmically many shared EPR pairs strictly reduce the model's computational power.