Quantum Pseudorandomness and Classical Complexity

on YouTube ↗37m

" summary

Constructs a simple quantum oracle where BQP = QMA relative to a quantum oracle while simultaneously pseudorandom quantum states (PRSs) exist relative to that oracle, showing a black‑box separation between PRSs and usual cryptographic primitives. Uses Haar concentration and the BBBV search lower bound. Proves the converse: if BQP = PP (i.e., can solve #P) then PRSs cannot exist by combining classical shadows protocols with postselection (post‑BQP = PP). Also rules out hyper‑efficient shadow tomography from black‑box state access.

AI-written summary · about

" chapters (10)

1. 0:00Intro
2. 0:33Pseudorandom States (PRSs): "Computational approx. to Haar measure"
3. 2:31Cryptography
4. 4:20Definition (li, Liu, Song 2018)
5. 8:14"QMA" protocol to break PRSS Suppose Arthur has @T Merlin: send quantum circuit C
6. 12:49Theorem (This work) There exists a quantum oracle O such that
7. 21:46Haar-random oracle
8. 27:01Classical shadows (Huang, kueng, Preskill 2020)
9. 28:49Classical oracles?
10. 31:09William Kretschmer

" related talks

• 01h 06mQuantum Advantage Without StructureMark Zhandry · Quantum and Lattices Joint Reunion Workshop
• 59mQuantum cryptography and quantum complexityWilliam Kretschmer · Summer Cluster on Quantum Computing 2025
• 44mQuantum Meets Minimum Circuit Size ProblemNai-Hui Chia · Lower Bounds, Learning, and Average-Case Complexity
• 58mTwo classical oracle separations between QMA and QCMAJohn Bostanci · Summer Cluster Final Workshop 2026
• 42mQuantum Learning Algorithms Imply Circuit Lower BoundsSrinivasan Arunachalam, Alex B. Grilo, Tom Gur, Igor C. Oliveira, Aarthi Sundaram · Lower Bounds, Learning, and Average-Case Complexity
• 01h 09mAre Random Quantum Circuits PRUs?Alex Lombardi · Summer Cluster on Quantum Computing 2025
• 01h 31mLightning TalksSummer Cluster on Quantum Computing 2025
• 22mQbC: Quantum Correctness by ConstructionAnurudh Peduri, Ina Schaefer, Michael Walter · PLanQC 2024