Two classical oracle separations between QMA and QCMA
summary
Claims two explicit classical oracle separations: one called spectral Forrelation and one called code intersection. Both languages are in QMA via a witness-and-measure routine (spectral Forrelation uses an S/U pair checked before/after Hadamards; code intersection uses Yamakawa–Zhandry convolution to produce valid signatures), yet both lie outside QCMA by a sampler argument that extracts >L/2 marked positions from any classical witness. Proof tools include a bosonic compressed oracle analysis to bound U-queries and multiplicity codes with near‑optimal list‑recoverability.
AI-written summary · about
chapters (10)
- 0:00Welcome
- 3:18Talk on QMA vs QCMA
- 12:32Fisherman parable
- 23:36Spectral Forrelation problem
- 28:17Few queries to U oracle fail
- 32:59Code intersection signatures
- 40:24QCMA lower bound
- 46:40Quantum proofs unclonability
- 48:50Open problems
- 51:20Q&A
related talks
44mQuantum Meets Minimum Circuit Size Problem
37mQuantum Pseudorandomness and Classical Complexity
33mVerified Compilation of Quantum Oracles
52mQMA and the Power of “Positivity”
34mTime-Space Lower Bounds for Proof Systems with Quantum and Randomized Verifiers
18mConcurrent Quantum Separation Logic for Fine-Grained Parallelism
59mQuantum cryptography and quantum complexity
01h 31mLightning Talks