Quantum space, ground space traversal, and how to embed multi-prover...
summary
Shows that QCMASPACE = NEXP, so allowing an exponentially long classical streamed proof breaks Savitch‑style collapse; proves a universal path‑following lemma that approximates any Lipschitz path on the unit sphere to error 1/x by an exponentially long sequence of 2‑local unitaries while intermediate states stay within 1/x; gives an embedding lemma reducing streamed proofs to a separable sparse Hamiltonian instance with inverse‑exponential promise gap; uses these to show GSCON becomes trivial below subexponential error and remains PSPACE‑hard at exponential precision.
AI-written summary · about
chapters (14)
- 0:00Intro
- 0:15Theme-Quantum Space (Quantum Analogue of NPSPACE)
- 1:41Quantum analogues of (N)PSPACE
- 4:14Universal path following lemma
- 5:39Statement and Proof
- 9:18Recursive Decomposition
- 9:35Local Hamiltonian Problem and QMA(2)
- 10:48Application to GSCON
- 12:28Feynman-Kitaev circuit-to-Hamiltonian construction
- 14:20QCMASPACE-Streaming proof definition
- 17:31FLUX gadget-Implementation
- 18:45FLUX gadget Analysis
- 20:03Embedding Lemma
- 21:45Open problems
related talks
34mTime-Space Lower Bounds for Proof Systems with Quantum and Randomized Verifiers
21mInteractive Proofs for Synthesizing Quantum States and Unitaries
45mInteractive Proofs for Synthesizing Quantum States and Unitaries
44mQuantum Meets Minimum Circuit Size Problem
48mThe Quantum Games PCP: Results and Confessions
25mQuantum NP and Beyond
40mDemocratizing quantum formal verification: the path-sum way
01h 10mQuantum Advantage with Shallow Clifford Circuits