Time-Space Lower Bounds for Proof Systems with Quantum and Randomized Verifiers
summary
Proves a concrete lower bound: there is a language in QCMA running in linear time on a QRAM that cannot be decided by small‑space random‑access machines in O(n^c) time for c < 2.366. The proof uses quantified‑trading chains, derives a generic slowdown rule (α=2/3) from the stronger QCMA assumption, and crucially applies Grover's search to remove log‑quantifiers, turning a universal log‑search into a √n speedup and yielding the 2.366 exponent.
AI-written summary · about
chapters (11)
- 0:00Start
- 2:03Proof Systems with Quantum and Randomized Verifiers
- 2:54Qcma
- 7:40Roadmap
- 8:53Key Components of Quantified Tuning Proofs
- 12:13Speed Up Rule
- 14:17Slow Down Rule
- 16:18Example of a Time Space
- 16:52The Speed Up Rule
- 23:49Prove Genetic Slowdown Rules in the Quantum Setting
- 24:58Gerber's Algorithm
related talks
22mQuantum space, ground space traversal, and how to embed multi-prover...
44mQuantum Meets Minimum Circuit Size Problem
18mSAQR-QC: A Logic for Scalable but Approximate Quantitative Reasoning about Quantum(…)
22mEfficient Formal Verification of Quantum Error Correcting Programs
46mQuantum Learning Algorithms Imply Circuit Lower Bounds
42mQuantum Learning Algorithms Imply Circuit Lower Bounds
37mQuantum Meets the Minimum Circuit Size Problem
45mClassical Verification of Quantum Computational Advantage