Quantum speedup in adaptive boosting of binary classification

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.