NP vs QMA_log(2) (pp0141-0151)
          Salman Beigi
          doi: https://doi.org/10.26421/QIC10.1-2-10
Abstracts: 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 belongs to 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 belongs to 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.
Key words: 3-SAT, Merlin-Arthur, Separable states