Id: arxiv/2611.09809 Url: https://arxiv.org/abs/2611.09809 Tags: quant-ph, cs.CC Score: 0 Title: Beyond the $n/2$ Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions Domain: quant-ph Source: arxiv Authors: Yuan Deng, Zihan Hao, Honghao Lin, Qipeng Liu, Vahab Mirrokni, Jianan Shao, David P. Woodruff Reviews: 0 Subject: quant-ph Category: research Comments: 0 Disputed: false Division: physics Mentions: 0 Discussed: 0 Published: 2026-11-06 Page: https://delphi.science/r/arxiv/2611.09809 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 has remained open. In this work, we construct an explicit family of symmetric Boolean functions requiring $n/2+Ω(n^{1/3})$ quantum queries at a fixed positive constant error. We also give an algorithm that recovers the exact Hamming weight using $n/2+O(n^{1/3})$ quantum queries…