Stoquastic PCP vs. Randomness

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. 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.

Authors

• Dorit Aharonov
• Alex Bredariol Grilo

Keywords

• Computer science
• Complexity theory
• Eigenvalues and eigenfunctions
• Probabilistic logic
• Probabilistically Checkable Proofs
• Conjecture
• Version Of Problem
• Constraint Satisfaction Problem
• Random Walk
• Hilbert Space
• Constant Factor
• Local Problems
• State Support
• Computational Basis
• Quantum State
• Sum Of Terms
• Expansion Terms
• Low-energy States
• Part Of The Proof
• Local Terms
• Source Of Frustration
• Set Constraints
• Verification Algorithm
• Number Of Strings
• Non-negative Entries
• Theoretical Computer Science
• Path Weights
• Uniform Case
• Energy State
• Quantum Circuit
• Eigenstates
• Quantum PCP
• Derandomization