A Survey on the Complexity of Entangled Provers
summary
Describes how classical multi‑prover PCP-style protocols are rewritten to resist entangled provers, proving completeness and inverse‑polynomial soundness gaps for the modified protocols; uses concrete tools — consistency checks, the multilinearity test, adding a third prover and an SDP consolidation step — to bound measurement distance and round operator strategies, and gives the explicit example that the magic square game wins perfectly using two EPR pairs, so the constructed protocols work against entanglement up to the proved error parameters.
AI-written summary · about
chapters (18)
- 0:00Intro
- 1:04Background
- 2:13Problem setting and notions
- 16:27Entanglement undermines soundness
- 20:10Entanglement resistant techniques
- 21:47Consistency check
- 23:21Consistency as a measure of "closeness"
- 24:38Confusion check
- 34:18What to prove?
- 36:48Proof outline
- 37:56The base step
- 41:36Upper bounds?
- 46:38Quantum satisfying assignment
- 48:46Magic square revisited
- 52:53Reductions of *-problems
- 54:12Triangular prism gadget
- 55:26The complexity of 3-SAT
- 57:14Hardness of the problems
related talks
48mThe Quantum Games PCP: Results and Confessions
32mBeating Classical Impossibility of Position Verification
21mInteractive Proofs for Synthesizing Quantum States and Unitaries
45mClassical Verification of Quantum Computational Advantage
22mQuantum space, ground space traversal, and how to embed multi-prover...
22mEfficient Formal Verification of Quantum Error Correcting Programs
45mInteractive Proofs for Synthesizing Quantum States and Unitaries
29mParallel Repetition for Entangled Games via Fast Quantum Search