  The weight decision problem, which requires to determine the Hamming weight
of a given binary string, is a natural and important problem, with applications
in cryptanalysis, coding theory, fault-tolerant circuit design and so on. In
particular, both Deutsch-Jozsa problem and Grover search problem can be
interpreted as special cases of weight decision problems. In this work, we
investigate the exact quantum query complexity of weight decision problems,
where the quantum algorithm must always output the correct answer. More
specifically we consider a partial Boolean function which distinguishes whether
the Hamming weight of the length-$n$ input is $k$ or it is $l$. Our
contribution includes both upper bounds and lower bounds for the precise number
of queries. Furthermore, for most choices of $(\frac{k}{n},\frac{l}{n})$ and
sufficiently large $n$, the gap between our upper and lower bounds is no more
than one. To get the results, we first build the connection between Chebyshev
polynomials and our problem, then determine all the boundary cases of
$(\frac{k}{n},\frac{l}{n})$ with matching upper and lower bounds, and finally
we generalize to other cases via a new \emph{quantum padding} technique. This
quantum padding technique can be of independent interest in designing other
quantum algorithms.
