We present two algorithms, one quantum and one classical, for estimating partition functions of quantum spin Hamiltonians. The first is a DQC1 (deterministic quantum computation with one clean qubit) algorithm. The second, for real temperatures, achieves performance comparable to a state-of-the-art DQC1 algorithm [A. N. Chowdhury, R. D. Somma, and Y. Suba\ifmmode \mbox{\c{s}}\else \c{s}\fi{}i, Phys. Rev. A 103, 032422 (2021)]. Both our algorithms take as input the Hamiltonian decomposed as a linear combination Pauli operators. We show this decomposition to be DQC1-hard for a given Hamiltonian, providing insight into the hardness of estimating partition functions.
We present two algorithms, one quantum and one classical, for estimating partition functions of quantum spin Hamiltonians. The first is a DQC1 (deterministic quantum computation with one clean qubit) algorithm. The second, for real temperatures, achieves performance comparable to a state-of-the-art DQC1 algorithm [A. N. Chowdhury, R. D. Somma, and Y. Suba\ifmmode \mbox{\c{s}}\else \c{s}\fi{}i, Phys. Rev. A 103, 032422 (2021)]. Both our algorithms take as input the Hamiltonian decomposed as a linear combination Pauli operators. We show this decomposition to be DQC1-hard for a given Hamiltonian, providing insight into the hardness of estimating partition functions.
We study the computational complexity of estimating the normalized trace 2−nTr[f(A)] for a log-local Hamiltonian A acting on n qubits. This problem arises naturally in the DQC1 model, yet its complexity is only understood for a limited class of functions f(x).
We show that if f(x) is a continuous function with approximate degree Ω(poly(n)), then estimating 2−nTr[f(A)] up to constant additive error is DQC1-complete, under a technical condition on the polynomial approximation error of f(x). This condition holds for a broad class of functions, including exponentials, trigonometric functions, logarithms, and inverse-type functions. We further prove that when A is sparse, the classical query complexity of this problem is exponential in the approximate degree. Together, these results identify the approximate degree as the key parameter governing the complexity of normalized trace estimation: it characterizes both the quantum complexity (via efficient DQC1 algorithms) and the classical hardness, yielding an exponential quantum-classical separation. Our proof develops a unified framework that cleanly combines circuit-to-Hamiltonian constructions, periodic Jacobi operators, and tools from polynomial approximation theory, including the Chebyshev equioscillation theorem.
We present a method to approximate partition functions of quantum systems using mixed-state quantum computation. For positive-semidefinite Hamiltonians, our method has an expected running-time that is almost linear in ${[M/({\ensuremath{\epsilon}}_{\mathrm{rel}}\mathcal{Z})]}^{2}$, where M is the dimension of the quantum system, Z is the partition function, and ${\ensuremath{\epsilon}}_{\mathrm{rel}}$ is the relative precision. It is based on approximations of the exponential operator as linear combinations of certain operators related to block-encoding of Hamiltonians or Hamiltonian evolutions. The trace of each operator is estimated using a standard algorithm in the one-clean-qubit model. For large values of Z, our method may run faster than exact classical methods, whose complexities are polynomial in M. We also prove that a version of the partition function estimation problem within additive error is complete for the so-called DQC1 complexity class, suggesting that our method provides a superpolynomial speedup for certain parameter values. To attain a desired relative precision, we develop a classical procedure based on a sequence of approximations within predetermined additive errors that may be of independent interest.
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.
Quantum statistical mechanics allows us to extract thermodynamic information from a microscopic description of a many-body system. A key step is the calculation of the density of states, from which the partition function and all finite-temperature equilibrium thermodynamic quantities can be calculated. In this work, we devise and implement a quantum algorithm to perform an estimation of the density of states on a digital quantum computer which is inspired by the kernel polynomial method. Classically, the kernel polynomial method allows us to sample spectral functions via a Chebyshev polynomial expansion. Our algorithm computes moments of the expansion on quantum hardware using a combination of random-state preparation for stochastic trace evaluation and a controlled unitary operator. We use our algorithm to estimate the density of states of a nonintegrable Hamiltonian on the Quantinuum H1-1 trapped ion chip for a controlled register of 18 qubits. This not only represents a state-of-the-art calculation of thermal properties of a many-body system on quantum hardware, but also exploits the controlled unitary evolution of a many-qubit register on an unprecedented scale. Published by the American Physical Society 2024
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.
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.