Quantum Boosting

Boosting is one of the most famous classical machine learning techniques (in theory and practice) that can construct a strong machine learning algorithm given access to a weak learning algorithm. It is natural to consider boosting in the quantum setting for the following reason: suppose we implement a quantum machine learning (QML) algorithm on a NISQ device, then the guarantees of the QML algorithm could be much worse than it was designed for, due to the noise in the quantum system. This motivates the question whether we can ``boost" the performance of a weak QML algorithm (implemented on a NISQ machine) to a *strong* QML algorithm?

Classically the time complexity for boosting the performance of a weak learner for a concept class C is characterized by the VC dimension of C. Here, we ask if quantum techniques can provide an improvement over the well-known AdaBoost algorithm introduced by Freund and Schapire '93 (for which they were awarded the Godel prize in 2003). In this work, we introduce the first quantum boosting algorithm which is provably faster than classical Adaboost with time complexity that scales quadratically in the VC dimension of C.