Simple parallel estimation of the partition ratio for Gibbs distributions

We consider the problem of estimating the partition function Z(β)=∑ₓ exp(β(H(x)) of a Gibbs distribution with the Hamiltonian H:Ω→\0\∪[1,n]. As shown in [Harris & Kolmogorov 2024], the log-ratio q=ln (Z(βₘₐₓ)/Z(βₘᵢₙ)) can be estimated with accuracy ε using O(q log n/ε²) calls to an oracle that produces a sample from the Gibbs distribution for parameter β∈[βₘᵢₙ,βₘₐₓ]. That algorithm is inherently sequential, or { adaptive}: the queried values of β depend on previous samples. Recently, [Liu, Yin & Zhang 2024] developed a non-adaptive version that needs O( q (log² n) (log q + log log n + ε⁻²) ) samples. We improve the number of samples to O(q log² n/ε²) for a non-adaptive algorithm, and to O(q log n/ε²) 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.