Stoquastic PCP vs. Randomness

Understand

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.