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.
We study the complexity of estimating the partition function Z(β)=∑x∈χ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 Ω(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.
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.
Estimating quantum partition functions is a critical task in a variety of fields. However, the problem is classically intractable in general due to the exponential scaling of the Hamiltonian dimension N in the number of particles. This paper introduces a quantum algorithm for estimating the partition function Zβ of a generic Hamiltonian H up to multiplicative error based on a quantum coin toss. The coin is defined by the probability of applying the quantum imaginary-time evolution propagator fβ[H]=e−βH/2 at inverse temperature β to the maximally mixed state, realized by a block-encoding of fβ[H] into a unitary quantum circuit followed by a post-selection measurement. Our algorithm does not use costly subroutines such as quantum phase estimation or amplitude amplification; and the binary nature of the coin allows us to invoke tools from Bernoulli-process analysis to prove a runtime scaling as O(N/Zβ), quadratically better than previous general-purpose algorithms using similar quantum resources. Moreover, since the coin is defined by a single observable, the method lends itself well to quantum error mitigation. We test this in practice with a proof-of-concept 9-qubit experiment, where we successfully mitigate errors through a simple noise-extrapolation procedure. Our findings offer an interesting alternative for quantum partition function estimation relevant to early-fault quantum hardware.
We consider the problem of estimating the partition function Z(β)=∑xexp(β(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(βmax)/Z(βmin)) can be estimated with accuracy ε using O(ε2qlogn) calls to an oracle that produces a sample from the Gibbs distribution for parameter β∈[β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(log2n)(logq+loglogn+ε−2)) samples. We improve the number of samples to O(ε2qlog2n) for a non-adaptive algorithm, and to 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.
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 problem of learning the Hamiltonian of a quantum many-body system given samples from its Gibbs (thermal) state. The classical analog of this problem, known as learning graphical models or Boltzmann machines, is a well-studied question in machine learning and statistics. In this work, we give the first sample-efficient algorithm for the quantum Hamiltonian learning problem. In particular, we prove that polynomially many samples in the number of particles (qudits) are necessary and sufficient for learning the parameters of a spatially local Hamiltonian in l_2-norm. Our main contribution is in establishing the strong convexity of the log-partition function of quantum many-body systems, which along with the maximum entropy estimation yields our sample-efficient algorithm. Classically, the strong convexity for partition functions follows from the Markov property of Gibbs distributions. This is, however, known to be violated in its exact form in the quantum case. We introduce several new ideas to obtain an unconditional result that avoids relying on the Markov property of quantum systems, at the cost of a slightly weaker bound. In particular, we prove a lower bound on the variance of quasi-local operators with respect to the Gibbs state, which might be of independent interest. Our work paves the way toward a more rigorous application of machine learning techniques to quantum many-body problems.
We give quantum algorithms that estimate the log partition function of an n-qubit quantum Hamiltonian to additive error ε with Heisenberg scaling, while minimizing calls to thermal-state purification preparation. The input is a block encoding of H, unitaries preparing thermofield-double states at chosen inverse temperatures, with their inverses and controlled versions, and an adaptive slowly-varying cooling schedule. The system-size bounds below assume 0⪯H⪯hI with h=O(n) and block-encoding normalization α=Θ(h). For constant inverse temperature, we show that such a schedule of length O(n) always exists and can be generated from overlap estimates with O(n) further preparations.
Given such a schedule and classically chosen temperatures, we estimate the log partition function with O(n5/4/ε) expected calls to state preparation and to the block encoding, improving by n1/4 on non-adaptive strategies. To achieve our result, we use a recursive-doubling identity that expresses each schedule increment as a weighted sum of logarithms of thermofield-double overlaps and of short imaginary-time steps implemented by quantum singular value transformation combined with previously developed variance reduction techniques. If thermofield doubles can be prepared controlled on a temperature register, a quantum inverse-binomial log estimator combined with quantum mean estimation reduces both query counts to O(n/ε). We show that the latter scaling is optimal in block-encoding queries up to polylogarithmic factors and discuss end-to-end complexities for one-dimensional partition-function estimation.