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• 9 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 $\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+ε}}$ for every constant $ε>0$.

arXiv:0810.5109•Oct 28, 2008•0 citations

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.

Quantum Information and Computation•Jan 1, 2010•26 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

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

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}δ)^{\exp(O(t))}$ a classical assignment $y\in \{0,1\}^n$ that maximizes the acceptance probability of $C$ up to a $δ$ additive factor. In particular, our algorithm runs in polynomial time if $t$ is constant and $1/poly(n) < δ< 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 $δ$ 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 $δ<1/2$, it is $\mathrm{QMA}$-complete to determine whether there exists a quantum state $\mid\!φ\rangle \in (\mathbb{C}^d)^{\otimes n}$ such that the acceptance probability of $C\mid\!φ\rangle$ is greater than $1-δ$, or whether for every such state $\mid\!φ\rangle$, the acceptance probability of $C\mid\!φ\rangle$ is less than $δ$. 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.

arXiv:1404.5565•Apr 22, 2014•0 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
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 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 $\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 1n3+ε\frac{1}{n^{3+ε}}n3+ε1​ for every constant ε>0ε>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.
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 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}δ)^{\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 δδδ additive factor. In particular, our algorithm runs in polynomial time if ttt is constant and 1/poly(n)<δ<11/poly(n) < δ< 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 δδδ 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δ<1/2δ<1/2, it is QMA\mathrm{QMA}QMA-complete to determine whether there exists a quantum state ∣ ⁣φ⟩∈(Cd)⊗n\mid\!φ\rangle \in (\mathbb{C}^d)^{\otimes n}∣φ⟩∈(Cd)⊗n such that the acceptance probability of C∣ ⁣φ⟩C\mid\!φ\rangleC∣φ⟩ is greater than 1−δ1-δ1−δ, or whether for every such state ∣ ⁣φ⟩\mid\!φ\rangle∣φ⟩, the acceptance probability of C∣ ⁣φ⟩C\mid\!φ\rangleC∣φ⟩ is less than δδδ. 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.
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.