A NOTE ABOUT A PARTIAL NO-GO THEROREM FOR QUANTUM PCP
This is not a disproof of the quantum PCP conjecture! In this note we use perturbation on the commuting Hamiltonian problem on a graph, based on results by Bravyi and Vyalyi [1], to provide a very partial no-go theorem for quantum PCP. Specifically, we derive an upper bound on how large the promise gap can be for the quantum PCP still to hold, as a function of the non-commuteness of the system. As the system becomes more and more commuting, the maximal promise gap shrinks. We view these results as possibly a preliminary step towards disproving the quantum PCP conjecture posed in [2]. A different way to view these results is actually as indications that a critical point exists, beyond which quantum PCP indeed holds; in any case, we hope that these results will lead to progress on this important open problem.
quantum pcp local hamiltonians qsat