Interactive Proofs for Synthesizing Quantum States and Unitaries
summary
Proves that space-uniform families of n‑qubit states admit interactive synthesis protocols, i.e. state PSPACE ⊆ state QIP, with perfect completeness and the soundness guarantee that any accepted output slightly above exponentially rare is only inverse‑polynomially far from the target. Construction replaces trusted amplitude oracles by QIP=PSPACE subprotocols for computing conditional amplitudes, and thwarts quantum entanglement/phase attacks by maintaining two-copy test-and-grow invariants with swap tests. Honest prover needs PSPACE; unitary synthesis only works so far for poly‑dimensional active subspaces.
AI-written summary · about
chapters (11)
- 0:00Start
- 0:55Motivating Tasks
- 1:50Task State Synthesis
- 3:35Interactive Protocol To Synthesize a State
- 4:28Soundness Property
- 8:46Interactive State Synthesis
- 11:58Space Uniform Family of Quantum States
- 15:23State Complexity Classes
- 19:18Conditional Amplitudes of Psi in Superposition
- 28:19Example of a Quantum Attack
- 32:53Cryptographic Applications of Interactive State Synthesis
related talks
21mInteractive Proofs for Synthesizing Quantum States and Unitaries
23mA Case for Synthesis of Recursive Quantum Unitary Programs
22mQuantum space, ground space traversal, and how to embed multi-prover...
39mDelegated Quantum Computation from Sequential Games
23mA feasible and unitary programming language with quantum control
44mQuantum Meets Minimum Circuit Size Problem
22mOptimal Two-Qubit Circuits for Universal Fault-Tolerant Quantum Computation
22mQbC: Quantum Correctness by Construction