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.
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) 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 24n61. Moreover, Aaronson {\it et al.} have shown the above inclusion with a constant gap by considering 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 n3+ε1 for every constant ε>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 24n61. Moreover, Aaronson {\it et al.} have shown the above inclusion with a constant gap by considering 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 n3+ϵ1 for every constant ϵ>0.
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 Ω(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-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, poly(n) gates, and treewidth t, one can compute in time (δn)exp(O(t)) a classical assignment y∈{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 QCMA, a quantum generalization of MA. In contrast, we show that the same problem is NP-complete if t=O(logn) even when δ is constant. On the other hand, we show that given a n-input quantum circuit C of treewidth t=O(logn), and a constant δ<1/2, it is QMA-complete to determine whether there exists a quantum state ∣φ⟩∈(Cd)⊗n such that the acceptance probability of C∣φ⟩ is greater than 1−δ, or whether for every such state ∣φ⟩, the acceptance probability of C∣φ⟩ is less than δ. As a consequence, under the widely believed assumption that 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-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, poly(n) gates, and treewidth t, one can compute in time (δn)exp(O(t)) a classical assignment y∈{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 QCMA, a quantum generalization of MA. In contrast, we show that the same problem is NP-complete if t=O(logn) even when δ is constant.
On the other hand, we show that given a n-input quantum circuit C of treewidth t=O(logn), and a constant δ<1/2, it is QMA-complete to determine whether there exists a quantum state ∣φ⟩∈(Cd)⊗n such that the acceptance probability of C∣φ⟩ is greater than 1−δ, or whether for every such state ∣φ⟩, the acceptance probability of C∣φ⟩ is less than δ. As a consequence, under the widely believed assumption that 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.