Quantum PCPs Meet Derandomization

          @misc{ scivideos_15584,
            doi = {},
            url = {https://simons.berkeley.edu/talks/tbd-144},
            author = {},
            keywords = {},
            language = {en},
            title = {Quantum PCPs Meet Derandomization},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2020},
            month = {apr},
            note = {15584 see, \url{https://scivideos.org/index.php/Simons-Institute/15584}}
          }
          

Abstract

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 ϵ, 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. Joint work with Dorit Aharonov.