超越 n/2 阈值：计算汉明重量与对称函数的量子查询复杂度
Beyond the $n/2$ Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions
Yuan Deng, Zihan Hao, Honghao Lin, Qipeng Liu, Vahab Mirrokni, Jianan Shao, David P. Woodruff
AI 速读 基于摘要
作者构造了一类需要 n/2+Ω(n^{1/3}) 次量子查询的对称布尔函数，并给出用 n/2+O(n^{1/3}) 次查询精确恢复汉明重量的算法，从而确定该加性阶数的最优性。
quant-ph · cs.CC
查看原文摘要
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 with bounded error, and therefore computes every symmetric Boolean function within the same query bound. Together, these results determine the optimal additive order for Hamming weight recovery and for the worst case over symmetric Boolean functions at sufficiently small constant error.