Beyond the $n/2$ Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions
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 computed exactly using $\lceil n/2\rceil$ queries, but whether an additive overhead beyond $n/2$ is necessary for a single Boolean output ha...