  We study the problem of computing the Hamming weight of an $n$-bit string
modulo $m$, for any positive integer $m \leq n$ whose only prime factors are 2
and 3. We show that the exact quantum query complexity of this problem is
$\left\lceil n(1 - 1/m) \right\rceil$. 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].

Quantum Physics;Computational Complexity;Data Structures and Algorithms