Exact quantum algorithm to distinguish Boolean functions of different weights

Braunstein, S.L., Choi, B.-S., Ghosh, S. and Maitra, S.
(2007): Journal of Physics A 40, 8441-8454 (PDF)

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₁ and w₂ satisfying a general weight condition as w₁ + w₂ = 1 and 0 < w₁ < w₂ < 1. First, we propose a limited weight-decision algorithm where the function has another constraint: a weight is in $\big\{w_1= \sin^2\!\big(\frac{k}{2k+1}\frac{\pi}{2}\big), w_2= \cos^2\big(\frac{k}{2k+1}\frac{\pi}{2}\big)\big\}$ 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²) 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.