Delegated Quantum Computation from Sequential Games
summary
Shows a constructive route to fully delegated quantum computation with a fully classical verifier and two untrusted quantum servers, proving QIP is contained in MIP by combining three concrete pieces: sequential CHSH rigidity (players must share EPR pairs and behave tensor-product-wise if they win ~cos^2(π/8)≈85% of games), computation by teleportation* using prepared resource states and Bell measurements, and a randomness/stop-at-a-random-block trick; protocol is explicit but incurs large adaptive round complexity.
AI-written summary · about
chapters (11)
- 0:00Intro
- 0:17Delegated Quantum Computation
- 2:50SemiQuantum Delegation
- 4:48The Obvious Approach
- 8:23Cheating Strategies
- 13:32Characterization
- 21:44CPR pairs
- 22:20Teleportation
- 26:39Set
- 31:33Mix
- 33:51Summary
related talks
21mInteractive Proofs for Synthesizing Quantum States and Unitaries
48mThe Quantum Games PCP: Results and Confessions
45mClassical Verification of Quantum Computational Advantage
45mInteractive Proofs for Synthesizing Quantum States and Unitaries
16mAsynchronous Multi-Party Quantum Computation
01h 10mQuantum Advantage with Shallow Clifford Circuits
44mQuantum Meets Minimum Circuit Size Problem
18mAutomated distribution of quantum circuits via hypergraph partitioning