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.
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.
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.
Quantum counting is a fundamental quantum algorithm that estimates the fraction of marked elements using a membership oracle, achieving a quadratic speedup over classical sampling. The membership oracle, however, assumes exact labeling of each element, but this assumption fails when the labels are inherently probabilistic. We study quantum counting with \emph{Bernoulli oracles}, where given m Bernoulli distributions with unknown biases p1,…,pm and a gap parameter Δ, the goal is to estimate the fraction ρ of \emph{positive} distributions (pi≥1/2+Δ) to within additive error ε. We prove an upper bound of O~(Δερ+Δε1) queries, achieving a quadratic speedup over the classical sample complexity. % of Θ(ρ/Δ2ε2).
Our algorithm first uses the Quantum Singular Value Transformation (QSVT) to coherently amplify the bias gap without collapsing the superposition over distributions, and then applies two-stage adaptive amplitude estimation. We complement this upper bound with a near-matching lower bound of Ω(ρ/(Δε)) via a new composition theorem for the quantum adversary method in the Boolean-over-average-case direction. For the special case of a constant gap Δ=Θ(1), which corresponds to the bounded-error oracle where each query returns the correct label with constant probability, our bounds specialize to O~(ερ+ε1) and Ω(ερ), thereby characterizing the query complexity of quantum counting with bounded-error oracles.
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.
What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires Θ(n) queries to an NP oracle to compute a witness to a given SAT formula, quantumly Θ(logn) queries suffice. We then show this is tight in the black-box model - any quantum algorithm with "NP-like" query access to a formula requires Ω(logn) queries to extract a solution with constant probability. Moving to approximate counting of SAT solutions, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal. First, we give a lower bound in the "NP-like" black-box query setting: Approximate counting requires Ω(logn) queries, even on a quantum computer. We then give a "white-box" lower bound (i.e. where the input formula is not hidden in the oracle) - if there exists a randomized poly-time classical or quantum algorithm for approximate counting making o(logn) NP queries, then BPPNP[o(n)] contains a PNP-complete problem if the algorithm is classical and FBQPNP[o(n)] contains an FPNP-complete problem if the algorithm is quantum.
For a convex function f:Rd→R, the problem of sampling from a distribution proportional to e−f(x) is called log-concave sampling. In many practical scenarios, the function f(x) turns out to admit a local decomposition f(x)=∑a=1Rψa(xSa). In this paper, we consider log-concave sampling using local queries, i.e., evaluation and gradient queries to each clause ψa(⋅), which can be computationally much cheaper than the queries to f(x) itself. We show that if each coordinate appears in only a small number of clauses, there is a quantum algorithm for strongly log-concave sampling using O(κd) local queries, where κ is the condition number. This improves the prior best classical result O(κd) due to Ascolani, Lavenant, and Zanella (Ann. Probab. 2026) and the quantum result O(κd2) implied by Childs et al. (NeurIPS 2022). Our quantum sampler applies to a broad class of locally structured models from statistical computing and machine learning, with representative examples including Gaussian Markov random fields, finite-element latent Gaussian models, and sparse generalized linear models. These results demonstrate that local structure is not merely an implementation detail, but a quantum algorithmic resource for high-dimensional sampling.
We study the quantum query complexity of maximizing a non-negative submodular function, considering both the unconstrained setting and, for monotone functions, a cardinality constraint k on an n-element ground set. In the exact reversible digital value-oracle model, our unconstrained algorithm achieves an expected (1/2−ε)-approximation using only Oε(logn) queries. In contrast, any classical randomized algorithm that attains a fixed expected ratio above 1/4 requires Ω(n/logn) queries (Li, Feldman, Kazemi, and Karbasi, 2022), establishing an exponential separation in query complexity. For cardinality-constrained maximization, we give a bounded-error quantum algorithm that achieves a (1−1/e−ε)-approximation using Oε(min{n,n/k}) queries. When k=o(n), our algorithm achieves at least a quadratic speedup up to logarithmic factors over classical randomized algorithms (Mirzasoleiman, Badanidiyuru, Karbasi, Vondrák, and Krause, 2015; Peng and Rubinstein, 2025). Moreover, when k=cn for any fixed rational c<1−1/e−ε, the query complexity reduces to Oε,c(logn), yielding an exponential separation from the classical Ω(n/logn) lower bound (Li, Feldman, Kazemi, and Karbasi, 2022). We further prove quantum lower bounds of exp(Ω(ε2n)) queries for achieving a ratio beyond 1/2+ε without constraints, and exp(Ω(ε2k)) queries for exceeding 1−1/e+ε when k/n≤ε. These barriers demonstrate that quantum computation offers no exponential speedup at these approximation thresholds.