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:2508.21288 · Journal of Physics A Mathematical and Theoretical

Quantum physics using weighted model counting

Dirck van den Ende, Joon‐Hyung Lee, Alfons Laarman, Henning Basold

Published Nov 4, 2026• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1088/1751-8121/aebddc

Related papers

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

Equivalence Checking of Quantum Circuits by Model Counting

Jingyi Mei, Tim J. Coopmans, Marcello Bonsangue +1 more

Abstract Verifying equivalence between two quantum circuits is a hard problem, that is nonetheless crucial in compiling and optimizing quantum algorithms for real-world devices. This paper gives a Turing reduction of the (universal) quantum circuits equivalence problem to weighted model counting (WMC). Our starting point is a folklore theorem showing that equivalence checking of quantum circuits can be done in the so-called Pauli-basis. We combine this insight with a WMC encoding of quantum circuit simulation, which we extend with support for the Toffoli gate. Finally, we prove that the weights computed by the model counter indeed realize the reduction. With an open-source implementation, we demonstrate that this novel approach can outperform a state-of-the-art equivalence-checking tool based on ZX calculus and decision diagrams.

arXiv:2403.18813•Lecture notes in computer science•Jan 1, 2024•21 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 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

A quantum algorithm to count weighted ground states of classical spin Hamiltonians

Bhuvanesh Sundar, Roger Paredes, David T. Damanik +2 more

Ground state counting plays an important role in several applications in science and engineering, from estimating residual entropy in physical systems, to bounding engineering reliability and solving combinatorial counting problems. While quantum algorithms such as adiabatic quantum optimization (AQO) and quantum approximate optimization (QAOA) can minimize Hamiltonians, they are inadequate for counting ground states. We modify AQO and QAOA to count the ground states of arbitrary classical spin Hamiltonians, including counting ground states with arbitrary nonnegative weights attached to them. As a concrete example, we show how our method can be used to count the weighted fraction of edge covers on graphs, with user-specified confidence on the relative error of the weighted count, in the asymptotic limit of large graphs. We find the asymptotic computational time complexity of our algorithms, via analytical predictions for AQO and numerical calculations for QAOA, and compare with the classical optimal Monte Carlo algorithm (OMCS), as well as a modified Grover's algorithm. We show that for large problem instances with small weights on the ground states, AQO does not have a quantum speedup over OMCS for a fixed error and confidence, but QAOA has a sub-quadratic speedup on a broad class of numerically simulated problems. Our work is an important step in approaching general ground-state counting problems beyond those that can be solved with Grover's algorithm. It offers algorithms that can employ noisy intermediate-scale quantum devices for solving ground state counting problems on small instances, which can help in identifying more problem classes with quantum speedups.

arXiv:1908.01745•Aug 5, 2019•18 citations

Quantum algorithms for equational reasoning

Davide Rattacaso, Daniel Jaschke, Marco Ballarin +2 more

As a cornerstone of automated reasoning, equational reasoning finds equivalences between symbolic expressions and fuels advances across scientific disciplines. Yet, its potential remains limited by the exponential growth of equivalent expressions with increasing problem size. We introduce quantum normal form reduction, a quantum computational framework designed to address this challenge. We construct an efficiently implementable quantum Hamiltonian whose ground state encodes all equivalent expressions in a quantum superposition. By preparing and manipulating these states, we tackle fundamental problems in equational reasoning, including verifying and counting equivalent expressions and identifying structural properties of equivalence classes. We demonstrate a quantum-inspired version of the algorithm using tensor networks to solve instances involving up to 10 28 equivalent expressions, far beyond the reach of classical graph exploration. This framework opens the path for quantum symbolic computation in areas from circuit design to data compression, computational group theory, linguistics, and macromolecular modeling, unlocking previously inaccessible problems.

arXiv:2508.21122•Science Advances•May 15, 2026•2 citations
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.
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.
Abstract Verifying equivalence between two quantum circuits is a hard problem, that is nonetheless crucial in compiling and optimizing quantum algorithms for real-world devices. This paper gives a Turing reduction of the (universal) quantum circuits equivalence problem to weighted model counting (WMC). Our starting point is a folklore theorem showing that equivalence checking of quantum circuits can be done in the so-called Pauli-basis. We combine this insight with a WMC encoding of quantum circuit simulation, which we extend with support for the Toffoli gate. Finally, we prove that the weights computed by the model counter indeed realize the reduction. With an open-source implementation, we demonstrate that this novel approach can outperform a state-of-the-art equivalence-checking tool based on ZX calculus and decision diagrams.
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.
Ground state counting plays an important role in several applications in science and engineering, from estimating residual entropy in physical systems, to bounding engineering reliability and solving combinatorial counting problems. While quantum algorithms such as adiabatic quantum optimization (AQO) and quantum approximate optimization (QAOA) can minimize Hamiltonians, they are inadequate for counting ground states. We modify AQO and QAOA to count the ground states of arbitrary classical spin Hamiltonians, including counting ground states with arbitrary nonnegative weights attached to them. As a concrete example, we show how our method can be used to count the weighted fraction of edge covers on graphs, with user-specified confidence on the relative error of the weighted count, in the asymptotic limit of large graphs. We find the asymptotic computational time complexity of our algorithms, via analytical predictions for AQO and numerical calculations for QAOA, and compare with the classical optimal Monte Carlo algorithm (OMCS), as well as a modified Grover's algorithm. We show that for large problem instances with small weights on the ground states, AQO does not have a quantum speedup over OMCS for a fixed error and confidence, but QAOA has a sub-quadratic speedup on a broad class of numerically simulated problems. Our work is an important step in approaching general ground-state counting problems beyond those that can be solved with Grover's algorithm. It offers algorithms that can employ noisy intermediate-scale quantum devices for solving ground state counting problems on small instances, which can help in identifying more problem classes with quantum speedups.
As a cornerstone of automated reasoning, equational reasoning finds equivalences between symbolic expressions and fuels advances across scientific disciplines. Yet, its potential remains limited by the exponential growth of equivalent expressions with increasing problem size. We introduce quantum normal form reduction, a quantum computational framework designed to address this challenge. We construct an efficiently implementable quantum Hamiltonian whose ground state encodes all equivalent expressions in a quantum superposition. By preparing and manipulating these states, we tackle fundamental problems in equational reasoning, including verifying and counting equivalent expressions and identifying structural properties of equivalence classes. We demonstrate a quantum-inspired version of the algorithm using tensor networks to solve instances involving up to 10 28 equivalent expressions, far beyond the reach of classical graph exploration. This framework opens the path for quantum symbolic computation in areas from circuit design to data compression, computational group theory, linguistics, and macromolecular modeling, unlocking previously inaccessible problems.