Quantum speedup in adaptive boosting of binary classification

• 作者: XiMing Wang YueChi Ma Min-Hsiu Hsieh Man-Hong Yung
• 来源期刊: 中国科学：物理学 力学 天文学（英文版）
• 年，卷（期）: 2021,（2）
• 所属期刊栏目: Article
• 页码范围: 51-60
• 页数: 10页
• 语种: 英文

摘要

In classical machine learning,a set of weak classifiers can be adaptively combined for improving the overall performance,a technique called adaptive boosting(or AdaBoost).However,constructing a combined 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.We prove that the query complexity of the non-deterministic classifiers is the same as those of deterministic classifiers,which may be of independent interest to the classical machine-learning community.Additionally,once the optimal classifier is determined by our quantum algorithm,no quantum resources are further required.This fact may lead to applications on near term quantum devices.