A note about a partial no-go theorem for quantum PCP

Details A note about a partial no-go theorem for quantum PCP A note about a partial no-go theorem for quantum PCP

2010-12-15

arxiv.org/abs/1012.3319v2

Computer Science

Computational Complexity

7 pages, comments are welcome! revised version with very minor corrections

Scientific paper

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, to provide a 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. 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.

Affiliated with

Also associated with

No associations

Rating

A note about a partial no-go theorem for quantum PCP does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A note about a partial no-go theorem for quantum PCP, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A note about a partial no-go theorem for quantum PCP will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-13880