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:0810.5109 · Quantum Information and Computation

NP vs QMA_\log(2)

Salman Beigi

Published Jan 1, 2010• 36 citations
arXivHTMLPDF

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 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.

DOI
10.26421/qic10.1-2-10

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

•Oct 28, 2008•11 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

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

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

QMA variants with polynomially many provers

Sevag Gharibian, Jamie Sikora, Sarvagya Upadhyay

We study three variants of multi-prover quantum Merlin-Arthur proof systems. We first show that the class of problems that can be efficiently verified using polynomially many quantum proofs, each of logarithmic-size, is exactly \class{MQA} (also known as QCMA), the class of problems which can be efficiently verified via a classical proof and a quantum verifier. We then study the class $\class{BellQMA}(\poly)$, characterized by a verifier who first applies unentangled, nonadaptive measurements to each of the polynomially many proofs, followed by an arbitrary but efficient quantum verification circuit on the resulting measurement outcomes. We show that if the number of outcomes per nonadaptive measurement is a polynomially-bounded function, then the expressive power of the proof system is exactly \class{QMA}. Finally, we study a class equivalent to \class{QMA}($m$), denoted $\class{SepQMA}(m)$, where the verifier's measurement operator corresponding to outcome {\it accept} is a fully separable operator across the $m$ quantum proofs. Using cone programming duality, we give an alternate proof of a result of Harrow and Montanaro [FOCS, pp. 633--642 (2010)] that shows a perfect parallel repetition theorem for $\class{SepQMA}(m)$ for any $m$.

arXiv:1108.0617•Quantum Information and Computation•Jan 1, 2013•21 citations

On perfect completeness for QMA

Scott Aaronson

Whether the class QMA (Quantum Merlin Arthur)\ is equal to QMA_1, or QMA with one-sided error, has been an open problem for years. This note helps to explain why the problem is difficult,\ by using ideas from real analysis to give a "quantum" relative to which QMA \neq QMA_1. As a byproduct, we find that there are facts about quantum complexity classes that are classically relativizing but not quantumly relativizing, among them such "trivial" containments as BQP \subseteq ZQEXP.

arXiv:0806.0450•Quantum Information and Computation•Jan 1, 2009•45 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-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.
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.
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}{\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.
We study three variants of multi-prover quantum Merlin-Arthur proof systems. We first show that the class of problems that can be efficiently verified using polynomially many quantum proofs, each of logarithmic-size, is exactly \class{MQA} (also known as QCMA), the class of problems which can be efficiently verified via a classical proof and a quantum verifier. We then study the class $\class{BellQMA}(\poly)$, characterized by a verifier who first applies unentangled, nonadaptive measurements to each of the polynomially many proofs, followed by an arbitrary but efficient quantum verification circuit on the resulting measurement outcomes. We show that if the number of outcomes per nonadaptive measurement is a polynomially-bounded function, then the expressive power of the proof system is exactly \class{QMA}. Finally, we study a class equivalent to \class{QMA}(mmm), denoted $\class{SepQMA}(m)$, where the verifier's measurement operator corresponding to outcome {\it accept} is a fully separable operator across the mmm quantum proofs. Using cone programming duality, we give an alternate proof of a result of Harrow and Montanaro [FOCS, pp. 633--642 (2010)] that shows a perfect parallel repetition theorem for $\class{SepQMA}(m)$ for any mmm.
Whether the class QMA (Quantum Merlin Arthur)\ is equal to QMA_1, or QMA with one-sided error, has been an open problem for years. This note helps to explain why the problem is difficult,\ by using ideas from real analysis to give a "quantum" relative to which QMA \neq QMA_1. As a byproduct, we find that there are facts about quantum complexity classes that are classically relativizing but not quantumly relativizing, among them such "trivial" containments as BQP \subseteq ZQEXP.