Penghui YAO, Zekun YE
In this paper, we consider the exact quantum query complexity of two fundamental symmetric functions. 1) , which calculates the Hamming weight of an -bit string modulo ; 2) , which determines if the Hamming weight of an -bit string is exactly or . 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 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 exactly for some specific values of and , we give a tight characterization of its exact quantum query complexity in these scenarios.