Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1301.4461

Sure-Success Quantum Algorithms on Weight Decision Problem

Kıvanç Uyanık, S. Turgut

Published Jan 18, 2013• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1301.4461

Related papers

Exact quantum algorithm to distinguish Boolean functions of different weights

Samuel L. Braunstein, Byung-Soo Choi, Subhroshekhar Ghosh +1 more

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/0410043•Journal of Physics A Mathematical and Theoretical•Jul 3, 2007•17 citations

FORMULATION OF A FAMILY OF SURE-SUCCESS QUANTUM SEARCH ALGORITHMS

Jin-Yuan Hsieh, Che‐Ming Li, Jenn-Sen Lin +1 more

In this work, we consider a family of sure-success quantum algorithms, which is grouped into even and odd members for solving a generalized Grover search problem. We prove the matching conditions for both groups and give the corresponding formulae for evaluating the iterations or oracle calls required in the search computation. We also present how to adjust the phase angles in the generalized Grover operator to ensure the sure-success if minimal oracle calls are demanded in the search.

arXiv:quant-ph/0210201•International Journal of Quantum Information•Aug 30, 2004•2 citations

Family of sure-success quantum algorithms for solving a generalized Grover search problem

Chia-Ren Hu

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 ${\mathcal{A}}_{2n}$ 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.

arXiv:quant-ph/0201049•Physical Review A•Oct 1, 2002•9 citations

Grover's search algorithm for nnn qubits with optimal number of iterations

Simanraj Sadana

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 $\mathcal{O}(\sqrt{N})$ for large $N$, the asymptote is not a good indicator of the optimal number of iterations when $\sqrt{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 \leq M \leq 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.

arXiv:2011.04051•Nov 8, 2020•4 citations

Quantum algorithms for testing Boolean functions

Dominik Floess, Erika Andersson, Mark S. Hillery

We discuss quantum algorithms, based on the Bernstein-Vazirani algorithm, for finding which variables a Boolean function depends on. There are 2^n possible linear Boolean functions of n variables; given a linear Boolean function, the Bernstein-Vazirani quantum algorithm can deterministically identify which one of these Boolean functions we are given using just one single function query. The same quantum algorithm can also be used to learn which input variables other types of Boolean functions depend on, with a success probability that depends on the form of the Boolean function that is tested, but does not depend on the total number of input variables. We also outline a procedure to futher amplify the success probability, based on another quantum algorithm, the Grover search.

arXiv:1006.1423•Electronic Proceedings in Theoretical Computer Science•Jun 9, 2010•16 citations

Kuantum hesaplamayla mantıksal fonksiyonların ağırlıklarının ayırt edilmesi.

Uyanık, Kıvanç

In this thesis, we investigate solvability of the weight decision problem of two Boolean functions by quantum computation. In particular, we study this problem first from a general quantum operator discrimination perspective and second from a direct algorithmic viewpoint. As quantum operator discrimination approach is concerned, we give two different formulations for two different cases. In one, the unitary transformations that correspond to the function evaluation are applied in a parallel fashion and in the other, they are applied only sequentially. Since the parallel case can always be simulated with a serial architecture, we put more emphasis on the serial approach and present a superior result in the serial setting. Specifically we show that any protocol with a serial application of p function evaluations interspersed with p − 1 generic unitary operators in between can be uniquely mapped to a density matrix acting on some other Hilbert space. In the direct approach, we generalize Grover’s iteration in such a way that it can be run deterministically for the discrimination of Boolean functions. We show that sure-success weight distinguishability problem of two Boolean functions using a certain number of evaluations can be reduced to the problem of determining whether a point lies inside the convex hull of a curve. This convex analysis problem is further translated into a system of algebraic equations of a single variable. These equations are solved analytically for the case of single and two evaluations. For more evaluations numerical methods are utilized.

•Jan 1, 2014•0 citations
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{\mathcal{A}}_{2n}A2n​ of the family covers an ever larger range of f for larger n, which is expected to become the full range 0< f< 10<~f<~10< 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 success probability of a search of MMM targets from a database of size NNN, 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)\mathcal{O}(\sqrt{N})O(N​) for large NNN, the asymptote is not a good indicator of the optimal number of iterations when M/N\sqrt{M/N}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 nnn-qubit Grover's search algorithm with 1≤M≤N1 \leq M \leq N1≤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 NNN and MMM, there is an upper-bound on the success probability of the algorithm.
We discuss quantum algorithms, based on the Bernstein-Vazirani algorithm, for finding which variables a Boolean function depends on. There are 2^n possible linear Boolean functions of n variables; given a linear Boolean function, the Bernstein-Vazirani quantum algorithm can deterministically identify which one of these Boolean functions we are given using just one single function query. The same quantum algorithm can also be used to learn which input variables other types of Boolean functions depend on, with a success probability that depends on the form of the Boolean function that is tested, but does not depend on the total number of input variables. We also outline a procedure to futher amplify the success probability, based on another quantum algorithm, the Grover search.
In this thesis, we investigate solvability of the weight decision problem of two Boolean functions by quantum computation. In particular, we study this problem first from a general quantum operator discrimination perspective and second from a direct algorithmic viewpoint. As quantum operator discrimination approach is concerned, we give two different formulations for two different cases. In one, the unitary transformations that correspond to the function evaluation are applied in a parallel fashion and in the other, they are applied only sequentially. Since the parallel case can always be simulated with a serial architecture, we put more emphasis on the serial approach and present a superior result in the serial setting. Specifically we show that any protocol with a serial application of p function evaluations interspersed with p − 1 generic unitary operators in between can be uniquely mapped to a density matrix acting on some other Hilbert space. In the direct approach, we generalize Grover’s iteration in such a way that it can be run deterministically for the discrimination of Boolean functions. We show that sure-success weight distinguishability problem of two Boolean functions using a certain number of evaluations can be reduced to the problem of determining whether a point lies inside the convex hull of a curve. This convex analysis problem is further translated into a system of algebraic equations of a single variable. These equations are solved analytically for the case of single and two evaluations. For more evaluations numerical methods are utilized.