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:quant-ph/0410043 · Journal of Physics A Mathematical and Theoretical

Exact quantum algorithm to distinguish Boolean functions of different weights

Samuel L. Braunstein, Byung-Soo Choi, Subhroshekhar Ghosh, Subhamoy Maitra

Published Jul 3, 2007• 17 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1088/1751-8113/40/29/017

Related papers

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

Exact Quantum Query Complexity of the Five-Bit Symmetric Boolean Function $\Exact^5_{3,4}$

Guoliang Xu, Haoran Zhang, Mengfan Wu +2 more

Let \(f = \text{EXACT}^5_{3,4}\) be the Boolean function that equals 1 exactly on inputs of Hamming weight 3 or 4. Earlier numerical studies reported success probabilities close to one using three queries, but the existence of an exact three-query algorithm had remained unresolved. This paper settles this problem by proving that the exact quantum query complexity of \(f\) is \(4\). For the lower bound, we express every three-query algorithm through layer-by-layer Gram matrices of low-degree Fourier coefficients. We then construct a fixed rational dual certificate whose slack matrices are all positive definite. This certificate separates the necessary Gram-matrix region from the exact-output condition and therefore rules out every exact algorithm using at most three queries in the stated model. The positivity verification reduces to five small rational matrices and Sylvester's criterion. For the upper bound, we invoke the previously known four-query algorithm for the seven-bit function \(\text{EXACT}^7_{3,4}\) and apply the standard padding reduction. To quantify the near-exact behavior, we use the same certificate to derive a valid, though not claimed tight, lower bound \(\frac{25600}{43779488192449}>0\) on the worst-case error of every algorithm using at most three queries. This positive error gap is compatible with the near-unit success probabilities reported in earlier numerical studies, which do not establish exact computation.

quant-pharXiv:2610.24518•Oct 20, 2026•0 citations

Quantum algorithms for testing and learning Boolean functions

Dominik Floess, Erika Andersson, Mark S. Hillery

We discuss quantum algorithms based on the Bernstein–Vazirani algorithm for finding which input variables a Boolean function depends on. There are 2 n possible linear Boolean functions of n input 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. We show how the same quantum algorithm can also be used to learn which input variables any other type of Boolean function} depends on. The success probability of learning that the function depends on a particular input variable 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 based on another quantum algorithm, the Grover search, to amplify further the success probability. Finally, we discuss quantum algorithms for learning the exact form of certain quadratic and cubic Boolean functions.

Mathematical Structures in Computer Science•Feb 28, 2013•8 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

An improved quantum query algorithm for computing AND Boolean function

Alina Vasilieva, Taisia Mischenko-Slatenkova

We consider the quantum query model for computing Boolean functions. The definition of the function is known, but a black box contains the input X = (x1, x2, ..., xn). Black box can be accessed by querying xivalues. The goal is to develop an algorithm, which would compute the function value for arbitrary input using as few queries to the black box as possible. We present two different quantum query algorithms for computing the basic Boolean function - logical AND of two bits. Both algorithms use only one query to determine the function value. Correct answer probability for the first algorithm is 80%, but for the second algorithm it is 90%. To compute this function with the same probability in the classical model, two queries are necessary. We analyze algorithms implementation differences and propose a way to extend the first algorithm to compute AND of two functions.

IEEE Congress on Evolutionary Computation (CEC)•Jul 1, 2010•0 citations

Quantum algorithms for weighted constrained sampling and weighted model counting

Fabrizio Riguzzi

Abstract We consider the problems of weighted constrained sampling and weighted model counting, where we are given a propositional formula and a weight for each world. The first problem consists of sampling worlds with a probability proportional to their weight given that the formula is satisfied. The latter is the problem of computing the sum of the weights of the models of the formula. Both have applications in many fields such as probabilistic reasoning, graphical models, statistical physics, statistics, and hardware verification. In this article, we propose quantum weighted constrained sampling (QWCS) and quantum weighted model counting (QWMC), two quantum algorithms for performing weighted constrained sampling and weighted model counting, respectively. Both are based on the quantum search/quantum model counting algorithms that are modified to take into account the weights. In the black box model of computation, where we can only query an oracle for evaluating the Boolean function given an assignment, QWCS requires $$O(2^{\frac{n}{2}}+1/\sqrt{\text {WMC}})$$ O ( 2 n 2 + 1 / WMC ) oracle calls, where n is the number of Boolean variables and $$\text {WMC}$$ WMC is the normalized between 0 and 1 weighted model count of the formula, while a classical algorithm has a complexity of $$\Omega (1/\text {WMC})$$ Ω ( 1 / WMC ) . QWMC takes $$\Theta (2^{\frac{n}{2}})$$ Θ ( 2 n 2 ) oracle calss, while classically the best complexity is $$\Theta (2^n)$$ Θ ( 2 n ) , thus achieving a quadratic speedup.

arXiv:2407.12816•Quantum Machine Intelligence•Nov 5, 2024•2 citations
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.
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.
Let f=EXACT3,45f = \text{EXACT}^5_{3,4}f=EXACT3,45​ be the Boolean function that equals 1 exactly on inputs of Hamming weight 3 or 4. Earlier numerical studies reported success probabilities close to one using three queries, but the existence of an exact three-query algorithm had remained unresolved. This paper settles this problem by proving that the exact quantum query complexity of fff is 444. For the lower bound, we express every three-query algorithm through layer-by-layer Gram matrices of low-degree Fourier coefficients. We then construct a fixed rational dual certificate whose slack matrices are all positive definite. This certificate separates the necessary Gram-matrix region from the exact-output condition and therefore rules out every exact algorithm using at most three queries in the stated model. The positivity verification reduces to five small rational matrices and Sylvester's criterion. For the upper bound, we invoke the previously known four-query algorithm for the seven-bit function EXACT3,47\text{EXACT}^7_{3,4}EXACT3,47​ and apply the standard padding reduction. To quantify the near-exact behavior, we use the same certificate to derive a valid, though not claimed tight, lower bound 2560043779488192449>0\frac{25600}{43779488192449}>04377948819244925600​>0 on the worst-case error of every algorithm using at most three queries. This positive error gap is compatible with the near-unit success probabilities reported in earlier numerical studies, which do not establish exact computation.
We discuss quantum algorithms based on the Bernstein–Vazirani algorithm for finding which input variables a Boolean function depends on. There are 2 n possible linear Boolean functions of n input 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. We show how the same quantum algorithm can also be used to learn which input variables any other type of Boolean function} depends on. The success probability of learning that the function depends on a particular input variable 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 based on another quantum algorithm, the Grover search, to amplify further the success probability. Finally, we discuss quantum algorithms for learning the exact form of certain quadratic and cubic Boolean functions.
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.
We consider the quantum query model for computing Boolean functions. The definition of the function is known, but a black box contains the input X = (x1, x2, ..., xn). Black box can be accessed by querying xivalues. The goal is to develop an algorithm, which would compute the function value for arbitrary input using as few queries to the black box as possible. We present two different quantum query algorithms for computing the basic Boolean function - logical AND of two bits. Both algorithms use only one query to determine the function value. Correct answer probability for the first algorithm is 80%, but for the second algorithm it is 90%. To compute this function with the same probability in the classical model, two queries are necessary. We analyze algorithms implementation differences and propose a way to extend the first algorithm to compute AND of two functions.
Abstract We consider the problems of weighted constrained sampling and weighted model counting, where we are given a propositional formula and a weight for each world. The first problem consists of sampling worlds with a probability proportional to their weight given that the formula is satisfied. The latter is the problem of computing the sum of the weights of the models of the formula. Both have applications in many fields such as probabilistic reasoning, graphical models, statistical physics, statistics, and hardware verification. In this article, we propose quantum weighted constrained sampling (QWCS) and quantum weighted model counting (QWMC), two quantum algorithms for performing weighted constrained sampling and weighted model counting, respectively. Both are based on the quantum search/quantum model counting algorithms that are modified to take into account the weights. In the black box model of computation, where we can only query an oracle for evaluating the Boolean function given an assignment, QWCS requires O(2n2+1/WMC)O(2^{\frac{n}{2}}+1/\sqrt{\text {WMC}})O(22n​+1/WMC​) O ( 2 n 2 + 1 / WMC ) oracle calls, where n is the number of Boolean variables and WMC\text {WMC}WMC WMC is the normalized between 0 and 1 weighted model count of the formula, while a classical algorithm has a complexity of Ω(1/WMC)\Omega (1/\text {WMC})Ω(1/WMC) Ω ( 1 / WMC ) . QWMC takes Θ(2n2)\Theta (2^{\frac{n}{2}})Θ(22n​) Θ ( 2 n 2 ) oracle calss, while classically the best complexity is Θ(2n)\Theta (2^n)Θ(2n) Θ ( 2 n ) , thus achieving a quadratic speedup.