Improved quantum boosting
Boosting is a general method to convert a weak learner (which generates hypotheses that are just slightly better than random) into a strong learner (which generates hypotheses that are much better than random). Recently, Arunachalam and Maity  gave the first quantum improvement for boosting, by combining Freund and Schapire’s AdaBoost algorithm with a quantum algorithm for approximate counting. Their booster is faster than classical boosting as a function of the VC-dimension of the weak learner’s hypothesis class, but worse as a function of the quality of the weak learner. In this paper we give a substantially faster and simpler quantum boosting algorithm, based on Servedio’s SmoothBoost algorithm .
|Leibniz International Proceedings in Informatics|
|Quantum Software Consortium , Quantum algorithms and applications|
|31st Annual European Symposium on Algorithms, ESA 2023|
|Organisation||Algorithms and Complexity|
Izdebski, A, & de Wolf, R.M. (2023). Improved quantum boosting. In Annual European Symposium on Algorithms (pp. 64:1–64:16). doi:10.4230/LIPIcs.ESA.2023.64