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:2512.10134

Approximate Counting in Local Lemma Regimes

Ryan L. Mann, Gabriel Waite

cs.DSmath.COmath.PRquant-phSubmitted Dec 10, 2025• Announced Dec 12, 2025• 0 citations
arXivHTMLPDF

Abstract

We establish efficient approximate counting algorithms for several natural problems in local lemma regimes. In particular, we consider the probability of intersection of events and the dimension of intersection of subspaces. Our approach is based on the cluster expansion method. We obtain fully polynomial-time approximation schemes for both the probability of intersection and the dimension of intersection for commuting projectors. For general projectors, we provide two algorithms: a fully polynomial-time approximation scheme under a global inclusion-exclusion stability condition, and an efficient affine approximation under a spectral gap assumption. As corollaries of our results, we obtain efficient algorithms for approximating the number of satisfying assignments of conjunctive normal form formulae and the dimension of satisfying subspaces of quantum satisfiability formulae.

Comments
20 pages, 0 figures

Related papers

A quantum Lovász local lemma

Andris Ambainis, Julia Kempe, Or Sattath

The Lovász Local Lemma (LLL) is a powerful tool in probability theory to show the existence of combinatorial objects meeting a prescribed collection of “weakly dependent” criteria. We show that the LLL extends to a much more general geometric setting, where events are replaced with subspaces and probability is replaced with relative dimension, which allows to lower bound the dimension of the intersection of vector spaces under certain independence conditions. Our result immediately applies to the k - qsat problem (quantum analog of k - sat ): For instance we show that any collection of rank-1 projectors, with the property that each qubit appears in at most 2 k /( e ċ k ) of them, has a joint satisfiable state. We then apply our results to the recently studied model of random k - qsat . Recent works have shown that the satisfiable region extends up to a density of 1 in the large k limit, where the density is the ratio of projectors to qubits. Using a hybrid approach building on work by Laumann et al. [2009, 2010] we greatly extend the known satisfiable region for random k - qsat to a density of Ω(2 k / k 2 ). Since our tool allows us to show the existence of joint satisfying states without the need to construct them, we are able to penetrate into regions where the satisfying states are conjectured to be entangled, avoiding the need to construct them, which has limited previous approaches to product states.

arXiv:0911.1696•Journal of the ACM•Oct 1, 2012•22 citations

A Constructive Quantum Lovász Local Lemma for Commuting Projectors

Itai Arad, Or Sattath

The Quantum Satisfiability problem generalizes the Boolean satisfiability problem to the quantum setting by replacing classical clauses with local projectors. The Quantum Lovász Local Lemma gives a sufficient condition for a Quantum Satisfiability problem to be satisfiable [AKS12], by generalizing the classical Lovász Local Lemma. The next natural question that arises is: can a satisfying quantum state be efficiently found, when these conditions hold? In this work we present such an algorithm, with the additional requirement that all the projectors commute. The proof follows the information theoretic proof given by Moser's breakthrough result in the classical setting [Mos09]. Similar results were independently published in [CS11,CSV13].

arXiv:1310.7766•Oct 29, 2013•6 citations

A constructive quantum Lovasz local lemma for commuting projectors

Or Sattath, Itai Arad

The Quantum Satisfiability problem generalizes the Boolean satisfiability problem to the quantum setting by replacing classical clauses with local projectors. The Quantum Lov\'asz Local Lemma gives a sufficient condition for a Quantum Satisfiability problem to be satisfiable~\cite{ambainis2012quantum}, by generalizing the classical Lov\'asz Local Lemma. The next natural question that arises is: can a satisfying quantum state be \emph{efficiently} found, when these conditions hold? In this work we present such an algorithm, with the additional requirement that all the projectors commute. The proof follows the information theoretic proof given by Moser's breakthrough result in the classical setting~\cite{moser2009constructiveSTOC}. Similar results were independently published in~\cite{cubitt2011constructive, cubitt2013quantum}.

Quantum Information and Computation•Sep 1, 2015•6 citations

Efficient Algorithms for Weakly-Interacting Quantum Spin Systems

Ryan L. Mann, Gabriel Waite

We establish efficient algorithms for weakly-interacting quantum spin systems at arbitrary temperature. In particular, we obtain a fully polynomial-time approximation scheme for the partition function and an efficient approximate sampling scheme for the thermal distribution over a classical spin space. Our approach is based on the cluster expansion method and a standard reduction from approximate sampling to approximate counting.

quant-pharXiv:2601.21140•Physical Review A•Jan 30, 2026•0 citations

Deterministic Approximate Counting for Juntas of Degree-2 Polynomial Threshold Functions

Anindya De, Ilias Diakonikolas, Rocco A. Servedio

Let g : {-1, 1}k→ {-1, 1} be any Boolean function and q1, . . . , qkbe any degree-2 polynomials over {-1, 1}n. We give a deterministic algorithm which, given as input explicit descriptions of g, q1, . . ., qkand an accuracy parameter ϵ > 0, approximates Prx~{-1, 1}n[g(sign(q1(x)), . . . , sign(qk(x))) = 1] to within an additive ±ϵ. For any constant ϵ > 0 and k ≥ 1 the running time of our algorithm is a fixed polynomial in n (in fact this is true even for some not-too-small ϵ = 0n(1) and not-too-large k = ωn(1)). This is the first fixed polynomial-time algorithm that can deterministically approximately count satisfying assignments of a natural class of depth-3 Boolean circuits. Our algorithm extends a recent result [1] which gave a deterministic approximate counting algorithm for a single degree-2 polynomial threshold function sign(q(x)), corresponding to the k = 1 case of our result. Note that even in the k = 1 case it is NP-hard to determine whether Prx~{-1, 1}n[sign(q(x)) = 1] is nonzero, so any sort of multiplicative approximation is almost certainly impossible even for efficient randomized algorithms. Our algorithm and analysis requires several novel technical ingredients that go significantly beyond the tools required to handle the k = 1 case in [1]. One of these is a new multidimensional central limit theorem for degree-2 polynomials in Gaussian random variables which builds on recent Malliavin-calculus-based results from probability theory. We use this CLT as the basis of a new decomposition technique for k-tuples of degree-2 Gaussian polynomials and thus obtain an efficient deterministic approximate counting algorithm for the Gaussian distribution, i.e., an algorithm for estimating Prx~N(0, 1)n[g(sign(q1(x)), . . . , sign(qk(x))) = 1]. Finally, a third new ingredient is a “regularity lemma” for k-tuples of degree-d polynomial threshold functions. This generalizes both the regularity lemmas of [2], [3] (which apply to a single degree-d polynomial threshold function) and the regularity lemma of Gopalan et al [4] (which applies to a k-tuples of linear threshold functions, i.e., the case d = 1). Our new regularity lemma lets us extend our deterministic approximate counting results from the Gaussian to the Boolean domain.

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2014•7 citations

Deterministic Approximate Counting of Polynomial Threshold Functions via a Derandomized Regularity Lemma

Rocco A. Servedio, Li-Yang Tan

We study the problem of deterministically approximating the number of satisfying assignments of a polynomial threshold function (PTF) over Boolean space. We present and analyze a scheme for transforming such algorithms for PTFs over Gaussian space into algorithms for the more challenging and more standard setting of Boolean space. Applying this transformation to existing algorithms for Gaussian space leads to new algorithms for Boolean space that improve on prior state-of-the-art results due to Meka and Zuckerman [Meka and Zuckerman, 2013] and Kane [Kane, 2012]. Our approach is based on a bias-preserving derandomization of Meka and Zuckerman’s regularity lemma for polynomials [Meka and Zuckerman, 2013] using the [Rocco A. Servedio and Li-Yang Tan, 2018] pseudorandom generator for PTFs.

Leibniz international proceedings in informatics•Jan 1, 2021•0 citations
We establish efficient approximate counting algorithms for several natural problems in local lemma regimes. In particular, we consider the probability of intersection of events and the dimension of intersection of subspaces. Our approach is based on the cluster expansion method. We obtain fully polynomial-time approximation schemes for both the probability of intersection and the dimension of intersection for commuting projectors. For general projectors, we provide two algorithms: a fully polynomial-time approximation scheme under a global inclusion-exclusion stability condition, and an efficient affine approximation under a spectral gap assumption. As corollaries of our results, we obtain efficient algorithms for approximating the number of satisfying assignments of conjunctive normal form formulae and the dimension of satisfying subspaces of quantum satisfiability formulae.
The Lovász Local Lemma (LLL) is a powerful tool in probability theory to show the existence of combinatorial objects meeting a prescribed collection of “weakly dependent” criteria. We show that the LLL extends to a much more general geometric setting, where events are replaced with subspaces and probability is replaced with relative dimension, which allows to lower bound the dimension of the intersection of vector spaces under certain independence conditions. Our result immediately applies to the k - qsat problem (quantum analog of k - sat ): For instance we show that any collection of rank-1 projectors, with the property that each qubit appears in at most 2 k /( e ċ k ) of them, has a joint satisfiable state. We then apply our results to the recently studied model of random k - qsat . Recent works have shown that the satisfiable region extends up to a density of 1 in the large k limit, where the density is the ratio of projectors to qubits. Using a hybrid approach building on work by Laumann et al. [2009, 2010] we greatly extend the known satisfiable region for random k - qsat to a density of Ω(2 k / k 2 ). Since our tool allows us to show the existence of joint satisfying states without the need to construct them, we are able to penetrate into regions where the satisfying states are conjectured to be entangled, avoiding the need to construct them, which has limited previous approaches to product states.
The Quantum Satisfiability problem generalizes the Boolean satisfiability problem to the quantum setting by replacing classical clauses with local projectors. The Quantum Lovász Local Lemma gives a sufficient condition for a Quantum Satisfiability problem to be satisfiable [AKS12], by generalizing the classical Lovász Local Lemma. The next natural question that arises is: can a satisfying quantum state be efficiently found, when these conditions hold? In this work we present such an algorithm, with the additional requirement that all the projectors commute. The proof follows the information theoretic proof given by Moser's breakthrough result in the classical setting [Mos09]. Similar results were independently published in [CS11,CSV13].
The Quantum Satisfiability problem generalizes the Boolean satisfiability problem to the quantum setting by replacing classical clauses with local projectors. The Quantum Lov\'asz Local Lemma gives a sufficient condition for a Quantum Satisfiability problem to be satisfiable~\cite{ambainis2012quantum}, by generalizing the classical Lov\'asz Local Lemma. The next natural question that arises is: can a satisfying quantum state be \emph{efficiently} found, when these conditions hold? In this work we present such an algorithm, with the additional requirement that all the projectors commute. The proof follows the information theoretic proof given by Moser's breakthrough result in the classical setting~\cite{moser2009constructiveSTOC}. Similar results were independently published in~\cite{cubitt2011constructive, cubitt2013quantum}.
Let g : {-1, 1}k→ {-1, 1} be any Boolean function and q1, . . . , qkbe any degree-2 polynomials over {-1, 1}n. We give a deterministic algorithm which, given as input explicit descriptions of g, q1, . . ., qkand an accuracy parameter ϵ > 0, approximates Prx~{-1, 1}n[g(sign(q1(x)), . . . , sign(qk(x))) = 1] to within an additive ±ϵ. For any constant ϵ > 0 and k ≥ 1 the running time of our algorithm is a fixed polynomial in n (in fact this is true even for some not-too-small ϵ = 0n(1) and not-too-large k = ωn(1)). This is the first fixed polynomial-time algorithm that can deterministically approximately count satisfying assignments of a natural class of depth-3 Boolean circuits. Our algorithm extends a recent result [1] which gave a deterministic approximate counting algorithm for a single degree-2 polynomial threshold function sign(q(x)), corresponding to the k = 1 case of our result. Note that even in the k = 1 case it is NP-hard to determine whether Prx~{-1, 1}n[sign(q(x)) = 1] is nonzero, so any sort of multiplicative approximation is almost certainly impossible even for efficient randomized algorithms. Our algorithm and analysis requires several novel technical ingredients that go significantly beyond the tools required to handle the k = 1 case in [1]. One of these is a new multidimensional central limit theorem for degree-2 polynomials in Gaussian random variables which builds on recent Malliavin-calculus-based results from probability theory. We use this CLT as the basis of a new decomposition technique for k-tuples of degree-2 Gaussian polynomials and thus obtain an efficient deterministic approximate counting algorithm for the Gaussian distribution, i.e., an algorithm for estimating Prx~N(0, 1)n[g(sign(q1(x)), . . . , sign(qk(x))) = 1]. Finally, a third new ingredient is a “regularity lemma” for k-tuples of degree-d polynomial threshold functions. This generalizes both the regularity lemmas of [2], [3] (which apply to a single degree-d polynomial threshold function) and the regularity lemma of Gopalan et al [4] (which applies to a k-tuples of linear threshold functions, i.e., the case d = 1). Our new regularity lemma lets us extend our deterministic approximate counting results from the Gaussian to the Boolean domain.
We study the problem of deterministically approximating the number of satisfying assignments of a polynomial threshold function (PTF) over Boolean space. We present and analyze a scheme for transforming such algorithms for PTFs over Gaussian space into algorithms for the more challenging and more standard setting of Boolean space. Applying this transformation to existing algorithms for Gaussian space leads to new algorithms for Boolean space that improve on prior state-of-the-art results due to Meka and Zuckerman [Meka and Zuckerman, 2013] and Kane [Kane, 2012]. Our approach is based on a bias-preserving derandomization of Meka and Zuckerman’s regularity lemma for polynomials [Meka and Zuckerman, 2013] using the [Rocco A. Servedio and Li-Yang Tan, 2018] pseudorandom generator for PTFs.