摘要
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.
基金
supported by the National Natural Science Foundation of China(Grant Nos.62332009,12347104,and 61972191)
the Innovation Program for Quantum Science and Technology(2021ZD0302901).
