Quantum Speedup in Adaptive Boosting of Binary Classification
This work addresses the computational bottleneck in boosting algorithms for binary classification, offering a quantum speedup that could benefit classical machine learning applications, though it is incremental as it extends existing methods to a quantum context.
The authors tackled the resource-intensive construction of strong classifiers in adaptive boosting for large datasets by proposing a quantum extension of AdaBoost, achieving a quadratic speedup in query complexity for optimal classifier output and generalizing the algorithm to handle probabilistic weak classifiers.
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.