  In classical machine learning, a set of weak classifiers can be adaptively
combined to form a strong classifier for improving the overall performance, a
technique called adaptive boosting (or AdaBoost). However, constructing the
strong 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 even for the same input. We prove that the update rules and
the query complexity of the non-deterministic classifiers are the same as those
of deterministic classifiers, which may be of independent interest to the
classical machine-learning community. Furthermore, the AdaBoost algorithm can
also be applied to data encoded in the form of quantum states; we show how the
training set can be simplified by using the tools of t-design. Our approach
describes a model of quantum machine learning where quantum speedup is achieved
in finding the optimal classifier, which can then be applied for classical
machine-learning applications.
