Exact quantum query complexity of weight decision problems via Chebyshev polynomials

作     者：Xiaoyu HE Xiaoming SUN Guang YANG Pei YUAN 

作者机构：Institute of Computing Technology Chinese Academy of Sciences (CAS) University of Chinese Academy of Sciences 

出 版 物：《Science China(Information Sciences)》 (中国科学:信息科学(英文版))

年 卷 期：2023年第66卷第2期

页      面：297-298页

核心收录：

学科分类：0808[工学-电气工程] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：supported in part by National Natural Science Foundation of China (Grant Nos. 61832003, 61872334, 61801459) Strategic Priority Research Program of Chinese Academy of Sciences (Grant No. XDB28000000) 

摘      要：The weight decision problem, which requires determining the Hamming weight of a given binary string, is a natural and important problem with lots of applications, such as cryptanalysis [1] and coding theory. In this study, we investigate the exact quantum query complexity of weight decision problems, where the exact quantum algorithm must always output the correct answer within finite steps(see Appendix A for a detailed explanation).