A Rigorous and Robust Quantum Speed-up in Supervised Machine Learning
summary
Proves an end-to-end quantum speedup for supervised classification by designing a kernel that is classically hard but solvable by quantum kernel estimation, tying hardness to discrete log hardness (so problem sits in BQP) and showing robustness to finite-shot noise via strong-convexity margins. Implementation detail: classical data → quantum feature map → estimate Hilbert–Schmidt inner products by measuring |0⟩ frequencies, then solve SVM dual classically. Requires deep polynomial-depth circuits (shallow 2D is simulable). Experimental note: 17-qubit Sycamore 60–70% accuracy observed.
AI-written summary · about
chapters (8)
- 0:00Introduction to Quantum ML
- 1:34Challenges in Quantum ML
- 5:33Quantum Kernel Methods
- 6:48Kernel Methods Explained
- 12:36Proving Quantum Advantage
- 19:31Complexity and States
- 22:50Prospects and Obstacles
- 25:00Experimental Implementation
related talks
22mSecurity of Quantum Machine Learning Systems
44mQuantum machine learning: Prospects and challenges
15mAccelerQ: Accelerating Quantum Eigensolvers With Machine Learning on Quantum Simulators
46mQuantum Machine Learning 101: An Introduction for Beginners with...
01h 06mPractical Quantum Machine Learning: Overcoming the Bottlenecks of Scalability and(…)
01h 09mRecent Progress in Quantum Advantage
48mQuantum Linear Algebra Using Subspace States
28mThe future of computing with Quantum Computing