南方科技大学知识苑(SUSTech KC): Quantum speedup in adaptive boosting of binary classification

题名	Quantum speedup in adaptive boosting of binary classification
作者	Wang, XiMing1,2 ; Ma, YueChi 2,3,4; Hsieh, Min-Hsiu 5; Yung, Man-Hong2,3,6
通讯作者	Hsieh, Min-Hsiu; Yung, Man-Hong
发表日期	2021-02-01
DOI	10.1007/s11433-020-1638-5
发表期刊	Science China-Physics Mechanics & Astronomy 影响因子和分区
ISSN	1674-7348
EISSN	1869-1927
卷号	64 期号:2
摘要	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.
关键词	AdaBoost quantum machine learning quantum algorithm 03 67 Ac Lx -a
相关链接	[来源记录]
收录类别	SCI ; EI
语种	英语
学校署名	通讯
资助项目	Natural Science Foundation of Guangdong Province[2017B030308003] ; Key R&D Program of Guangdong Province[2018B030326001] ; Science, Technology and Innovation Commission of Shenzhen Municipality["JCYJ20170412152620376","JCYJ20170817105046702","KYTDPT20181011104202253"] ; National Natural Science Foundation of China[11875160,"U1801661"] ; Economy, Trade and Information Commission of Shenzhen Municipality[201901161512] ; Guangdong Provincial Key Laboratory[2019B121203002]
WOS研究方向	Physics
WOS类目	Physics, Multidisciplinary
WOS记录号	WOS:000609822100001
出版者	SCIENCE PRESS
EI入藏号	20210309787721
EI主题词	Classification (of information) ; Machine learning ; Quantum theory
EI分类号	Information Theory and Signal Processing:716.1 ; Computer Software, Data Handling and Applications:723 ; Quantum Theory; Quantum Mechanics:931.4
来源库	Web of Science
引用统计	被引频次[WOS]：9
成果类型	期刊论文
条目标识符	http://sustech.caswiz.com/handle/2SGJ60CL/221243
专题	理学院_物理系量子科学与工程研究院
作者单位	1.Nanyang Technol Univ, Sch Phys & Mathmat Sci, Singapore, Singapore 2.Southern Univ Sci & Technol, Dept Phys, Shenzhen 518055, Peoples R China 3.Southern Univ Sci & Technol, Shenzhen Inst Quantum Sci & Engn, Shenzhen 518055, Peoples R China 4.Tsinghua Univ, Inst Interdisciplinary Informat Sci, Ctr Quantum Informat, Beijing 100084, Peoples R China 5.Univ Technol Sydney, Ctr Quantum Software & Informat, Sydney, NSW 2007, Australia 6.Southern Univ Sci & Technol, Guangdong Prov Key Lab Quantum Sci & Engn, Shenzhen 518055, Peoples R China
第一作者单位	物理系
通讯作者单位	物理系; 量子科学与工程研究院
推荐引用方式 GB/T 7714	Wang, XiMing,Ma, YueChi,Hsieh, Min-Hsiu,et al. Quantum speedup in adaptive boosting of binary classification[J]. Science China-Physics Mechanics & Astronomy,2021,64(2).
APA	Wang, XiMing,Ma, YueChi,Hsieh, Min-Hsiu,&Yung, Man-Hong.(2021).Quantum speedup in adaptive boosting of binary classification.Science China-Physics Mechanics & Astronomy,64(2).
MLA	Wang, XiMing,et al."Quantum speedup in adaptive boosting of binary classification".Science China-Physics Mechanics & Astronomy 64.2(2021).