×

Exact quantum algorithm to distinguish Boolean functions of different weights. (English) Zbl 1117.81016

Summary: 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 \(\{w_1 =\sin^2(\frac{k}{2k+1}\,\frac\pi2)\), \(w_2=\cos^2(\frac{2}{2k+1}\,\frac\pi2)\}\) for an 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 \(\Omega(k2)\) 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.

MSC:

81P68 Quantum computation
PDFBibTeX XMLCite
Full Text: DOI arXiv