Paper Info
Title
NP vs QMA_log(2).
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 subset of 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 subset of 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) over tilde(root 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+delta) every constant epsilon > 0.
Year
Venue
Keywords
2010
QUANTUM INFORMATION & COMPUTATION
3-SAT,Merlin-Arthur,Separable states
Field
DocType
Volume
Separable state,Discrete mathematics,Quantum,Combinatorics,e,Logarithm,Completeness (statistics),Mathematics
Journal
10
Issue
ISSN
Citations 
1-2
1533-7146
3
PageRank 
References 
Authors
0.40
3
1
Name
Order
Citations
PageRank
Salman Beigi15611.43