(2007):

ABSTRACT:
In this work, we exploit the Grover operator for the weight analysis of a
Boolean function, specifically to solve the weight-decision problem. The
weight *w* is the fraction of all possible inputs for which the
output is 1. The goal of the weight-decision problem is to find the exact
weight *w* from the given two weights *w*_{1} and
*w*_{2} satisfying a general weight condition as
*w*_{1} + *w*_{2} = 1 and 0 <
*w*_{1} < *w*_{2} < 1. First, we propose
a limited weight-decision algorithm where the function has another
constraint: a weight is in for integer
*k*. Second, by changing the phases in the last two Grover iterations,
we propose a general weight-decision algorithm which is free from the above
constraint. Finally, we show that when our algorithm requires
*O*(*k*) queries to find *w* with a unit success probability,
any classical algorithm requires at least Ω(*k*^{2})
queries for a unit success probability. In addition, we show that our
algorithm requires fewer queries to solve this problem compared with the
quantum counting algorithm.