Interactive Proofs for Synthesizing Quantum States and Unitaries
summary
Defines quantum analogs of function classes and proves concrete inclusions: state PSPACE ⊆ state QIP (completeness with exponentially small trace distance, soundness requiring non-negligible accept prob gives polynomially small error) and state QIP ⊆ state EXP via SDPs that encode roundwise verifier density matrices. A special-case result shows polynomial action unitary PSPACE ⊆ unitary QIP using Hamiltonian simulation from copies of a PSPACE-computable density ρ. Protocols use private-coin randomness, swap tests, tomography, and polynomially many rounds.
AI-written summary · about
chapters (11)
- 0:00Intro
- 1:07Why state & unitary synthesis seems hard
- 3:08Interactive state & unitary synthesis (1/2)
- 4:13Interactive state synthesis
- 4:43Interactive unitary synthesis
- 5:56Quantum polynomial space
- 6:58State synthesis with a trusted prover Aaronson'16
- 10:32The actual protocol (1/3)
- 13:16The actual protocol (2/3)
- 17:05Multiple entangled provers
- 18:57Open problems
related talks
45mInteractive Proofs for Synthesizing Quantum States and Unitaries
39mDelegated Quantum Computation from Sequential Games
22mQuantum space, ground space traversal, and how to embed multi-prover...
41mQuantum Abstract Interpretation
23mA feasible and unitary programming language with quantum control
44mQuantum Meets Minimum Circuit Size Problem
23mA Case for Synthesis of Recursive Quantum Unitary Programs
28mA type-theoretic account of quantum computation (Extended Abstract)