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:0709.0738

A quantum characterization of NP

Hugue Blier, Alain Tapp

Published Sep 5, 2007• 11 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.0709.0738

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

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

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 Unentangled Quantum Proofs with Non-negative Amplitudes

Fernando Granha Jeronimo, Pei Wu

Quantum entanglement is a fundamental property of quantum mechanics and it serves as a basic resource in quantum computation and information. Despite its importance, the power and limitations of quantum entanglement are far from being fully understood. Here, we study entanglement via the lens of computational complexity. This is done by studying quantum generalizations of the class NP with multiple unentangled quantum proofs, the so-called QMA(2) and its variants. The complexity of QMA(2) is known to be closely connected to a variety of problems such as deciding if a state is entangled and several classical optimization problems. However, determining the complexity of QMA(2) is a longstanding open problem, and only the trivial complexity bounds ⊆ (2) ⊆ are known.

arXiv:2402.18790•ACM Symposium on Theory of Computing (STOC)•May 16, 2023•5 citations
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.
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].
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.
Quantum entanglement is a fundamental property of quantum mechanics and it serves as a basic resource in quantum computation and information. Despite its importance, the power and limitations of quantum entanglement are far from being fully understood. Here, we study entanglement via the lens of computational complexity. This is done by studying quantum generalizations of the class NP with multiple unentangled quantum proofs, the so-called QMA(2) and its variants. The complexity of QMA(2) is known to be closely connected to a variety of problems such as deciding if a state is entangled and several classical optimization problems. However, determining the complexity of QMA(2) is a longstanding open problem, and only the trivial complexity bounds ⊆ (2) ⊆ are known.