Quantum Learning Algorithms Imply Circuit Lower Bounds
summary
Shows a concrete implication: any quantum learner that beats the two trivial learners (full truth-table queries or the sampling-based 1/2 − 2^{-n/2} advantage) yields a language in BQE that evades polynomial-size Boolean circuits, so nontrivial quantum learning collapses to circuit lower bounds. Proof ingredients: a reduction from quantum learning to a pseudorandom generator secure against uniform quantum computations (constructed from PSPACE hardness) and a quantum generalization of IJKW local list‑decoding for inherently randomized oracles; the construction is modular and gives explicit parameter tradeoffs.
AI-written summary · about
chapters (8)
- 0:00Start
- 5:45Quantum learning model
- 15:33Roadmap of the proof
- 19:05Construction
- 22:59Hardness amplification
- 27:49Quantum natural properties.
- 30:03Quantum learning imply quantum natural properties
- 36:01Open problems
related talks
46mQuantum Learning Algorithms Imply Circuit Lower Bounds
42mLearning Shallow Quantum Circuits and Quantum States Prepared by Shallow Circuits in Polynomial Time
01h 06mQuantum Advantage Without Structure
22mSecurity of Quantum Machine Learning Systems
01h 10mQuantum Advantage with Shallow Clifford Circuits
20mThe Quantum Supremacy Tsirelson Inequality
50mQuantum Benchmarking
37mQuantum Pseudorandomness and Classical Complexity