⚛️ quantum physics

Improved Adaptive Estimation of Quantum Partition Functions with Heisenberg Scaling

This paper presents quantum algorithms that achieve Heisenberg scaling for estimating the log partition function of an $n$ -qubit Hamiltonian by utilizing an adaptive cooling schedule and recursive-doubling identities to reduce query complexity to $\widetilde O(n/\epsilon)$ , which is proven to be optimal up to polylogarithmic factors.

Original authors: Yufei Wang, Daniel Stilck França, Samuel Slezak

Published 2026-10-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yufei Wang, Daniel Stilck França, Samuel Slezak

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the quiet, invisible world of atoms and molecules, matter does not sit still. Even when a system appears frozen, its constituent particles are constantly jostling, exchanging energy, and settling into patterns dictated by temperature. Physicists have long sought a single number that captures the total behavior of such a system: the partition function. This value acts as a master key, unlocking the ability to calculate everything from the pressure of a gas to the stability of a protein. Knowing this number allows scientists to predict how a material will react to heat, how it will conduct electricity, or how it might fold into a complex shape. However, calculating this number for quantum systems—where particles exist in multiple states simultaneously—is notoriously difficult. As the number of particles grows, the complexity of the calculation explodes, often becoming impossible for even the most powerful supercomputers to handle in a reasonable time.

For decades, researchers have tried to build quantum computers to solve this problem, hoping to use the strange rules of quantum mechanics to speed up the process. The challenge has been that existing methods often required an impractical amount of time or resources, scaling poorly as the system grew larger. A new study by Yufei Wang, Daniel Stilck França, and Samuel Slezak offers a significant leap forward. They have developed a new quantum algorithm that can estimate this crucial number with unprecedented efficiency. Their method does not just work faster; it achieves a level of speedup that was previously thought to be the absolute limit of what is possible for this type of problem, known as Heisenberg scaling. This means that as they demand more precision, the time required grows much more slowly than with any previous approach, making it feasible to study larger and more complex quantum systems than ever before.

The core of the researchers' achievement lies in how they navigate the "cooling" of a quantum system. To find the partition function, one typically imagines cooling a system from a state of high energy down to a specific temperature, step by step. The difficulty is that if the steps are too large, the calculation becomes unstable and inaccurate; if they are too small, the process takes forever. The team devised a way to create a "slowly varying" schedule, a carefully mapped path of temperatures where the system changes just enough at each step to remain stable without wasting time. They proved that for a wide range of quantum systems, such a path always exists and can be found efficiently.

Once this path is established, the team's algorithm breaks the problem down into tiny, manageable pieces. Instead of trying to calculate the total energy change all at once, they measure the tiny shifts in probability that occur as the system moves from one temperature to the next. They use a clever mathematical trick, similar to doubling a number repeatedly, to reconstruct the full answer from these small steps. This approach allows them to avoid the need to resolve individual energy levels, which is a major hurdle in quantum computing. By focusing on the overlaps between different states of the system, they can extract the necessary information without getting bogged down in the details of every single particle.

The researchers explored two different ways to access the quantum system, leading to two versions of their algorithm. The first version works with a classical computer that tells the quantum machine which temperature to check next. This method is already a major improvement, reducing the number of required operations by a factor related to the square root of the system size compared to older strategies. However, the second version is even more powerful. In this approach, the quantum computer holds a superposition of many different temperatures at once, effectively checking multiple steps of the cooling path simultaneously. This coherent access allows the algorithm to estimate the final result with a speed that scales linearly with the system size, a dramatic improvement that matches the theoretical best-case scenario.

The team demonstrated that their method is not just a theoretical possibility but a practical recipe for building better quantum simulations. They showed that for one-dimensional chains of atoms, a common model in physics, their algorithm can be implemented with a manageable number of quantum gates. This means that as quantum hardware continues to improve, these algorithms will be ready to run on real machines. The work also clarifies the limits of what is possible, proving that their most efficient method is nearly optimal and cannot be significantly improved upon without changing the fundamental way the computer accesses the data.

This research bridges a critical gap between the theoretical potential of quantum computers and the practical needs of statistical physics. By providing a reliable, efficient way to calculate the partition function, the authors have opened the door to more accurate simulations of chemical reactions, material properties, and biological processes. Their work suggests that the era of using quantum computers to solve complex thermodynamic problems is closer than many anticipated, provided the hardware can keep pace with the algorithmic advances. The findings offer a clear path forward, turning a problem that was once considered intractable into one that can be solved with a level of precision and speed that was previously out of reach.

Technical Summary: Improved Adaptive Estimation of Quantum Partition Functions with Heisenberg Scaling

1. Problem Statement

The paper addresses the fundamental problem of estimating the log partition function, $f(\beta) = \ln Z(\beta)$ , for an $n$ -qubit quantum Hamiltonian $H$ at inverse temperature $\beta$ . The partition function $Z(\beta) = \text{Tr}(e^{-\beta H})$ determines free energy and encodes equilibrium thermodynamics. The goal is to achieve Heisenberg scaling in precision, i.e., an additive error $\epsilon$ with query complexity scaling as $\tilde{O}(1/\epsilon)$ , while minimizing dependence on system size $n$ and resources related to thermal state access.

The work operates under the assumption that the Hamiltonian is supplied via an $\alpha$ -block encoding (where $\alpha = \Theta(h)$ and $0 \preceq H \preceq hI$ ) and distinguishes between two access models for thermal states:

Fixed-temperature coherent access: The algorithm chooses a temperature classically and accesses a unitary $U_\theta$ preparing the thermofield-double (TFD) state $|\psi_\theta\rangle$ .
Coherent-temperature access: The inverse temperature is stored in a quantum register, allowing a unitary $U_{\text{coh}}$ to prepare a superposition of TFD states $|\theta\rangle|\psi_\theta\rangle$ coherently.

2. Methodology and Algorithmic Framework

2.1 The Reconstruction Framework

The core contribution is a reconstruction framework that expresses the log partition function as a telescopic sum over a slowly-varying cooling schedule $0 = \beta_0 < \dots < \beta_\ell = \beta$ . A schedule is $C$ -slowly varying if the squared overlap between adjacent TFD states is bounded below by $1/C$ .

The increment $f(\beta_{i+1}) - f(\beta_i)$ is decomposed using a recursive-doubling identity. This identity expresses the increment as a weighted sum of:

Overlaps: $O(\theta, s) = |\langle \psi_\theta | \psi_{\theta+s} \rangle|^2$ , related to the second finite difference of $f$ .
Reweighting ratios: $R(\theta, s) = \text{Tr}(\rho_\theta e^{-sH})$ , related to the first difference of $f$ .

Specifically, for an interval $\Delta_i = \beta_{i+1} - \beta_i$ , the authors choose a step size $\delta_i$ such that $h\delta_i \leq 1$ and an integer $k_i$ such that $2^{k_i}\delta_i = \Delta_i$ . The increment is reconstructed as:
$f(\beta_{i+1}) - f(\beta_i) = 2^{k_i} B(\beta_i, \delta_i) + \sum_{j=1}^{k_i} 2^{k_i-j} A(\beta_i, 2^j \delta_i)$
where $A = -\ln O$ and $B = \ln R$ . This decomposition ensures that all probabilities involved remain uniformly bounded away from zero, allowing for stable logarithmic estimation.

2.2 Estimation Strategies

The paper proposes two algorithms based on the access model:

A. Fixed-Temperature Algorithm (Algorithm 2)

Approach: Estimates each logarithmic term ( $A$ and $B$ ) independently using nearly unbiased quantum amplitude estimators (based on Cornelissen and Hamoudi [10]).
Variance Allocation: The estimation depth for each term is allocated adaptively based on the reconstruction coefficients ( $a_{i,j}$ ) to minimize total query cost while controlling the variance of the weighted sum.
Mechanism: Uses Quantum Singular Value Transformation (QSVT) to implement the short imaginary-time reweighting steps required for $B$ .

B. Coherent-Temperature Algorithm (Algorithm 3)

Approach: Avoids estimating terms separately. Instead, it prepares a superposition over all reconstruction terms with probabilities proportional to their coefficients.
Estimator: Utilizes a quantum inverse-binomial log estimator. For each branch, it performs repeated coherent trials to count failures before the first success, converting this count into a harmonic number that approximates the negative logarithm of the success probability.
Aggregation: Applies quantum mean estimation (Montanaro [19]) directly to the weighted sum of these samples. This eliminates the $\sqrt{\ell}$ factor associated with summing independent estimates.

2.3 Schedule Generation

The authors adapt the adaptive cooling schedule generation procedure of Arunachalam et al. [2] to real-valued spectra. Using binary search on TFD overlap estimates, they construct a schedule of length $\ell = \tilde{O}(\sqrt{n})$ for extensive Hamiltonians at constant temperature, without requiring a spectral gap assumption.

3. Key Results and Complexity Bounds

Assuming an extensive bound $h = O(n)$ and constant inverse temperature $\beta = \Theta(1)$ , the expected query complexities (calls to state preparation and block encoding) are:

Access Model	Query Complexity	Comparison
Fixed-Temperature	$\tilde{O}\left(\frac{n^{5/4}}{\epsilon}\right)$	Improves upon non-adaptive strategies by a factor of $n^{1/4}$ .
Coherent-Temperature	$\tilde{O}\left(\frac{n}{\epsilon}\right)$	Matches the theoretical lower bound up to polylogarithmic factors.

Lower Bound Optimality:
The paper establishes a lower bound of $\Omega(\alpha \beta / \epsilon)$ for block-encoding queries in a hidden-offset model. For $\alpha = \Theta(n)$ , the coherent-temperature algorithm achieves $\tilde{O}(n/\epsilon)$ , proving it is optimal up to polylogarithmic factors. The fixed-temperature algorithm is within a factor of $\tilde{O}(n^{1/4})$ of this benchmark.

Circuit Complexity (1D Spin Chains):
For one-dimensional systems with efficient TFD preparation (e.g., via quasi-adiabatic continuation), the authors translate query bounds to gate counts.

Fixed-Temperature: $\tilde{O}(n^{9/4}/\epsilon)$ gates.
Coherent-Temperature: $\tilde{O}(n^2/\epsilon)$ gates.
The coherent method retains an $n^{1/4}$ advantage in gate count, provided the coherent TFD preparation does not incur excessive overhead (achievable via shared circuit structures with parameterized angles).

4. Significance and Claims

The paper claims to extend adaptive quantum algorithms for partition-function estimation from classical Gibbs distributions to general quantum Hamiltonians accessed via block encodings. Its significance lies in:

Removing Classical Assumptions: Unlike prior works relying on integer spectra or efficient energy evaluation, this method uses smooth quantities (TFD overlaps and reweighting) implementable via QSVT, avoiding the need to resolve individual energy levels.
Heisenberg Scaling: It achieves the optimal $1/\epsilon$ scaling for general quantum Hamiltonians, a significant improvement over previous quadratic scaling in precision.
Optimality in Stronger Models: It demonstrates that coherent temperature control is a genuine resource, achieving the theoretical lower bound for block-encoding queries, whereas fixed-temperature access incurs a polynomial penalty in system size.
Practical Applicability: The framework includes a complete pipeline from schedule generation to end-to-end circuit resource estimates for 1D systems, showing that the theoretical query advantages can translate to gate-count improvements.

The authors note that while the coherent-temperature model offers optimal scaling, its implementation overhead is non-trivial. They provide a sufficient condition (Proposition 7.1) and a concrete construction for 1D spin chains (Proposition 8.1) where this overhead is manageable, preserving the asymptotic advantage.