{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-11-06","reactions":{}}