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.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.

arXiv:quant-ph/0410043Journal of Physics A Mathematical and TheoreticalJul 3, 200718 citations

Exact quantum query complexity of weight decision problems.

Xiaoyu He, Xiaoming Sun, Guang Yang +1 more

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.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.

Jan 17, 20183 citations

Quantum Algorithms for Optimization Problems

Dilnoz Muhamediyeva, Rustam Raximov, Shavkat Urokov

Lecture notes in computer scienceJul 29, 20250 citations

Sure-Success Quantum Algorithms on Weight Decision Problem

Kıvanç Uyanık, S. Turgut

Conditions on sure-success decidability of weights of Boolean functions are presented for a given number of generalized Grover iterations. It is shown that the decidability problem reduces to a system of algebraic equations of a single variable. For problems that require a large number of iterations, it is observed that the iteration number of sure-success quantum algorithms scale as the square root of the iteration number of the corresponding classical probabilistic algorithms. It is also demonstrated that for a few iterations, quantum algorithms can be more efficient than this.Conditions on sure-success decidability of weights of Boolean functions are presented for a given number of generalized Grover iterations. It is shown that the decidability problem reduces to a system of algebraic equations of a single variable. For problems that require a large number of iterations, it is observed that the iteration number of sure-success quantum algorithms scale as the square root of the iteration number of the corresponding classical probabilistic algorithms. It is also demonstrated that for a few iterations, quantum algorithms can be more efficient than this.

arXiv:1301.4461Jan 18, 20130 citations

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.