Quantum speedup in adaptive boosting of binary classification
- Publisher:
- Springer Science and Business Media LLC
- Publication Type:
- Journal Article
- Citation:
- Science China: Physics, Mechanics and Astronomy, 2021, 64, (2), pp. 220311
- Issue Date:
- 2021-02-01
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
| Wang2020_Article_QuantumSpeedupInAdaptiveBoosti.pdf | Published version | 193.71 kB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
In classical machine learning, a set of weak classifiers can be adaptively combined for improving the overall performance, a technique called adaptive boosting (or AdaBoost). However, constructing a combined classifier for a large data set is typically resource consuming. Here we propose a quantum extension of AdaBoost, demonstrating a quantum algorithm that can output the optimal strong classifier with a quadratic speedup in the number of queries of the weak classifiers. Our results also include a generalization of the standard AdaBoost to the cases where the output of each classifier may be probabilistic. We prove that the query complexity of the non-deterministic classifiers is the same as those of deterministic classifiers, which may be of independent interest to the classical machine-learning community. Additionally, once the optimal classifier is determined by our quantum algorithm, no quantum resources are further required. This fact may lead to applications on near term quantum devices.
Please use this identifier to cite or link to this item: