Limitations for Quantum PCPs
summary
Shows a concrete obstruction to a straightforward quantum PCP: using a quantum de Finetti-type bound (extended beyond permutation symmetry) and monogamy of entanglement, any n-qubit, D-regular 2-local Hamiltonian has a separable (product) witness whose energy per clause is within about error ~ d^2 / degree of the true minimum (d = local dimension). The construction is efficient, uses parallel-repetition-style blowups (alphabet and degree grow exponentially in t), and implies that if those blowup maps exist then QPCP with those parameters cannot hold.
AI-written summary · about
chapters (12)
- 0:00Limitations for Quantum PCPs
- 2:56Quantum Constraint Satisfaction Problems
- 6:52PCP Theorem
- 8:55Quantum Cook-Levin Thm
- 10:43Quantum PCP? The Quantum PCP conjecture: There is Ost. the following problem is GMA-complete: Given 12.2.n.m-gesp H determine whether
- 19:50History of the Problem
- 20:44"Blowing up" maps prop for everyt21 there is an efficient mapping from
- 22:52Example: Parallel Repetition (for kids)
- 30:17Entanglement Monogamy...
- 35:07Quantum de Finetti Theorems
- 48:43Summary and Open Questions
- 56:07Coming back to quantum "blowing up" maps + qPCP thm if for everyt21 there is an efficient mapping from
related talks
50mMaking the Leap to Quantum PCPs
48mThe Quantum Games PCP: Results and Confessions
01h 37mFault-Tolerance Against Adversarial Errors & PCPs
48mIntroduction To Commuting Local Hamiltonian Problems
33mLightning Talks
44mQuantum Meets Minimum Circuit Size Problem
32mTowards local testability for quantum coding
26mBounds on qLDPC Code Parameters