On the exact quantum query complexity of MOD and EXACT functions  

作　　者：Penghui YAO Zekun YE 

机构地区：[1]State Key Laboratory for Novel Software Technology,Nanjing University,Nanjing 210023,China [2]Hefei National Laboratory,Hefei 230088,China

出　　处：《Frontiers of Computer Science》2025年第4期91-98,共8页计算机科学前沿(英文版)

基　　金：supported by the National Natural Science Foundation of China(Grant Nos.62332009,12347104,and 61972191);the Innovation Program for Quantum Science and Technology(2021ZD0302901).

摘　　要：In this paper,we consider the exact quantum query complexity of two fundamental symmetric functions.1)MOD_(m)^(n),which calculates the Hamming weight of an-bit string modulo;2)EXACT_(k,l)^(n),which determines if the Hamming weight of an-bit string is exactly k or l.Although these two symmetric functions have received considerable attention,their exact quantum query complexities have not been fully characterized.Specifically,our results are as follows:1)We design an optimal quantum query algorithm to compute MOD_(m)^(n)exactly and thus provide a tight characterization of its exact quantum query complexity,which settles a previous conjecture.Based on this algorithm,we demonstrate that a broad class of symmetric functions is not evasive in the quantum model,i.e.,there exist quantum algorithms to compute these functions exactly when the number of queries is less than their input size.2)By proposing a quantum algorithm that utilizes the minimum number of queries to compute EXACT_(k,l)^(n)exactly for some specific values of k and l,we give a tight characterization of its exact quantum query complexity in these scenarios.

关 键 词：quantum computing query complexity symmetric functions exact algorithms evasiveness 

分 类 号：O413[理学—理论物理]