@techreport{TR-IC-14-16,
   number = {IC-14-16},
   author = {Fernando Granha Jeronimo and Arnaldo Vieira Moura},
   title  = {{Classical Probabilistic Checkable Proof and Multi-Prover
                   Quantum Merlin-Arthur}},
   month = {October},
   year = {2014},
   institution = {Institute of Computing, University of Campinas},
   note = {In English, 18 pages.
    \par\selectlanguage{english}\textbf{Abstract}
       Classically,  extending  the  Merlin-Arthur complexity class to
       multiple  provers  does  not  increase  its computational power
       since  multiple  Merlins  can  be  simulated  by  a single one.
       However, in the quantum model an analogous result may no longer
       hold   if   the   provers   are   assumed  to  be  unentangled. 
       Surprisingly,  NP-complete  problems admit quantum Multi-prover
       Merlin-Arthur protocols in which only two unentangled witnesses
       of  logarithm  size  are  used.  In  this  work,  we extend one
       protocol   so   that   it   can   simulate   generic  classical 
       Probabilistic  Checkable  Proofs  (PCP) verifiers. By combining
       this  new  protocol with specific PCPs theorems, it is possible
       to  recover known results in a simplified way. The first result
       is  a  Two-prover QMA protocol for $3SAT$ with logarithmic size
       witnesses    and    a    completeness    soundness    gap    of   
       $\Omega(\frac{1}{n^{2+\varepsilon}})$  for  any  $\varepsilon >
       0$. The second one is a known characterization of NEXP.
  }
}