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\preceq H\preceq hI$ with $h=O(n)$ and block-encoding normalization $α=Θ(h)$. For constant inverse temperature, we show that such a schedule of length $O(\sqrt n)$ always exists and can be generated from overlap estimates with $\widetilde O(\sqrt n)$ further preparations.
Given such a schedule and classically chosen temperatures, we estimate the log partition function with $\widetilde O(n^{5/4}/ε)$ expected calls to state preparation and to the block encoding, improving by $n^{1/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 $\widetilde 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.
AI Summary
The paper studies estimating $f(\beta)=\ln\operatorname{Tr}(e^{-\beta H})$ to additive error $\epsilon$, equivalently estimating the partition function multiplicatively within $e^{\pm\epsilon}$. It assumes an $\alpha$-normalized block encoding of $0\preceq H\preceq hI$, with $\alpha=\Theta(h)$, and coherent access to canonical thermofield-double (TFD) preparations, including inverse and controlled operations.
For a supplied constant-overlap cooling schedule with $\ell$ intervals, reconstruction uses $\widetilde O(\sqrt{\ell}(\ell+h\beta)/\epsilon)$ expected TFD and block-encoding queries when temperatures are selected classically. If TFD preparation and reconstruction-term selection support coherent temperature registers, both counts become $\widetilde O((\ell+h\beta)/\epsilon)$. Adaptive overlap estimation constructs a schedule of length $O(1+\sqrt{h\beta})$ without a spectral-gap assumption. Thus, for $h=\Theta(n)$ and constant $\beta$, the bounds are $\widetilde O(n^{5/4}/\epsilon)$ and $\widetilde O(n/\epsilon)$.
The reconstruction recursively doubles short imaginary-time increments, combining QSVT-implemented reweighting probabilities with TFD overlaps. All probabilities remain bounded below by constants. The first algorithm allocates nearly unbiased estimation depths using variance bounds; the second coherently samples logarithms using truncated inverse-binomial harmonic estimators and quantum mean estimation. A hidden-energy-offset construction proves an $\Omega(\alpha\beta/\epsilon)$ block-query lower bound, matching the coherent algorithm up to logarithms.
Thermal-state preparation costs are separate resources, and coherent temperature selection can erase query savings through implementation overhead. A one-dimensional bounded-temperature construction gives gate bounds $\widetilde O(n^{9/4}/\epsilon)$ and $\widetilde O(n^2/\epsilon)$. The lower bound neither establishes preparation optimality nor separates the access models; it also excludes models supplying an exact ground-energy normalization.
Little sign of AI-generated textAI use disclosedStrong assumptions
OpenAI Codex with ChatGPT 5.6 and 6 Astra assisted with exploring and checking proof strategies, and with preparing the manuscript.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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.
The paper studies estimating f(β)=lnTr(e−βH) to additive error ϵ, equivalently estimating the partition function multiplicatively within e±ϵ. It assumes an α-normalized block encoding of 0⪯H⪯hI, with α=Θ(h), and coherent access to canonical thermofield-double (TFD) preparations, including inverse and controlled operations.
For a supplied constant-overlap cooling schedule with ℓ intervals, reconstruction uses O(ℓ(ℓ+hβ)/ϵ) expected TFD and block-encoding queries when temperatures are selected classically. If TFD preparation and reconstruction-term selection support coherent temperature registers, both counts become O((ℓ+hβ)/ϵ). Adaptive overlap estimation constructs a schedule of length O(1+hβ) without a spectral-gap assumption. Thus, for h=Θ(n) and constant β, the bounds are O(n5/4/ϵ) and O(n/ϵ).
The reconstruction recursively doubles short imaginary-time increments, combining QSVT-implemented reweighting probabilities with TFD overlaps. All probabilities remain bounded below by constants. The first algorithm allocates nearly unbiased estimation depths using variance bounds; the second coherently samples logarithms using truncated inverse-binomial harmonic estimators and quantum mean estimation. A hidden-energy-offset construction proves an Ω(αβ/ϵ) block-query lower bound, matching the coherent algorithm up to logarithms.
Thermal-state preparation costs are separate resources, and coherent temperature selection can erase query savings through implementation overhead. A one-dimensional bounded-temperature construction gives gate bounds O(n9/4/ϵ) and O(n2/ϵ). The lower bound neither establishes preparation optimality nor separates the access models; it also excludes models supplying an exact ground-energy normalization.
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.
Quantum computers have great potential to uncover new and unexpected physical phenomena.They can simulate classically intractable many-particle quantum systems and probe them in a programmable, computational manner.They can also process experimental quantum data directly, enabling us to probe unseen aspects of physical systems that cannot be reached by any classical means.In both roles, refining quantum algorithms toward their fundamental limits expands and sharpens the reach of quantum computers.Among quantum algorithms, quantum estimation is of central importance because it elicits the physical properties of interest from quantum systems.Even in an ideal, noiseless setting, however, obtaining precise estimates of such properties is significantly resource-intensive, unless one leverages coherent quantum operations.While many quantum-enhanced (i.e., higher performance than any classical means enabled by quantum effects) estimation algorithms have been proposed under reasonable access assumptions, it is still an ongoing quest to design quantum algorithms achieving ultimate estimation efficiency allowed by quantum mechanics.In addition, rapid experimental progress makes us envision an early fault-tolerant regime with large-scale yet not fully error-corrected quantum computers.Toward this regime, it is also crucial to develop quantum estimation algorithms that elicit as much information of interest as possible from a quantum system subject to noise.In these contexts, this thesis advances quantum-enhanced algorithms for estimating physical properties in two respects: Heisenberg-limited multi-observable estimation and single-observable estimation for the early faulttolerant quantum computing (FTQC) regime.First, we provide an adaptive quantum algorithm for estimating expectation values of multiple observables simultaneously in an ideal (noiseless) setting.Given common access to block-encoded observables, a state-preparation unitary, and its inverse, this algorithm achieves a double quantum enhancement in query complexity to the state preparation and its inverse: the mean-squared-error (MSE) scaling at the Heisenberg limit and sublinear scaling in the number of observables.It also essentially matches the query lower bound in the small-additive-error regime (not in MSE), previously derived in quantum complexity theory.In addition, the proposed algorithm significantly reduces the number of ancilla qubits and the classical computation for circuit synthesis, compared to prior art for this task.The double enhancement and the circuit simplification come from a novel algorithm design that integrates key ideas from adaptive phase estimation, quantum amplification, and quantum gradient estimation.Next, we focus on expectation value estimation for a single observable in the early FTQC regime.In this regime, available coherent resources are mostly consumed for a state preparation unitary, and the dominant noise stems from that costly unitary and its inverse.Under a specific model reflecting these aspects, we derive the quantum-enhanced precision limit, that is, the minimal quantum Cramér-Rao bound over all possible estimation strategies in the model.Then, by designing an adaptive optimization based on Fisher information, we propose a quantum-enhanced estimation algorithm, with rigorous estimation guarantees, that asymptotically achieves the quantum Cramér-Rao bound, when the target system size is sufficiently large.Finally, we numerically demonstrate that the asymptotic behavior holds with only a few hundred measurements per step and a few tens of qubits.
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 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.
In quantum mechanics, measuring the expectation value of a general observable has an inherent statistical uncertainty that is quantified by variance or mean squared error of measurement outcome. While the uncertainty can be reduced by averaging several samples, the number of samples should be minimized when each sample is very costly. This is especially the case for fault-tolerant quantum computing that involves measurement of multiple observables of nontrivial states in large quantum systems that exceed the capabilities of classical computers. In this work, we provide an adaptive quantum algorithm for estimating the expectation values of M general observables within root mean squared error ε simultaneously, using O ( ε − 1 M log M ) queries to a state preparation oracle of a target state. This remarkably achieves the scaling of Heisenberg limit 1 / ε , a fundamental bound on the estimation precision in terms of mean squared error, together with the sublinear scaling of the number of observables M . The proposed method is an adaptive version of the quantum gradient-estimation algorithm and has a resource-efficient implementation due to its adaptiveness. Specifically, the space overhead in the proposed method is O ( M ) , which is independent from the estimation precision ε unlike noniterative algorithms. In addition, our method can avoid the numerical instability problem for constructing quantum circuits in a large-scale task (e.g., ε ≪ 1 in our case), which appears in the actual implementation of many algorithms relying on quantum signal processing techniques. Our method paves a new way to precisely understand and predict various physical properties in complicated quantum systems using quantum computers.
We describe algorithms to obtain an approximate classical description of a d-dimensional quantum state when given access to a unitary (and its inverse) that prepares it. For pure states we characterize the query complexity for ℓq-norm error up to logarithmic factors. As a special case, we show that it takes applications of the unitaries to obtain an ε-ℓ2-approximation of the state. For mixed states we consider a similar model, where the unitary prepares a purification of the state. We characterize the query complexity for obtaining Schatten q-norm estimates of a rank-r mixed state, up to polylogarithmic factors. In particular, we show that a trace-norm (q = 1) estimate can be obtained with queries. This improves (assuming our stronger input model) the ε-dependence over the works of O'Donnell and Wright (STOC 2016) and Haah et al. (IEEE Trans. Inf. Theory, 63.9, 2017), that use a joint measurement on copies of the state. To our knowledge, the most sample-efficient results for pure-state tomography come from setting the rank to 1 in generic mixed-state tomography algorithms, which can require a large amount of computing resources. We describe sample-optimal algorithms for pure states that are simple and fast to implement. Along the way we show that an ℓ∞-norm estimate of a normalized vector induces a (slightly worse) ℓq-norm estimate for that vector, without losing a dimension-dependent factor in the precision. We also develop an unbiased and symmetric version of phase estimation, where the probability distribution of the estimate is centered around the true value. Finally, we give an efficient method for estimating multiple expectation values, improving over the recent result by Huggins et al. (arXiv:2111.09283) when the measurement operators do not fully overlap. More specifically, we show that for E1,…, Em normalized measurement operators, all expectation values Tr(Ejρ) can be efficiently learned up to error ε with applications of a state-preparation unitary for a purification of ρ. * The full version of the paper can be accessed at https://arxiv.org/abs/2207.08800