The Quantum Games PCP: Results and Confessions
summary
Claims a 7-prover, 1-round MIP proof system that would map QMA local Hamiltonians with 1/poly gap to a constant-gap Pauli-measurement test, using an error-correcting code encoding and the quantum low-degree test to force Pauli X/Z measurements. The amplification step raises (I+H)/2 to a polynomial tensor power, which converts 1/poly gaps to constant gaps but enlarges the Pauli 1-norm (e.g., tensor powers of (X+Z)/√2 give exponential blowup), breaking the soundness scaling, so the core reduction currently fails.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 0:45The classical PCP theorem
- 3:31Inspiration from history
- 4:58The games PCP conjecture
- 11:10Quantum PCP formalization
- 14:53Good news and bad news
- 20:11Limits of the conjecture
- 27:10Confession of the error
- 32:42Analyzing the flaw
- 38:11Amplification challenges
- 42:27Future open questions
related talks
22mEfficient Formal Verification of Quantum Error Correcting Programs
39mDelegated Quantum Computation from Sequential Games
44mQuantum Meets Minimum Circuit Size Problem
52mQMA and the Power of “Positivity”
58mLimitations for Quantum PCPs
22mQuantum space, ground space traversal, and how to embed multi-prover...
30mQuantum Constant Propagation
01h 00mQuantum Physics for Software Developers