For a graph G on n vertices, let Z(G, λ) be the partition function of the monomer-dimer system defined by: Z(G, λ) = ∑ k mk(G)λk, where mk(G) is the number of matchings of cardinality k in G. We develop a constant-time algorithm for approximating log Z(G, λ) at an arbitrary point λ ≥ 0 with additive error ɛn. In the bounded degree model, the query complexity of our algorithm is polynomial in 1/ɛ, and we provide a lower bound quadratic in 1/ɛ for this problem. This is the first analysis of a sublinear-time algorithm for a #P-complete problem. Our approach is based on the correlation decay of the Gibbs distribution associated with Z(G, λ). We show that our algorithm approximates the probability for a vertex to be covered by a matching sampled according to this Gibbs distribution in a near-optimal sublinear-time. We extend our results to approximate the average size and the entropy of such a matching with an additive error in constant time, where again the query complexity is polynomial in 1/ɛ and the lower bound is quadratic in 1/ɛ. Our algorithms are simple to implement and of practical use when dealing with massive datasets. Our results extend to many other problems where the correlation decay is known to hold as for independent sets or the Ising model up to the critical activity.
For a graph G on n vertices, let Z(G, λ) be the partition function of the monomer-dimer system defined by: Z(G, λ) = ∑ k mk(G)λk, where mk(G) is the number of matchings of cardinality k in G. We develop a constant-time algorithm for approximating log Z(G, λ) at an arbitrary point λ ≥ 0 with additive error ɛn. In the bounded degree model, the query complexity of our algorithm is polynomial in 1/ɛ, and we provide a lower bound quadratic in 1/ɛ for this problem. This is the first analysis of a sublinear-time algorithm for a #P-complete problem. Our approach is based on the correlation decay of the Gibbs distribution associated with Z(G, λ). We show that our algorithm approximates the probability for a vertex to be covered by a matching sampled according to this Gibbs distribution in a near-optimal sublinear-time. We extend our results to approximate the average size and the entropy of such a matching with an additive error in constant time, where again the query complexity is polynomial in 1/ɛ and the lower bound is quadratic in 1/ɛ. Our algorithms are simple to implement and of practical use when dealing with massive datasets. Our results extend to many other problems where the correlation decay is known to hold as for independent sets or the Ising model up to the critical activity.
We present a novel quantum algorithm for estimating Gibbs partition functions in sublinear time with respect to the logarithm of the size of the state space. This is the first speed-up of this type to be obtained over the seminal nearly-linear time algorithm of Štefankovič, Vempala and Vigoda [45]. Our result also preserves the quadratic speed-up in precision and spectral gap achieved in previous work by exploiting the properties of quantum Markov chains. As an application, we obtain new polynomial improvements over the best-known algorithms for computing the partition function of the Ising model, counting the number of k-colorings, matchings or independent sets of a graph, and estimating the volume of a convex body. Our approach relies on developing new variants of the quantum phase and amplitude estimation algorithms that return nearly unbiased estimates with low variance and without destroying their initial quantum state. We extend these subroutines into a nearly unbiased quantum mean estimator that reduces the variance quadratically faster than the classical empirical mean. No such estimator was known to exist prior to our work. These properties, which are of general interest, lead to better convergence guarantees within the paradigm of simulated annealing for computing partition functions. * The full version of the paper can be accessed at http://arxiv.org/abs/2207.08643.
In this work, we study bipartiteness and expansion testing, two canonical problems in graph property testing in the bounded-degree model through the lens of quantum query complexity. In the classical setting, it is known that Θ(N) queries are necessary and sufficient for both these testing problems (Goldreich and Ron, 1999, 2000 & 2002), where N denotes the number of vertices of the input graph. Due to their significance, (Ambainis, Childs, and Liu, 2011) initiated the study of these problems in the quantum setting and designed quantum algorithms for bipartiteness and expansion testing that perform O(N1/3) queries, showing a polynomial speedup. They also proved that Ω(N1/4) queries are necessary for expansion testing, but the possibility of an exponential quantum advantage for bipartiteness testing remained open. Despite significant effort, there has been no improvement in these results in the last decade and a half. In this work, we prove essentially tight Ω(N1/3) quantum query lower bounds for both bipartiteness and expansion testing, thereby completely characterizing the quantum query complexity of these problems up to polylogarithmic factors. While our proofs use the polynomial method similarly to Ambainis, Childs, and Liu, we use intermediate problems that we relate to the main problems via reductions, and perform a more precise analysis of the resulting polynomials, leading to the near-optimal lower bounds.
The computational equivalence between approximate counting and sampling is well established for polynomial-time algorithms. The most efficient general reduction from counting to sampling is achieved via simulated annealing, where the counting problem is formulated in terms of estimating the ratio Q=Z(βmax)/Z(βmin) between partition functions Z(β)=∑x∈Ωexp(βH(x)) of Gibbs distributions μβ over Ω with Hamiltonian H, given access to a sampling oracle that produces samples from μβ for β∈[βmin,βmax]. The best bound achieved by known annealing algorithms with relative error ε is O(qlogh/ε2), where q,h are parameters which respectively bound lnQ and H. However, all known algorithms attaining this near-optimal complexity are inherently sequential, or *adaptive*: the queried parameters β depend on previous samples. We develop a simple non-adaptive algorithm for approximate counting using O(qlog2h/ε2) samples, as well as an algorithm that achieves O(qlogh/ε2) samples with just two rounds of adaptivity, matching the best sample complexity of sequential algorithms. These algorithms naturally give rise to work-efficient parallel (RNC) counting algorithms. We discuss applications to RNC counting algorithms for several classic models, including the anti-ferromagnetic 2-spin, monomer-dimer and ferromagnetic Ising models.
We study the problem of approximating the Ising model partition function with complex parameters on bounded degree graphs. We establish a deterministic polynomial-time approximation scheme for the partition function when the interactions and external fields are absolutely bounded close to zero. Furthermore, we prove that for this class of Ising models the partition function does not vanish. Our algorithm is based on an approach due to Barvinok for approximating evaluations of a polynomial based on the location of the complex zeros and a technique due to Patel and Regts for efficiently computing the leading coefficients of graph polynomials on bounded degree graphs. Finally, we show how our algorithm can be extended to approximate certain output probability amplitudes of quantum circuits.
The constructive diagonal Ramsey problem asks, given adjacency-oracle access to an N-vertex graph, for a clique or independent set of the order guaranteed by Ramsey's theorem. We give a bounded-error quantum algorithm that, for every K≥2 and N≥4K−1, finds and verifies a homogeneous K-set using O(2KKlogηK) edge queries with failure probability at most η. At the Ramsey scale N=2n, this yields a homogeneous set of order ⌊n/2⌋+1 using O(NlogNlog(logN/η)) queries, improving on the O(N) queries of the explicit classical recursion and giving, to our knowledge, the first sublinear worst-case algorithm for the Ramsey relation. We also derive an Ω(N1/12) quantum lower bound by a reduction from collision finding.
The algorithm runs the constructive recursion over implicit candidate sets. Each set is represented by a short conjunction of adjacency constraints and sampled using capped unknown-solution quantum search, and a scale-aware concentration schedule balances estimation accuracy against the increasing cost of sampling deeper sets. We complement the upper bound with an Ω(N1−1/2) randomized lower bound, transported from the random-Painter analysis of online Ramsey numbers, which holds on the uniform distribution G(N,1/2). On that distribution a greedy quantum search uses only O(N1/4) queries, giving a provable polynomial quantum speedup for Ramsey search on random graphs. We also give an estimation-free size-biased recursion and extend it to every fixed number of edge colours.
Subgraph detection asks whether an n-vertex graph, accessed through queries to its adjacency matrix, contains a copy of a fixed graph H. We prove the first unconditional superlinear lower bounds on the bounded-error quantum query complexity of this problem, answering a longstanding open question. A copy of H is a certificate of constant size, so the adversary method with nonnegative weights cannot prove superlinear lower bounds.
For every fixed r≥4, detecting the clique Kr requires nλr−o(1) queries, where λ4=19/18, the exponents λr increase strictly with r, and λr≥2−42/r+O(1/r). More generally, we prove superlinear lower bounds for detecting every fixed connected graph H with chromatic number c≥4. These bounds approach quadratic as c grows: for sufficiently large c, detection requires n2−O(loglogc/c)−o(1) queries. Chromatic number alone does not characterize the quantum query complexity of subgraph detection: we show that detecting the complete bipartite graph Kr,r requires nβr−o(1) queries, where β10=181/180 and βr≥2−O(1/r).
Our main technical result is a lower bound for finding an all-ones certificate from a known family when the input bits are sampled independently. Its proof combines Zhandry's compressed oracle [CRYPTO 2019] with conditioning on a randomly planted certificate, adapting an argument of Belovs [FOCS 2026]. Our hard instances are built from graphs containing many copies of the desired subgraph with limited overlap. For cliques, we use a construction of Gowers and Janzer [CPC 2021]; for complete bipartite graphs, we use a random construction.