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.
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.
This work considers a generalization of Grover's search problem, viz., to find any one element in a set of acceptable choices which constitute a fraction f of the total number of choices in an unsorted database. An infinite family of sure-success quantum algorithms are introduced here to solve this problem, each member for a different range of f. The nth member of this family involves n queries of the database, and so the lowest few members of this family should be very convenient algorithms within their ranges of validity. The even member A2n of the family covers an ever larger range of f for larger n, which is expected to become the full range 0<f<1 in the limit $\stackrel{\ensuremath{\rightarrow}}{n}\ensuremath{\infty}.$ These algorithms are particularly useful when the cost of failure of a search is very high, and for multistage searches with a different search criterion for each stage.
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 (nk,nl) 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 (nk,nl) 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 success probability of a search of M targets from a database of size N, using Grover's search algorithm depends critically on the number of iterations of the composite operation of the oracle followed by Grover's diffusion operation. Although the required number of iterations scales as O(N) for large N, the asymptote is not a good indicator of the optimal number of iterations when M/N is not small. A scheme for the determination of the exact number of iterations, subject to a threshold set for the success probability of the search (probability of detecting the target state(s)), is crucial for the efficacy of the algorithm. In this work, a general scheme for the construction of n-qubit Grover's search algorithm with 1≤M≤N target states is presented, along with the procedure to find the optimal number of iterations for a successful search. It is also shown that for given N and M, there is an upper-bound on the success probability of the algorithm.
Decision of whether a Boolean equation system has a solution is an NPC problem and finding a solution is NP hard. In this paper, we present a quantum algorithm to decide whether a Boolean equation system FS has a solution and compute one if FS does have solutions with any given success probability. The runtime complexity of the algorithm is polynomial in the size of FS and the condition number of FS. As a consequence, we give a polynomial-time quantum algorithm for solving Boolean equation systems if their condition numbers are small, say polynomial in the size of FS. We apply our quantum algorithm for solving Boolean equations to the cryptanalysis of several important cryptosystems: the stream cipher Trivum, the block cipher AES, the hash function SHA-3/Keccak, and the multivariate public key cryptosystems, and show that they are secure under quantum algebraic attack only if the condition numbers of the corresponding equation systems are large. This leads to a new criterion for designing cryptosystems that can against the attack of quantum computers: their corresponding equation systems must have large condition numbers.