# Improved Quantum Boosting

arXiv: https://arxiv.org/abs/2009.08360 · HTML: https://mlsanity.com/paper/2009.08360/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Sep 2020.

## Built on by (most cited first, 7 of 7)

- [Quantum Machine Learning on Near-Term Quantum Devices: Current State of Supervised and Unsupervised Techniques for Real-World Applications](https://mlsanity.com/paper/2307.00908/) (2023)
- [Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints](https://mlsanity.com/paper/2110.13086/) (2021)
- [Private learning implies quantum stability](https://mlsanity.com/paper/2102.07171/) (2021)
- [Quantum advantage for learning shallow neural networks with natural data distributions](https://mlsanity.com/paper/2503.20879/) (2025)
- [Efficient Quantum Agnostic Improper Learning of Decision Trees](https://mlsanity.com/paper/2210.00212/) (2022)
- [The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem](https://mlsanity.com/paper/2409.11597/) (2024)
- [Quantum Boosting using Domain-Partitioning Hypotheses](https://mlsanity.com/paper/2110.12793/) (2021)

## Abstract (arXiv)

Boosting is a general method to convert a weak learner (which generates hypotheses that are just slightly better than random) into a strong learner (which generates hypotheses that are much better than random). Recently, Arunachalam and Maity gave the first quantum improvement for boosting, by combining Freund and Schapire's AdaBoost algorithm with a quantum algorithm for approximate counting. Their booster is faster than classical boosting as a function of the VC-dimension of the weak learner's hypothesis class, but worse as a function of the quality of the weak learner. In this paper we give a substantially faster and simpler quantum boosting algorithm, based on Servedio's SmoothBoost algorithm.