Beyond the $n/2$ Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions

Yuan Deng, Zihan Hao, Honghao Lin +4

The oracle-interrogation algorithm [van Dam, FOCS '98] computes every $n$-bit Boolean function with bounded error using $n/2+O(\sqrt{n})$ quantum queries. In contrast, parity can be…