Compiled Nonlocal Games: From CHSH to BQP Verification
summary
Applies the Kalai‑et‑al. compilation to CHSH and proves the compiled single‑prover protocol still attains the Tsirelson bound (cos^2(π/8) ≈ 0.85), then extracts the usual CHSH rigidity (anticommuting Pauli‑like observables) using a sum‑of‑squares decomposition and the swap isometry. Builds a single‑prover classical verification protocol for BQP that mirrors Mahadev but uses quantum fully homomorphic encryption (QFHE) as a black box and avoids explicit reliance on TCFs or an adaptive hardcore bit, yielding a CHSH rigidity recovered soundness proof.
AI-written summary · about
chapters (11)
- 0:00Classical testing of quantum devices
- 1:26Classical control with two devices
- 3:53Single-device verification via cryptography
- 9:11Relaxing cryptographic assumptions
- 11:03Protocol using QFHE
- 17:13Nonlocal games and CHSH
- 22:14Compiling nonlocal games
- 33:06KLVY compiler overview
- 37:44Sum of squares for Tsirelson bound
- 43:30Sum of squares on compiled CHSH
- 52:50Future outlook in quantum verification
related talks
01h 25mIntroduction to Verifiable Computing
32mBeating Classical Impossibility of Position Verification
51mDistributed Zero-Knowledge Proofs and Applications to Secure Computation
34mQuantum and Classical Coin-flipping Protocols Based on Bit-commitment and their Point Games
31mSequential Composition of Rational Proofs
44mBilinear Pairings-based Zero-Knowledge Proofs
57mThe Cryptographic Lens: Visions of our Past and Future
41mGKR based Zero-Knowledge Proofs