Abstract
An interesting current open problem in quantum complexity theory is the quantum PCP conjecture. In analogy with the PCP theorem, the conjecture states that it is QMA-hard to tell whether a quantum constraint satisfaction problem (aka a local quantum Hamiltonian) is satisfiable or far from satisfiable, with a constant fraction of the constraints being violated in any assignment.
In this talk I will discuss limitations for quantum PCPs due to one of the most distinguishing features of quantum entanglement: its monogamous character. The monogamy of entanglement is the principle that the more entangled a system is with another one, the less entangled it can be with anything else. I will show how a quantitative understanding of entanglement monogamy leads both to limitations on the parameters that a potential quantum analogue of the PCP theorem might have, and to potential approaches to proving such an analogue (for instance by attempting to quantize the main steps of Dinur’s proof of the PCP theorem).
The talk will be mostly based on joint work with Aram Harrow (arXiv:1310.0017).