Quantum query limits discovered for symmetric Boolean functions
Beyond the $n/2$ Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions
Computational Complexity
Summary
Some problems in computing require asking many yes-or-no questions to find the answer. Using quantum computers, it was known you could solve any such problem on n bits in about half the number of questions, plus a little extra. But it was unclear if there had to be this extra overhead beyond half. The authors showed certain problems definitely need more than half plus a small amount of questions, and they also gave a method that matches this lower limit for a key problem—counting how many bits are 1 in a string. This helps understand the exact limits of quantum speedups for these problems.
What this means in practice
- •For quantum algorithm designers: Know precise quantum query costs for symmetric Boolean functions to optimize algorithm efficiency.
- •For quantum hardware developers: Plan resource requirements for quantum devices by understanding minimal queries needed for fundamental problems like Hamming weight.
A theory result. No direct application yet.
Authors
Yuan Deng, Zihan Hao, Honghao Lin, Qipeng Liu, Vahab Mirrokni, Jianan Shao, David P. Woodruff
Abstract
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.