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

Quantum Information Processing

A new sure-success generalization of Grover iteration and its application to weight decision problem of Boolean functions

Kıvanç Uyanık, S. Turgut

Published Jul 1, 2013• 1 citation
Publisher
DOI
10.1007/s11128-013-0606-9

Related papers

Application of Grover’s algorithm to check non-resiliency of a Boolean function

Kaushik Chakraborty, Subhamoy Maitra

Cryptography and Communications•Aug 17, 2015•10 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.

arXiv:1301.4461•Jan 18, 2013•0 citations

A quantum algorithm for approximating the influences of Boolean functions and its applications

Hongwei Li, Li Yang

arXiv:1409.1416•Quantum Information Processing•Mar 4, 2015•31 citations

Optimality proofs of quantum weight decision algorithms

Byung-Soo Choi

Quantum Information Processing•Mar 10, 2011•5 citations

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•18 citations

Quantum algorithm for the asymmetric weight decision problem and its generalization to multiple weights

Byung-Soo Choi, Samuel L. Braunstein

Quantum Information Processing•Jul 12, 2010•7 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.