  The derandomization of MA, the probabilistic version of NP, is a long
standing open question. In this work, we connect this problem to a variant of
another major problem: the quantum PCP conjecture. Our connection goes through
the surprising quantum characterization of MA by Bravyi and Terhal. They proved
the MA-completeness of the problem of deciding whether the groundenergy of a
uniform stoquastic local Hamiltonian is zero or inverse polynomial. We show
that the gapped version of this problem, i.e. deciding if a given uniform
stoquastic local Hamiltonian is frustration-free or has energy at least some
constant $\epsilon$, is in NP. Thus, if there exists a gap-amplification
procedure for uniform stoquastic Local Hamiltonians (in analogy to the gap
amplification procedure for constraint satisfaction problems in the original
PCP theorem), then MA = NP (and vice versa). Furthermore, if this gap
amplification procedure exhibits some additional (natural) properties, then P =
RP. We feel this work opens up a rich set of new directions to explore, which
might lead to progress on both quantum PCP and derandomization.
  We also provide two small side results of potential interest. First, we are
able to generalize our result by showing that deciding if a uniform stoquastic
Local Hamiltonian has negligible or constant frustration can be also solved in
NP. Additionally, our work reveals a new MA-complete problem which we call
SetCSP, stated in terms of classical constraints on strings of bits, which we
define in the appendix. As far as we know this is the first (arguably) natural
MA-complete problem stated in non-quantum CSP language.
