Quantum Learning Algorithms Imply Circuit Lower Bounds
summary
Claim: nontrivial quantum learners for a circuit class C (produce a quantum hypothesis with error 1/2−γ in time roughly γ^2·2^n/n) imply uniform circuit lower bounds: BQE is not contained in C. Proof builds a quantum natural property from the learner, then—assuming PSPACE hardness—constructs a PRG secure against uniform quantum circuits via hardness amplification (Goldreich‑Levin, Nisan‑Wigderson) and a win‑win argument. Result is conditional but constructive: the PRG and separation are achieved under the stated assumptions.
AI-written summary · about
chapters (12)
- 0:00Intro
- 0:47Boolean circuits
- 2:52Uniform vs. non-uniform circuit
- 6:23Non-uniform circuit lower bounds
- 8:51Quantum learning model
- 14:32Our result
- 23:08Quantum learning vs. circuit lower bounds
- 25:31Roadmap
- 33:31Conditional PRG against uniform quantum computation
- 35:31Quantum natural properties imply circuit lower bounds
- 41:53Construction
- 44:11Open problems
related talks
42mQuantum Learning Algorithms Imply Circuit Lower Bounds
50mQuantum Benchmarking
42mLearning Shallow Quantum Circuits and Quantum States Prepared by Shallow Circuits in Polynomial Time
01h 10mQuantum Advantage with Shallow Clifford Circuits
01h 09mAre Random Quantum Circuits PRUs?
22mSecurity of Quantum Machine Learning Systems
53mFundamental limits to quantum computation
44mQuantum Meets Minimum Circuit Size Problem