Abstract Quantum counting is one of the well-known problems in which the application of quantum parallelism speeds up computations. Different authors suggest different estimates for the success probability of a quantum counting algorithm. Moreover, some authors use the direct quantum Fourier transform, while others, the inverse quantum Fourier transform in the quantum counting algorithm. The present paper demonstrates the results of mathematical simulation of the application of the quantum counting algorithm to estimate the weights of some Boolean functions, depending on six variables, in a quantum simulator Quipper to verify known estimates of the success probability of the quantum counting algorithm.
Abstract Quantum counting is one of the well-known problems in which the application of quantum parallelism speeds up computations. Different authors suggest different estimates for the success probability of a quantum counting algorithm. Moreover, some authors use the direct quantum Fourier transform, while others, the inverse quantum Fourier transform in the quantum counting algorithm. The present paper demonstrates the results of mathematical simulation of the application of the quantum counting algorithm to estimate the weights of some Boolean functions, depending on six variables, in a quantum simulator Quipper to verify known estimates of the success probability of the quantum counting algorithm.
In Weighted Model Counting (WMC) we assign weights to Boolean literals and we want to compute the sum of the weights of the models of a Boolean function where the weight of a model is the product of the weights of its literals.WMC was shown to be particularly effective for performing inference in graphical models, with a complexity of O(n2 w ) where n is the number of variables and w is the treewidth.In this paper, we propose a quantum algorithm for performing WMC, Quantum WMC (QWMC), that modifies the quantum model counting algorithm to take into account the weights.In turn, the model counting algorithm uses the algorithms of quantum search, phase estimation and Fourier transform.In the black box model of computation, where we can only query an oracle for evaluating the Boolean function given an assignment, QWMC solves the problem approximately with a complexity of Θ(2 n 2 ) oracle calls while classically the best complexity is Θ(2 n ), thus achieving a quadratic speedup.
In Weighted Model Counting (WMC) we assign weights to Boolean literals and we want to compute the sum of the weights of the models of a Boolean function where the weight of a model is the product of the weights of its literals. WMC was shown to be particularly effective for performing inference in graphical models, with a complexity of O(n2w) where n is the number of variables and w is the treewidth. In this paper, we propose a quantum algorithm for performing WMC, Quantum WMC (QWMC), that modifies the quantum model counting algorithm to take into account the weights. In turn, the model counting algorithm uses the algorithms of quantum search, phase estimation and Fourier transform. In the black box model of computation, where we can only query an oracle for evaluating the Boolean function given an assignment, QWMC solves the problem approximately with a complexity of Θ(22n) oracle calls while classically the best complexity is Θ(2n), thus achieving a quadratic speedup.
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(22n+1/WMC) O ( 2 n 2 + 1 / WMC ) oracle calls, where n is the number of Boolean variables and 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) Ω ( 1 / WMC ) . QWMC takes Θ(22n) Θ ( 2 n 2 ) oracle calss, while classically the best complexity is Θ(2n) Θ ( 2 n ) , thus achieving a quadratic speedup.
A quantum algorithm for the computation the order of an integer, which uses the quantum Fourier transform, is discussed. The cases of the exact and approximate Fourier transform are considered, and estimates of the probability of the successful solution of the problem that significantly improve the available results are obtained. The quantum algorithm for order finding is simulated using the QuantumCircuit package written in the computer algebra system Wolfram Mathematica , and its efficiency in combination with the approximate Fourier transform is demonstrated.
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 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.