Exact quantum query complexity of computing Hamming weight modulo powers of two and three

Arjan Cornelissen, Nikhil S. Mande, Maris Ozols +1

We study the problem of computing the Hamming weight of an $n$-bit string modulo $m$, for any positive integer $m\le n$ whose only prime factors are 2 and 3. We show that the exa…