Abstract
Boosting is a technique that boosts a weak and inaccurate machine learning algorithm into a strong accurate learning algorithm. The AdaBoost algorithm by Freund and Schapire (for which they were awarded the Gödel prize in 2003) is one of the widely used boosting algorithms, with many applications in theory and practice. Suppose we have a-weak learner for a Boolean concept class C that takes time R(C), then the time complexity of AdaBoost scales as VC(C)-poly(R(C); 1=), where VC(C) is the VC-dimension of C. In this paper, we show how quantum techniques can improve the time complexity of classical AdaBoost. To this end, suppose we have a-weak quantum learning algorithm for a Boolean concept class C that takes time Q(C), we introduce a quantum boosting algorithm whose complexity scales as p VC(C)-poly(Q(C); 1=); thereby achieving quadratic quantum improvement over classical AdaBoost in terms of VC(C).