pith. sign in

arxiv: quant-ph/0410043 · v2 · submitted 2004-10-06 · 🪐 quant-ph

Quantum algorithm to distinguish Boolean functions of different weights

classification 🪐 quant-ph
keywords algorithmgroverweightsfracdecidegivenoperatorquantum
0
0 comments X p. Extension
read the original abstract

We exploit Grover operator of database search algorithm for weight decision algorithm. In this research, weight decision problem is to find an exact weight w from given two weights as w1 and w2 where w1+w2=1 and 0<w1<w2<1. Firstly, if a Boolean function is given and when weights are {1/4,3/4}, we can find w with only one application of Grover operator. Secondly, if we apply k many times of Grover operator, we can decide w from the set of weights {sin^2(\frac{k}{2k+1}\frac{\pi}{2}) cos^2(\frac{k}{2k+1}\frac{\pi}{2})}. Finally, by changing the last two Grover operators with two phase conditions, we can decide w from given any set of two weights. To decide w with a sure success, if the quantum algorithm requires O(k) Grover steps, then the best known classical algorithm requires \Omega(k^s) steps where s>2. Hence the quantum algorithm achieves at least quadratic speedup.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.