Research map / Learning theory and algorithms / Sample complexity
Sublinear quantum algorithms for training linear and kernel-based classifiers
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use quantum state preparation and amplitude amplification in the primal-dual classifier | Linear classification · Linear classification | complexity dependence on n and d: \tilde{O}((n+d)/\epsilon^{2}) -> \tilde{O}(\frac{\sqrt{n}}{\epsilon^{4}}+\frac{\sqrt{d}}{\epsilon^{8}}) | Helped |
| Replace explicit coordinate-wise norm computation with amplitude estimation | Quantum linear classifier · Linear classification | dimension-dependent gate complexity: d/\epsilon^{2} -> \sqrt{d}/\epsilon^{8} | Helped |
| Use the quantum algorithm rather than the classical classifier | Polynomial-kernel classification · Polynomial-kernel classification | complexity dependence on n and d: \tilde{O}\big(\frac{q(n+d)}{\epsilon^{2}}+\min\big\{\frac{d\log q}{\epsilon^{4}},\frac{q}{\epsilon^{6}}\big\}\big) -> \t | Helped |
| Use the quantum algorithm rather than the classical classifier | Gaussian-kernel classification · Gaussian-kernel classification | complexity dependence on n and d: \tilde{O}\big(\frac{n+d}{s^{4}\epsilon^{2}}+\min\big\{\frac{d}{\epsilon^{4}},\frac{1}{s^{4}\epsilon^{6}}\big\}\big) -> \ | Helped |
| Use amplitude estimation to reduce the dependence on d | Quantum MEB algorithm · Minimum enclosing ball | dimension-dependent gate complexity: \frac{d}{\epsilon} -> \frac{\sqrt{d}}{\epsilon^{7}} | Helped |
| Use amplitude estimation to reduce the dependence on d | Quantum SVM algorithm · \ell^{2}-margin SVM | dimension-dependent gate complexity: \frac{d}{\epsilon} -> \frac{\sqrt{d}}{\epsilon^{7}} | Helped |
| Use the quantum zero-sum game algorithm | Matrix zero-sum games · Matrix zero-sum games | complexity dependence on n: \tilde{O}(\sqrt{n}) | Helped |
| Require higher accuracy instead of constant error | Quantum linear classifier versus classical classifier · Linear classification | running time: \tilde{O}\big(\frac{\sqrt{n}}{\epsilon^{4}}+\frac{\sqrt{d}}{\epsilon^{8}}\big) versus \tilde{O}\big(\frac{n+d}{\epsilon^ | Mixed |
Closest papers by meaning
- Winning Lottery Tickets in Neural Networks via a Quantum-Inspired Classical Algorithm (NeurIPS 2026 · similarity 0.87)
- On the Relation between Trainability and Dequantization of Variational Quantum Learning Models (ICLR 2025 · similarity 0.87)
- Optimal algorithmic complexity of inference in quantum kernel methods (NeurIPS 2026 · similarity 0.87)
- Quantum Algorithms and Lower Bounds for Finite-Sum Optimization (ICML 2024 · similarity 0.86)
- Sublinear Time Quantum Sensitivity Sampling (NeurIPS 2026 · similarity 0.86)
- Understanding Generalization in Quantum Machine Learning with Margins (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.