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, 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.

arXiv:2604.01263•ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)•Jul 6, 2026•1 citation

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•27 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

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•1 citation

Estimating Gibbs partition function with quantum Clifford sampling

Yusen Wu, Jingbo B. Wang

Abstract The partition function is an essential quantity in statistical mechanics, and its accurate computation is a key component of any statistical analysis of quantum systems and phenomena. However, for interacting many-body quantum systems, its calculation generally involves summing over an exponential number of terms and can thus quickly grow to be intractable. Accurately and efficiently estimating the partition function of its corresponding system Hamiltonian then becomes the key in solving quantum many-body problems. In this paper we develop a hybrid quantum–classical algorithm to estimate the partition function, utilising a novel quantum Clifford sampling technique. Note that previous works on the estimation of partition functions require O ( 1 / ϵ Δ ) -depth quantum circuits (Srinivasan et al 2021 IEEE Int. Conf. on Quantum Computing and Engineering (QCE) pp 112–22; Montanaro 2015 Proc. R. Soc. A 471 20150301), where Δ is the minimum spectral gap of stochastic matrices and ϵ is the multiplicative error. Our algorithm requires only a shallow O ( 1 ) -depth quantum circuit, repeated O ( n / ϵ 2 ) times, to provide a comparable ϵ approximation. Shallow-depth quantum circuits are considered vitally important for currently available noisy intermediate-scale quantum devices.

arXiv:2109.10486•Quantum Science and Technology•Jan 4, 2022•10 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
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 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.
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.
Abstract The partition function is an essential quantity in statistical mechanics, and its accurate computation is a key component of any statistical analysis of quantum systems and phenomena. However, for interacting many-body quantum systems, its calculation generally involves summing over an exponential number of terms and can thus quickly grow to be intractable. Accurately and efficiently estimating the partition function of its corresponding system Hamiltonian then becomes the key in solving quantum many-body problems. In this paper we develop a hybrid quantum–classical algorithm to estimate the partition function, utilising a novel quantum Clifford sampling technique. Note that previous works on the estimation of partition functions require O ( 1 / ϵ Δ ) -depth quantum circuits (Srinivasan et al 2021 IEEE Int. Conf. on Quantum Computing and Engineering (QCE) pp 112–22; Montanaro 2015 Proc. R. Soc. A 471 20150301), where Δ is the minimum spectral gap of stochastic matrices and ϵ is the multiplicative error. Our algorithm requires only a shallow O ( 1 ) -depth quantum circuit, repeated O ( n / ϵ 2 ) times, to provide a comparable ϵ approximation. Shallow-depth quantum circuits are considered vitally important for currently available noisy intermediate-scale quantum devices.
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}}$.