Fetching the paper…

Reading the bibliography…

NP vs QMA_log(2) · Around

2008

NP vs QMA_log(2)

Beigi, Salman

Original
PDF
Post on X

Understand

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

Built on

C. H, Papadimitriou,
1994
Earlier work this paper cites.
E. Knill. Quantum randomness and nondeterminism. Technical Report LAUR-96-2186, Los Alamos National Laboratory, 1996. quantph/9610012
1996
Earlier work this paper cites.
A. Ben-Tal and A. Nemirovski,
1998
Earlier work this paper cites.
A. Kitaev. Quantum NP. Talk at AQIP99: Second Workshop on Algorithms in Quantum Information Processing, 1999
1999
Earlier work this paper cites.
M. A. Nielsen and I. L. Chuang,
2000
Earlier work this paper cites.

Similar

J. Watrous,
2000
Cited alongside, same era.
A. Kitaev, A. Shen, and M. N. Vyalyi,
2002
Cited alongside, same era.
H. Kobayashi, K. Matsumoto and T. Yamakami,
2003
Cited alongside, same era.
Leonid Gurvits,
2004
Cited alongside, same era.
Dorit Aharonov and Tomer Naveh,
Cited in the paper.
H. Kobayashi, K. Matsumoto and T. Yamakami,
Cited in the paper.

Then

Chris Marriott, John Watrous,
2005
Later among the works it cites.
Michael Sipser,
2005
Later among the works it cites.
S. Aaronson, S. Beigi, A. Drucker, B. Fefferman and P. Shor,
2009
Closest in time.
Hugue Blier and Alain Tapp,
2009
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…