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

Simple parallel estimation of the partition ratio for Gibbs distributions

David G. Harris, Vladimir Kolmogorov

Published May 23, 2025• 0 citations
arXivHTMLPDF

Abstract

We consider the problem of estimating the partition function $Z(β)=\sum_x \exp(β(H(x))$ of a Gibbs distribution with the Hamiltonian $H:Ω\rightarrow\{0\}\cup[1,n]$. As shown in [Harris & Kolmogorov 2024], the log-ratio $q=\ln (Z(β_{\max})/Z(β_{\min}))$ can be estimated with accuracy $ε$ using $O(\frac{q \log n}{ε^2})$ calls to an oracle that produces a sample from the Gibbs distribution for parameter $β\in[β_{\min},β_{\max}]$. That algorithm is inherently sequential, or {\em adaptive}: the queried values of $β$ depend on previous samples. Recently, [Liu, Yin & Zhang 2024] developed a non-adaptive version that needs $O( q (\log^2 n) (\log q + \log \log n + ε^{-2}) )$ samples. We improve the number of samples to $O(\frac{q \log^2 n}{ε^2})$ for a non-adaptive algorithm, and to $O(\frac{q \log n}{ε^2})$ for an algorithm that uses just two rounds of adaptivity (matching the complexity of the sequential version). Furthermore, our algorithm simplifies previous techniques. In particular, we use just a single estimator, whereas methods in [Harris & Kolmogorov 2024, Liu, Yin & Zhang 2024] employ two different estimators for different regimes.

DOI
10.48550/arxiv.2505.18324

Related papers

Near-Optimal Parallel Approximate Counting via Sampling

David G. Harris, Vladimir Kolmogorov, Hongyang Liu +2 more

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(β)=\sum_{x\in Ω} \exp(βH(x))$ of Gibbs distributions $μ_β$ over $Ω$ with Hamiltonian $H$, given access to a sampling oracle that produces samples from $μ_β$ for $β\in [β_{\min}, β_{\max}]$. The best bound achieved by known annealing algorithms with relative error $\varepsilon$ is $O(q \log h / \varepsilon^2)$, where $q, h$ are parameters which respectively bound $\ln Q$ 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(q \log^2 h / \varepsilon^2)$ samples, as well as an algorithm that achieves $O(q \log h / \varepsilon^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.

arXiv:2604.01263•Apr 1, 2026•0 citations

Near-Optimal Parallel Approximate Counting via Sampling

David G. Harris, Vladimir Kolmogorov, H.W. Liu +2 more

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 based on simulated annealing. In this approach, the counting problem is formulated as 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 for μβ at any β ∈ [βmin, βmax]. The sample complexity (measured by the number of oracle calls) is typically expressed in terms of q and h, which respectively bound ln Q and H. The best upper bound achieved by known annealing algorithms with relative error ε is O(qε−2 log h). However, all known algorithms attaining this near-optimal complexity are inherently sequential, or adaptive: the queried parameters β depend on previous samples.

ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)•Jul 6, 2026•0 citations

Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions

Srinivasan Arunachalam, Vojtěch Havlíček, Giacomo Nannicini +2 more

We present classical and quantum algorithms for approximating partition functions of classical Hamiltonians at a given temperature. Our work has two main contributions: first, we modify the classical algorithm of Stefankovic, Vempala and Vigoda (J. ACM, 56(3), 2009) to improve its sample complexity; second, we quantize this new algorithm, improving upon the previously fastest quantum algorithm for this problem, due to Harrow and Wei (SODA 2020). The conventional approach to estimating partition functions requires approximating the means of Gibbs distributions at a set of inverse temperatures that form the so-called cooling schedule. The length of the cooling schedule directly affects the complexity of the algorithm. Combining our improved version of the algorithm of Stefankovic, Vempala and Vigoda with the paired-product estimator of Huber (Ann. Appl. Probab., 25(2), 2015), our new quantum algorithm uses a shorter cooling schedule than previously known. This length matches the optimal length conjectured by Stefankovic, Vempala and Vigoda. The quantum algorithm also achieves a quadratic advantage in the number of required quantum samples compared to the number of random samples drawn by the best classical algorithm, and its computational complexity has quadratically better dependence on the spectral gap of the Markov chains used to produce the quantum samples.

arXiv:2009.11270•Quantum•Sep 1, 2022•17 citations

Simpler (Classical) and Faster (Quantum) Algorithms for Gibbs Partition Functions

Srinivasan Arunachalam, Vojtěch Havlíček, Giacomo Nannicini +2 more

We give classical and quantum algorithms for approximating partition functions of classical Hamiltonians at a given temperature. Specifically, we modify the classical algorithm of Štefankovič, Vempala and Vigoda (J. ACM, 56(3), 2009) to improve its sample complexity; and we quantize this new algorithm, improving upon the previously best quantum algorithm for computing Gibbs partition functions due to Harrow and Wei (SODA 2020).The conventional approach to estimate partition functions requires approximating the mean of Gibbs distributions at nearby inverse temperatures that satisfy certain properties; this set of temperatures is called a cooling schedule. The length of the cooling schedule directly affects the complexity of the algorithm. Combining our improved version of the algorithm of Štefankovič, Vempala and Vigoda with the paired-product estimator of Huber (Ann. Appl. Probab., 25(2), 2015), our new quantum algorithm uses a shorter cooling schedule than previously known. This length matches the optimal length conjectured by Štefankovič, Vempala and Vigoda. The quantum algorithm also achieves a quadratic advantage in the number of required quantum samples compared to the number of random samples drawn by the best classical algorithm, and its computational complexity has quadratically better dependence on the spectral gap of the Markov chains used to produce the quantum samples.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Oct 1, 2021•7 citations

Quantum Tsallis Entropy Estimation: Near-Optimal Bounds and High-Precision Improvements

Chengshen Gao, Zongxing Xiong, Lvzhou Li

Estimating statistical properties of probability distributions is a fundamental problem in statistics and theoretical computer science. We develop quantum algorithms for estimating the $q$-Tsallis entropy $\mathrm{H}_q^{\mathrm{Tsa}}(P) =\frac{\sum_{i=1}^n p_i^q-1}{1-q}$ when $0<q<1$, given purified quantum query access to a distribution $P$ on $[n]$. When $0<q\leq \frac{1}{2}$, we provide a quantum algorithm with query complexity $\widetilde{O}\rbra{\left(\frac{n}{\varepsilon}\right)^{\frac{1}{2q}}}$, which is optimal up to polylogarithmic factors. When $\frac{1}{2}<q<1$, we introduce a two-stage simultaneous probability estimation procedure, yielding a quantum algorithm with query complexity $\widetilde{O}\left(\frac{n^{\frac12+\frac{1}{2q}}}{\varepsilon^{\frac{1}{2q}}}+\frac{n^{1-q}}{\varepsilon}\right)$, which improves the result given by Chen et al. (ICALP 2026) when $\varepsilon=O\rbra{n^{1-2q}}$.

quant-pharXiv:2610.22983•Oct 19, 2026•0 citations

A simple lower bound for the complexity of estimating partition functions on a quantum computer

Zherui Chen, Giacomo Nannicini

We study the complexity of estimating the partition function $\mathsf{Z}(β)=\sum_{x\inχ} e^{-βH(x)}$ for a Gibbs distribution characterized by the Hamiltonian $H(x)$. We provide a simple and natural lower bound for quantum algorithms that solve this task by relying on reflections through the coherent encoding of Gibbs states. Our primary contribution is a $\varOmega(1/ε)$ lower bound for the number of reflections needed to estimate the partition function with a quantum algorithm. The proof is based on a reduction from the problem of estimating the Hamming weight of an unknown binary string.

arXiv:2404.02414•Apr 3, 2024•0 citations
We consider the problem of estimating the partition function Z(β)=∑xexp⁡(β(H(x))Z(β)=\sum_x \exp(β(H(x))Z(β)=∑x​exp(β(H(x)) of a Gibbs distribution with the Hamiltonian H:Ω→{0}∪[1,n]H:Ω\rightarrow\{0\}\cup[1,n]H:Ω→{0}∪[1,n]. As shown in [Harris & Kolmogorov 2024], the log-ratio q=ln⁡(Z(βmax⁡)/Z(βmin⁡))q=\ln (Z(β_{\max})/Z(β_{\min}))q=ln(Z(βmax​)/Z(βmin​)) can be estimated with accuracy εεε using O(qlog⁡nε2)O(\frac{q \log n}{ε^2})O(ε2qlogn​) calls to an oracle that produces a sample from the Gibbs distribution for parameter β∈[βmin⁡,βmax⁡]β\in[β_{\min},β_{\max}]β∈[βmin​,βmax​]. That algorithm is inherently sequential, or {\em adaptive}: the queried values of βββ depend on previous samples. Recently, [Liu, Yin & Zhang 2024] developed a non-adaptive version that needs O(q(log⁡2n)(log⁡q+log⁡log⁡n+ε−2))O( q (\log^2 n) (\log q + \log \log n + ε^{-2}) )O(q(log2n)(logq+loglogn+ε−2)) samples. We improve the number of samples to O(qlog⁡2nε2)O(\frac{q \log^2 n}{ε^2})O(ε2qlog2n​) for a non-adaptive algorithm, and to O(qlog⁡nε2)O(\frac{q \log n}{ε^2})O(ε2qlogn​) for an algorithm that uses just two rounds of adaptivity (matching the complexity of the sequential version). Furthermore, our algorithm simplifies previous techniques. In particular, we use just a single estimator, whereas methods in [Harris & Kolmogorov 2024, Liu, Yin & Zhang 2024] employ two different estimators for different regimes.
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⁡)Q={Z(β_{\max})}/{Z(β_{\min})}Q=Z(βmax​)/Z(βmin​) between partition functions Z(β)=∑x∈Ωexp⁡(βH(x))Z(β)=\sum_{x\in Ω} \exp(βH(x))Z(β)=∑x∈Ω​exp(βH(x)) of Gibbs distributions μβμ_βμβ​ over ΩΩΩ with Hamiltonian HHH, given access to a sampling oracle that produces samples from μβμ_βμβ​ for β∈[βmin⁡,βmax⁡]β\in [β_{\min}, β_{\max}]β∈[βmin​,βmax​]. The best bound achieved by known annealing algorithms with relative error ε\varepsilonε is O(qlog⁡h/ε2)O(q \log h / \varepsilon^2)O(qlogh/ε2), where q,hq, hq,h are parameters which respectively bound ln⁡Q\ln QlnQ and HHH. 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(qlog⁡2h/ε2)O(q \log^2 h / \varepsilon^2)O(qlog2h/ε2) samples, as well as an algorithm that achieves O(qlog⁡h/ε2)O(q \log h / \varepsilon^2)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.
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 based on simulated annealing. In this approach, the counting problem is formulated as 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 for μβ at any β ∈ [βmin, βmax]. The sample complexity (measured by the number of oracle calls) is typically expressed in terms of q and h, which respectively bound ln Q and H. The best upper bound achieved by known annealing algorithms with relative error ε is O(qε−2 log h). However, all known algorithms attaining this near-optimal complexity are inherently sequential, or adaptive: the queried parameters β depend on previous samples.
We present classical and quantum algorithms for approximating partition functions of classical Hamiltonians at a given temperature. Our work has two main contributions: first, we modify the classical algorithm of Stefankovic, Vempala and Vigoda (J. ACM, 56(3), 2009) to improve its sample complexity; second, we quantize this new algorithm, improving upon the previously fastest quantum algorithm for this problem, due to Harrow and Wei (SODA 2020). The conventional approach to estimating partition functions requires approximating the means of Gibbs distributions at a set of inverse temperatures that form the so-called cooling schedule. The length of the cooling schedule directly affects the complexity of the algorithm. Combining our improved version of the algorithm of Stefankovic, Vempala and Vigoda with the paired-product estimator of Huber (Ann. Appl. Probab., 25(2), 2015), our new quantum algorithm uses a shorter cooling schedule than previously known. This length matches the optimal length conjectured by Stefankovic, Vempala and Vigoda. The quantum algorithm also achieves a quadratic advantage in the number of required quantum samples compared to the number of random samples drawn by the best classical algorithm, and its computational complexity has quadratically better dependence on the spectral gap of the Markov chains used to produce the quantum samples.
We give classical and quantum algorithms for approximating partition functions of classical Hamiltonians at a given temperature. Specifically, we modify the classical algorithm of Štefankovič, Vempala and Vigoda (J. ACM, 56(3), 2009) to improve its sample complexity; and we quantize this new algorithm, improving upon the previously best quantum algorithm for computing Gibbs partition functions due to Harrow and Wei (SODA 2020).The conventional approach to estimate partition functions requires approximating the mean of Gibbs distributions at nearby inverse temperatures that satisfy certain properties; this set of temperatures is called a cooling schedule. The length of the cooling schedule directly affects the complexity of the algorithm. Combining our improved version of the algorithm of Štefankovič, Vempala and Vigoda with the paired-product estimator of Huber (Ann. Appl. Probab., 25(2), 2015), our new quantum algorithm uses a shorter cooling schedule than previously known. This length matches the optimal length conjectured by Štefankovič, Vempala and Vigoda. The quantum algorithm also achieves a quadratic advantage in the number of required quantum samples compared to the number of random samples drawn by the best classical algorithm, and its computational complexity has quadratically better dependence on the spectral gap of the Markov chains used to produce the quantum samples.
Estimating statistical properties of probability distributions is a fundamental problem in statistics and theoretical computer science. We develop quantum algorithms for estimating the qqq-Tsallis entropy HqTsa(P)=∑i=1npiq−11−q\mathrm{H}_q^{\mathrm{Tsa}}(P) =\frac{\sum_{i=1}^n p_i^q-1}{1-q}HqTsa​(P)=1−q∑i=1n​piq​−1​ when 0<q<10<q<10<q<1, given purified quantum query access to a distribution PPP on [n][n][n]. When 0<q≤120<q\leq \frac{1}{2}0<q≤21​, we provide a quantum algorithm with query complexity $\widetilde{O}\rbra{\left(\frac{n}{\varepsilon}\right)^{\frac{1}{2q}}}$, which is optimal up to polylogarithmic factors. When 12<q<1\frac{1}{2}<q<121​<q<1, we introduce a two-stage simultaneous probability estimation procedure, yielding a quantum algorithm with query complexity O~(n12+12qε12q+n1−qε)\widetilde{O}\left(\frac{n^{\frac12+\frac{1}{2q}}}{\varepsilon^{\frac{1}{2q}}}+\frac{n^{1-q}}{\varepsilon}\right)O(ε2q1​n21​+2q1​​+εn1−q​), which improves the result given by Chen et al. (ICALP 2026) when $\varepsilon=O\rbra{n^{1-2q}}$.
We study the complexity of estimating the partition function Z(β)=∑x∈χe−βH(x)\mathsf{Z}(β)=\sum_{x\inχ} e^{-βH(x)}Z(β)=∑x∈χ​e−βH(x) for a Gibbs distribution characterized by the Hamiltonian H(x)H(x)H(x). We provide a simple and natural lower bound for quantum algorithms that solve this task by relying on reflections through the coherent encoding of Gibbs states. Our primary contribution is a Ω(1/ε)\varOmega(1/ε)Ω(1/ε) lower bound for the number of reflections needed to estimate the partition function with a quantum algorithm. The proof is based on a reduction from the problem of estimating the Hamming weight of an unknown binary string.