# Quantum Boosting

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Feb 2020.

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

- [Beyond Classical Attention: Quantum Attention for Scalable Computation](https://mlsanity.com/paper/2307.08045/) (2023)
- [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)
- [Quantum Perceptron Revisited: Computational-Statistical Tradeoffs](https://mlsanity.com/paper/2106.02496/) (2021)
- [Classical ensemble of Quantum-classical ML algorithms for Phishing detection in Ethereum transaction networks](https://mlsanity.com/paper/2211.00004/) (2022)
- [Efficient Quantum Agnostic Improper Learning of Decision Trees](https://mlsanity.com/paper/2210.00212/) (2022)
- [Quantum Boosting using Domain-Partitioning Hypotheses](https://mlsanity.com/paper/2110.12793/) (2021)
- [Quantum Speedup for Spectral Approximation of Kronecker Products](https://mlsanity.com/paper/2402.07027/) (2024)

## Abstract (arXiv)

Suppose we have a weak learning algorithm A for a Boolean-valued problem: A produces hypotheses whose bias γ is small, only slightly better than random guessing (this could, for instance, be due to implementing A on a noisy device), can we boost the performance of A so that A's output is correct on 2/3 of the inputs? Boosting is a technique that converts a weak and inaccurate machine learning algorithm into a strong accurate learning algorithm. The AdaBoost algorithm by Freund and Schapire (for which they were awarded the G"odel prize in 2003) is one of the widely used boosting algorithms, with many applications in theory and practice. Suppose we have a γ-weak learner for a Boolean concept class C that takes time R(C), then the time complexity of AdaBoost scales as VC(C)· poly(R(C), 1/γ), where VC(C) is the VC-dimension of C. In this paper, we show how quantum techniques can improve the time complexity of classical AdaBoost. To this end, suppose we have a γ-weak quantum learner for a Boolean concept class C that takes time Q(C), we introduce a quantum boosting algorithm whose complexity scales as √VC(C)· poly(Q(C),1/γ); thereby achieving a quadratic quantum improvement over classical AdaBoost in terms of VC(C).