We study the problem of computing the Hamming weight of an
n-bit string modulo
m, for any positive integer
m≤n whose only prime factors are 2 and 3. We show that the exact quantum query complexity of this problem is
⌈n(1−1/m)⌉. The upper bound is via an iterative query algorithm whose core components are the well-known 1-query quantum algorithm (essentially due to Deutsch) to compute the Hamming weight a 2-bit string mod 2 (i.e., the parity of the input bits), and a new 2-query quantum algorithm to compute the Hamming weight of a 3-bit string mod 3. We show a matching lower bound (in fact for arbitrary moduli
m) via a variant of the polynomial method [de Wolf, SIAM J. Comput., 32(3), 2003]. This bound is for the weaker task of deciding whether or not a given
n-bit input has Hamming weight 0 modulo
m, and it holds even in the stronger non-deterministic quantum query model where an algorithm must have positive acceptance probability iff its input evaluates to 1. For
m>2 our lower bound exceeds
n/2, beating the best lower bound provable using the general polynomial method [Theorem 4.3, Beals et al., J. ACM 48(4), 2001].
Deutsch–Jozsa problem (D–J) has exact quantum 1-query complexity (“exact” means no error), but requires super-exponential queries for the optimal classical deterministic decision trees. D–J problem is equivalent to a symmetric partial Boolean function, and in fact, all symmetric partial Boolean functions having exact quantum 1-query complexity have been found out and these functions can be computed by D–J algorithm. A special case is that all symmetric Boolean functions with exact quantum 1-query complexity follow directly and these functions are also all total Boolean functions with exact quantum 1-query complexity obviously. Then there are pending problems concerning partial Boolean functions having exact quantum 1-query complexity and new results have been found, but some problems are still open. In this paper, we review these results regarding exact quantum 1-query complexity and in particular, we also obtain a new result that a partial Boolean function with exact quantum 1-query complexity is constructed and it cannot be computed by D–J algorithm. Further problems are pointed out for future study.