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

All languages in NP have very short quantum proofs

Hugue Blier, Alain Tapp

Published Sep 5, 2007• 10 citations
OpenAlex

Abstract

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

Related papers

All Languages in NP Have Very Short Quantum Proofs

Hugue Blier, Alain Tapp

In this paper, we show that all languages in NP have logarithmic-size quantum proofs which can be verified provided that two unentangled copies are given. More formally, we introduce the complexity class QMAlog(2) and show that 3COL E QMAlog(2). To obtain this strong and surprising result we have to relax the usual requirements: the completeness is one but the soundness is 1-1/poly. Since the natural classical equivalent of QMAlog(2) is uninteresting (it would be equal to P), this result, like many others, stresses the fact that quantum information is fundamentally different from classical information. It also contributes to our understanding of entanglement since QMAlog = BQP[7].

International Conference on Quantum, Nano and Micro Technologies (ICQNM)•Feb 1, 2009•48 citations

A quantum characterization of NP

Hugue Blier, Alain Tapp

In this article we introduce a new complexity class called PQMA_log(2). Informally, this is the class of languages for which membership has a logarithmic-size quantum proof with perfect completeness and soundness which is polynomially close to 1 in a context where the verifier is provided a proof with two unentangled parts. We then show that PQMA_log(2) = NP. For this to be possible, it is important, when defining the class, not to give too much power to the verifier. This result, when compared to the fact that QMA_log = BQP, gives us new insight on the power of quantum information and the impact of entanglement.

arXiv:0709.0738•Sep 5, 2007•11 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 $\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$.

•Oct 28, 2008•9 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 $\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

The Power of Unentanglement

Scott Aaronson, Salman Beigi, Andrew Drucker +2 more

The class $\mathsf{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? Does $\mathsf{QMA}( k) =\mathsf{QMA}( 2) $ for $k\geq2$? Can $\mathsf{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 $m$ is satisfiable, with constant soundness, given $\widetilde{O}(\sqrt{m}) $ unentangled quantum witnesses with $O( \log m) $ qubits each. Our protocol relies on the existence of very short PCPs. We show that assuming a weak version of the Additivity Conjecture from quantum information theory, any $\mathsf{QMA}( 2) $ protocol can be amplified to exponentially small error, and $\mathsf{QMA}( k) =\mathsf{QMA}( 2) $ for all $k\geq2$. We prove the nonexistence of “perfect disentanglers” for simulating multiple Merlins with one.

Theory of Computing•Jan 1, 2009•53 citations
In this paper, we show that all languages in NP have logarithmic-size quantum proofs which can be verified provided that two unentangled copies are given. More formally, we introduce the complexity class QMAlog(2) and show that 3COL E QMAlog(2). To obtain this strong and surprising result we have to relax the usual requirements: the completeness is one but the soundness is 1-1/poly. Since the natural classical equivalent of QMAlog(2) is uninteresting (it would be equal to P), this result, like many others, stresses the fact that quantum information is fundamentally different from classical information. It also contributes to our understanding of entanglement since QMAlog = BQP[7].
In this article we introduce a new complexity class called PQMA_log(2). Informally, this is the class of languages for which membership has a logarithmic-size quantum proof with perfect completeness and soundness which is polynomially close to 1 in a context where the verifier is provided a proof with two unentangled parts. We then show that PQMA_log(2) = NP. For this to be possible, it is important, when defining the class, not to give too much power to the verifier. This result, when compared to the fact that QMA_log = BQP, gives us new insight on the power of quantum information and the impact of entanglement.
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+\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.
The class $\mathsf{QMA}( k) $, introduced by Kobayashi et al., consists of all languages that can be verified using kkk unentangled quantum proofs. Many of the simplest questions about this class have remained embarrassingly open: for example, can we give any evidence that kkk quantum proofs are more powerful than one? Does $\mathsf{QMA}( k) =\mathsf{QMA}( 2) $ for k≥2k\geq2k≥2? Can $\mathsf{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 mmm is satisfiable, with constant soundness, given $\widetilde{O}(\sqrt{m}) $ unentangled quantum witnesses with $O( \log m) $ qubits each. Our protocol relies on the existence of very short PCPs. We show that assuming a weak version of the Additivity Conjecture from quantum information theory, any $\mathsf{QMA}( 2) $ protocol can be amplified to exponentially small error, and $\mathsf{QMA}( k) =\mathsf{QMA}( 2) $ for all k≥2k\geq2k≥2. We prove the nonexistence of “perfect disentanglers” for simulating multiple Merlins with one.