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(n) quantum queries. In contrast, parity can be computed exactly using ⌈n/2⌉ 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+Ω(n1/3) quantum queries at a fixed positive constant error. We also give an algorithm that recovers the exact Hamming weight using n/2+O(n1/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.
We give and prove an optimal exact quantum query algorithm with complexity k+1 for computing the promise problem (i.e., symmetric and partial Boolean function) DJnk defined as: DJnk(x)=1 for ∣x∣=n/2, DJnk(x)=0 for ∣x∣ in the set {0,1,…,k,n−k,n−k+1,…,n}, and it is undefined for the rest cases, where n is even, ∣x∣ is the Hamming weight of x. The case of k=0 is the well-known Deutsch-Jozsa problem. We outline all symmetric (and partial) Boolean functions with degrees 1 and 2, and prove their exact quantum query complexity. Then we prove that any symmetrical (and partial) Boolean function f has exact quantum 1-query complexity if and only if f can be computed by the Deutsch-Jozsa algorithm. We also discover the optimal exact quantum 2-query complexity for distinguishing between inputs of Hamming weight {⌊n/2⌋,⌈n/2⌉} and Hamming weight in the set {0,n} for all odd n. In addition, a method is provided to determine the degree of any symmetrical (and partial) Boolean function.
This paper considers the query complexity of the functions in the family F_{N,M} of N-variable Boolean functions with onset size M, i.e., the number of inputs for which the function value is 1, where 1<= M <= 2^{N}/2 is assumed without loss of generality because of the symmetry of function values, 0 and 1. Our main results are as follows: (1) There is a super-linear gap between the average-case and worst-case quantum query complexities over F_{N,M} for a certain range of M. (2) There is no super-linear gap between the average-case and worst-case randomized query complexities over F_{N,M} for every M. (3) For every M bounded by a polynomial in N, any function in F_{N,M} has quantum query complexity Theta (sqrt{N}). (4) For every M=O(2^{cN}) with an arbitrary large constant c<1, any function in F_{N,M} has randomized query complexity Omega (N).
Approximating the Influence of Monotone Boolean Functions in O(n) Query Complexity