Parallel Repetition for Entangled Games via Fast Quantum Search
summary
Proves for free (product-input) games a stronger parallel-repetition upper bound: the entangled value falls like entangled value ≤ (1−ε^{3/2})^{Θ(n/s)} where ε = 1 − val, saving a √ε factor over prior bounds. The proof embeds a too-good n-copy strategy into one copy via mutual-information conditions and replaces the classical checking protocol with a distributed Grover search* style quantum communication protocol, reducing communication and tightening the decay. Extensions cover multi-player and quantum-answer variants.
AI-written summary · about
chapters (11)
- 0:00Intro
- 0:41Parallel repetition 101
- 5:33Quantum parallel repetition
- 6:53Our main result
- 8:23What's known classically?
- 12:20Proving parallel repetition, using communication protocols
- 19:11Chailloux-Scarpa communication protocol
- 24:29Our communication protocol
- 25:56Technical Details
- 26:09Other results
- 26:34Open Questions
related talks
20mThe Quantum Supremacy Tsirelson Inequality
21mQuantum versus Randomized Communication Complexity, with Efficient Players
48mGames to Establish Structure in an Unknown Hilbert Space
39mDelegated Quantum Computation from Sequential Games
01h 03mA Survey on the Complexity of Entangled Provers
42mTests for "Quantumness"
01h 10mQuantum Advantage with Shallow Clifford Circuits
48mThe Quantum Games PCP: Results and Confessions