Oracle Separations Between QMA and QCMA

on YouTube ↗47m

" summary

Surveys explicit constructions that separate QMA vs QCMA under nonstandard oracles: a quantum oracle that reflects one random state (needs a quantum witness and is provably hard for classical proofs), a distributional adjacency-list problem called expander-distinguishing whose QMA protocol uses phase estimation on a provided eigenstate, and constructions that embed a tiny decision bit in indices hard to find via Yamakawa‑Zhandry invertibility so classical witnesses and queries fail. Follow-ups relax verifier access to nonadaptive quantum queries; a full classical (standard) oracle separation remains open.

AI-written summary · about

" chapters (7)

1. 0:00QMA and QCMA separations
2. 1:04QMA vs QCMA definitions
3. 10:12Motivation for oracle separations
4. 19:06Random circuit oracle separation
5. 21:58Expander graph oracle separation
6. 34:11Restricting oracle access
7. 42:44Open problems in QMA vs QCMA

" related talks

• 25mQuantum NP and BeyondSandy Irani · KARPfest80
• 22mQuantum space, ground space traversal, and how to embed multi-prover...Dorian Rudolph, Sevag Gharibian · ITCS 2023
• 49mQuantum CryptanalysisRen Taguchi, Jiayu Xu · RSA Conference 2023
• 01h 20mVerifiable Quantum Supremacy: What I Hope Will Be DoneScott Aaronson · Quantum Summer Cluster Workshop 2023
• 57mA Simple Quantum Sketch With Applications to Graph AlgorithmsJohn Kallaugher · Sketching and Algorithm Design 2023
• 46mInteractive Proofs for Verifying Machine LearningShafi Goldwasser, Guy N. Rothblum, Jonathan Shafer, Amir Yehudayoff · ITCS 2021
• 59mThe Bizarre Quantum World with Q# and Azure QuantumFilip W · NDC Porto 2022
• 01h 03mMicrosoft Q# and Azure QuantumJohnny Hooyberghs · NDC London 2021