ECCC-Report TR19-010https://eccc.weizmann.ac.il/report/2019/010Comments and Revisions published for TR19-010en-usSun, 27 Jan 2019 14:32:57 +0200
Paper TR19-010
| Stoquastic PCP vs. Randomness |
Alex Bredariol Grilo,
Dorit Aharonov
https://eccc.weizmann.ac.il/report/2019/010The 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 $\varepsilon$, 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. As a small side result, we also show that deciding if commuting stoquastic Hamiltonian is frustration free is in NP. Sun, 27 Jan 2019 14:32:57 +0200https://eccc.weizmann.ac.il/report/2019/010