Fetching the paper…

Reading the bibliography…

2010

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

Arad, Itai

Original
PDF
Post on X

Understand

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 note about a partial no-go theorem for quantum PCP · Around

Built on

Some unsolved problems of unknown depth about operators on Hilbert space
PR Halmos · 1976
Earlier work this paper cites.
Almost commuting matrices
Carl Pearcy and Allen Shields · 1979
Earlier work this paper cites.
Commutative version of the k-local Hamiltonian problem and common eigenspace problem
S. Bravyi and M. Vyalyi · 2003
Earlier work this paper cites.

Similar

Efficient algorithm for a quantum analogue of 2-SAT
S. Bravyi · 2006
Cited alongside, same era.
The pcp theorem by gap amplification
Irit Dinur · 2007
Cited alongside, same era.
personal communication, 2008
M. B. Hastings · 2008
Cited alongside, same era.

Then

The detectability lemma and quantum gap amplification
Original
Dorit Aharonov, Itai Arad, Zeph Landau, and Umesh Vazirani · 2009
Later among the works it cites.
personal communication, 2009
M. B. Hastings · 2009
Later among the works it cites.
Markov entropy decomposition: a variational dual for quantum belief propagation
Original
D. Poulin and M. B. Hastings · 2010
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…