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:2407.12816 · Quantum Machine Intelligence

Quantum algorithms for weighted constrained sampling and weighted model counting

Fabrizio Riguzzi

Published Nov 5, 2024• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1007/s42484-024-00209-5

Related papers

Quantum Weighted Model Counting

Fabrizio Riguzzi

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.

Frontiers in artificial intelligence and applications•Jan 1, 2020•3 citations

Quantum Weighted Model Counting

Fabrizio Riguzzi

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^{\frac{n}{2}})$ oracle calls while classically the best complexity is $Θ(2^n)$, thus achieving a quadratic speedup.

arXiv:1910.13530•Oct 22, 2019•0 citations

Quantum Approximate Counting with Bernoulli Oracles

Chengshen Gao, Yongzhen Xu, Lvzhou Li

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 $p_1,\dots,p_m$ and a gap parameter $Δ$, the goal is to estimate the fraction $ρ$ of \emph{positive} distributions ($p_i\ge1/2+Δ$) to within additive error $ε$. We prove an upper bound of $\tilde{O}\!\big(\frac{\sqrtρ}{Δε}+\frac{1}{Δ\sqrtε}\big)$ 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 $Ω(\sqrtρ/(Δε))$ 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 $\tilde{O}\big(\frac{\sqrtρ}ε+\frac{1}{\sqrtε}\big)$ and $Ω(\frac{\sqrtρ}ε)$, thereby characterizing the query complexity of quantum counting with bounded-error oracles.

quant-pharXiv:2609.07604•Sep 8, 2026•0 citations

Quantum physics using weighted model counting

Dirck van den Ende, Joon‐Hyung Lee, Alfons Laarman +1 more

Abstract Weighted model counting (WMC) has proven effective at a range of tasks within computer science, physics, and beyond. However, existing approaches for using WMC in quantum physics only target specific problem instances, lacking a general framework for expressing problems using WMC. This limits the reusability of these approaches in other applications and risks a lack of mathematical rigor on a per-instance basis. We present an approach for expressing linear algebraic problems, specifically those present in physics and quantum computing, as WMC instances. We do this by introducing a framework that converts Dirac notation to WMC problems, which comprise of a formula with weighted variables. This approach preserves the structural and sparsity information of a problem, while giving access to efficient, general purpose model counting implementations. We build up this framework theoretically, using a type system and denotational semantics, and provide an implementation in Python. We demonstrate the effectiveness of our framework in calculating the partition functions of several physical models: The transverse-field Ising model (quantum) and the Potts model (classical). The results suggest that automated reasoning heuristics, including clause learning, algebraic decision diagrams, and tensor network decomposition, can be systematically applied through a single unified framework to a wide class of quantum physics problems, including those requiring non-commuting operators, without problem-specific solver engineering. The framework naturally supports complex-valued weights through a reduction to real-valued WMC instances, broadening its applicability to a wider class of quantum models.

arXiv:2508.21288•Journal of Physics A Mathematical and Theoretical•Nov 4, 2026•2 citations

BQP, Meet NP: Search-To-Decision Reductions and Approximate Counting

Sevag Gharibian, Jonas Kamminga

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 $Θ(\log n)$ 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 $Ω(\log n)$ 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 $Ω(\log n)$ 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(log n)$ NP queries, then $\text{BPP}^{\text{NP}[o(n)]}$ contains a $\text{P}^{\text{NP}}$-complete problem if the algorithm is classical and $\text{FBQP}^{\text{NP}[o(n)]}$ contains an $\text{FP}^{\text{NP}}$-complete problem if the algorithm is quantum.

arXiv:2401.03943•Leibniz international proceedings in informatics•Jan 1, 2024•3 citations

Quantum algorithms for exponential sums and the evaluation of the Riemann zeta function

Sandeep Tyagi

We give quantum algorithms for estimating weighted exponential sums $S(f,w,N)= \sum_{k=0}^{N-1} w_k e^{2 πi f(k)}$, with $w_k \ge 0$, $\sum_k w_k =1$, and $N=2^{n}$ exponentially large. Under two explicit oracle assumptions -- efficiently computable prefix sums for the weights, enabling Grover--Rudolph state preparation, and a fixed-point circuit for $f$ -- amplitude estimation yields $S$ to additive error $\varepsilon$ with $O(\varepsilon^{-1}\log(1/γ))$ oracle uses and $\operatorname{polylog}(N)$ gates per use; all bounds are full gate complexities, and the saving over classical sampling is quadratic in $1/\varepsilon$. Applying this to the Riemann--Siegel formula, we prove that $ζ(σ+it)$ in the critical strip can be estimated to accuracy $δ$ with $\widetilde O(t^{(1-σ)/2}\, δ^{-1})$ gates, hence $\widetilde O(t^{1/4}\, δ^{-1})$ on the critical line, where $\widetilde O$ suppresses factors polylogarithmic in $t/δ$. At fixed accuracy this improves on the $t^{1/2}$ Riemann--Siegel cost and on the best rigorous classical algorithm's $t^{4/13+o(1)}$; the quantum algorithm is advantageous precisely when $δ\gg t^{-3/52}$, which covers the accuracy needed to locate and count zeros. We show that a $\operatorname{polylog}(t)$ algorithm does not follow from these techniques -- undoing the normalization costs the $\ell^{1}$ mass $\sum_{k\le N} k^{-σ} = Θ(t^{(1-σ)/2})$ of the main sum -- and that Hiary-type block decompositions cannot improve the quantum query complexity. We also give an estimator for the magnitude of the amplitude sum $\lvert \sum_k a_k \rvert$ of any efficiently preparable state, and review the required amplitude- and phase-estimation subroutines.

arXiv:2002.11094•Feb 25, 2020•0 citations
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.
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)O(n2^w)O(n2w) where nnn is the number of variables and www 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 Θ(2n2)Θ(2^{\frac{n}{2}})Θ(22n​) oracle calls while classically the best complexity is Θ(2n)Θ(2^n)Θ(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 mmm Bernoulli distributions with unknown biases p1,…,pmp_1,\dots,p_mp1​,…,pm​ and a gap parameter ΔΔΔ, the goal is to estimate the fraction ρρρ of \emph{positive} distributions (pi≥1/2+Δp_i\ge1/2+Δpi​≥1/2+Δ) to within additive error εεε. We prove an upper bound of O~ ⁣(ρΔε+1Δε)\tilde{O}\!\big(\frac{\sqrtρ}{Δε}+\frac{1}{Δ\sqrtε}\big)O~(Δερ​​+Δε​1​) queries, achieving a quadratic speedup over the classical sample complexity. % of Θ(ρ/Δ2ε2)Θ(ρ/Δ^2ε^2)Θ(ρ/Δ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 Ω(ρ/(Δε))Ω(\sqrtρ/(Δε))Ω(ρ​/(Δε)) 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)Δ=Θ(1)Δ=Θ(1), which corresponds to the bounded-error oracle where each query returns the correct label with constant probability, our bounds specialize to O~(ρε+1ε)\tilde{O}\big(\frac{\sqrtρ}ε+\frac{1}{\sqrtε}\big)O~(ερ​​+ε​1​) and Ω(ρε)Ω(\frac{\sqrtρ}ε)Ω(ερ​​), thereby characterizing the query complexity of quantum counting with bounded-error oracles.
Abstract Weighted model counting (WMC) has proven effective at a range of tasks within computer science, physics, and beyond. However, existing approaches for using WMC in quantum physics only target specific problem instances, lacking a general framework for expressing problems using WMC. This limits the reusability of these approaches in other applications and risks a lack of mathematical rigor on a per-instance basis. We present an approach for expressing linear algebraic problems, specifically those present in physics and quantum computing, as WMC instances. We do this by introducing a framework that converts Dirac notation to WMC problems, which comprise of a formula with weighted variables. This approach preserves the structural and sparsity information of a problem, while giving access to efficient, general purpose model counting implementations. We build up this framework theoretically, using a type system and denotational semantics, and provide an implementation in Python. We demonstrate the effectiveness of our framework in calculating the partition functions of several physical models: The transverse-field Ising model (quantum) and the Potts model (classical). The results suggest that automated reasoning heuristics, including clause learning, algebraic decision diagrams, and tensor network decomposition, can be systematically applied through a single unified framework to a wide class of quantum physics problems, including those requiring non-commuting operators, without problem-specific solver engineering. The framework naturally supports complex-valued weights through a reduction to real-valued WMC instances, broadening its applicability to a wider class of quantum models.
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)Θ(n)Θ(n) queries to an NP oracle to compute a witness to a given SAT formula, quantumly Θ(log⁡n)Θ(\log n)Θ(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 Ω(log⁡n)Ω(\log n)Ω(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 Ω(log⁡n)Ω(\log n)Ω(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)o(log n)o(logn) NP queries, then BPPNP[o(n)]\text{BPP}^{\text{NP}[o(n)]}BPPNP[o(n)] contains a PNP\text{P}^{\text{NP}}PNP-complete problem if the algorithm is classical and FBQPNP[o(n)]\text{FBQP}^{\text{NP}[o(n)]}FBQPNP[o(n)] contains an FPNP\text{FP}^{\text{NP}}FPNP-complete problem if the algorithm is quantum.
We give quantum algorithms for estimating weighted exponential sums S(f,w,N)=∑k=0N−1wke2πif(k)S(f,w,N)= \sum_{k=0}^{N-1} w_k e^{2 πi f(k)}S(f,w,N)=∑k=0N−1​wk​e2πif(k), with wk≥0w_k \ge 0wk​≥0, ∑kwk=1\sum_k w_k =1∑k​wk​=1, and N=2nN=2^{n}N=2n exponentially large. Under two explicit oracle assumptions -- efficiently computable prefix sums for the weights, enabling Grover--Rudolph state preparation, and a fixed-point circuit for fff -- amplitude estimation yields SSS to additive error ε\varepsilonε with O(ε−1log⁡(1/γ))O(\varepsilon^{-1}\log(1/γ))O(ε−1log(1/γ)) oracle uses and polylog⁡(N)\operatorname{polylog}(N)polylog(N) gates per use; all bounds are full gate complexities, and the saving over classical sampling is quadratic in 1/ε1/\varepsilon1/ε. Applying this to the Riemann--Siegel formula, we prove that ζ(σ+it)ζ(σ+it)ζ(σ+it) in the critical strip can be estimated to accuracy δδδ with O~(t(1−σ)/2 δ−1)\widetilde O(t^{(1-σ)/2}\, δ^{-1})O(t(1−σ)/2δ−1) gates, hence O~(t1/4 δ−1)\widetilde O(t^{1/4}\, δ^{-1})O(t1/4δ−1) on the critical line, where O~\widetilde OO suppresses factors polylogarithmic in t/δt/δt/δ. At fixed accuracy this improves on the t1/2t^{1/2}t1/2 Riemann--Siegel cost and on the best rigorous classical algorithm's t4/13+o(1)t^{4/13+o(1)}t4/13+o(1); the quantum algorithm is advantageous precisely when δ≫t−3/52δ\gg t^{-3/52}δ≫t−3/52, which covers the accuracy needed to locate and count zeros. We show that a polylog⁡(t)\operatorname{polylog}(t)polylog(t) algorithm does not follow from these techniques -- undoing the normalization costs the ℓ1\ell^{1}ℓ1 mass ∑k≤Nk−σ=Θ(t(1−σ)/2)\sum_{k\le N} k^{-σ} = Θ(t^{(1-σ)/2})∑k≤N​k−σ=Θ(t(1−σ)/2) of the main sum -- and that Hiary-type block decompositions cannot improve the quantum query complexity. We also give an estimator for the magnitude of the amplitude sum ∣∑kak∣\lvert \sum_k a_k \rvert∣∑k​ak​∣ of any efficiently preparable state, and review the required amplitude- and phase-estimation subroutines.