We introduce a classical algorithm to approximate the free energy of local, translation-invariant, one-dimensional quantum systems in the thermodynamic limit of infinite chain size. While the ground state problem (i.e., the free energy at temperature T=0 ) for these systems is expected to be computationally hard even for quantum computers, our algorithm runs for any fixed temperature T>0 in subpolynomial time, i.e., in time O((1ε)c) for any constant c>0 where ε is the additive approximation error. Previously, the best known algorithm had a runtime that is polynomial in 1ε . Our algorithm is also particularly simple as it reduces to the computation of the spectral radius of a linear map. This linear map has an interpretation as a noncommutative transfer matrix and has been studied previously to prove results on the analyticity of the free energy and the decay of correlations. We also show that the corresponding eigenvector of this map gives an approximation of the marginal of the Gibbs state and thereby allows for the computation of various thermodynamic properties of the quantum system.
We introduce a classical algorithm to approximate the free energy of local, translation-invariant, one-dimensional quantum systems in the thermodynamic limit of infinite chain size. While the ground state problem (i.e., the free energy at temperature T=0 ) for these systems is expected to be computationally hard even for quantum computers, our algorithm runs for any fixed temperature T>0 in subpolynomial time, i.e., in time O((1ε)c) for any constant c>0 where ε is the additive approximation error. Previously, the best known algorithm had a runtime that is polynomial in 1ε . Our algorithm is also particularly simple as it reduces to the computation of the spectral radius of a linear map. This linear map has an interpretation as a noncommutative transfer matrix and has been studied previously to prove results on the analyticity of the free energy and the decay of correlations. We also show that the corresponding eigenvector of this map gives an approximation of the marginal of the Gibbs state and thereby allows for the computation of various thermodynamic properties of the quantum system.
We introduce a classical algorithm to approximate the free energy of local, translation-invariant, one-dimensional quantum systems in the thermodynamic limit of infinite chain size. While the ground state problem (i.e., the free energy at temperature T=0) for these systems is expected to be computationally hard even for quantum computers, our algorithm runs for any fixed temperature T>0 in subpolynomial time, i.e., in time O((ε1)c) for any constant c>0 where ε is the additive approximation error. Previously, the best known algorithm had a runtime that is polynomial in ε1. Our algorithm is also particularly simple as it reduces to the computation of the spectral radius of a linear map. This linear map has an interpretation as a noncommutative transfer matrix and has been studied previously to prove results on the analyticity of the free energy and the decay of correlations. We also show that the corresponding eigenvector of this map gives an approximation of the marginal of the Gibbs state and thereby allows for the computation of various thermodynamic properties of the quantum system.
We consider the problem of approximating the free energy density of a translation-invariant, one-dimensional quantum spin system with finite range. While the complexity of this problem is nontrivial due to its close connection to problems with known hardness results, a classical subpolynomial-time algorithm has recently been proposed [Fawzi et al., 2022]. Combining several algorithmic techniques previously used for related problems, we propose an algorithm outperforming this result asymptotically and give rigorous bounds on its runtime. Our main techniques are the use of Araki expansionals, known from results on the nonexistence of phase transitions, and a matrix product operator construction. We also review a related approach using the Quantum Belief Propagation [Kuwahara et al., 2018], which in combination with our findings yields an equivalent result.
Despite progress in quantum Hamiltonian complexity, little is known about the computational complexity of quantum physics at the thermodynamic limit. Even defining the problem is not straight forward. We study the complexity of estimating the ground energy of a fixed, translationally invariant Hamiltonian in the thermodynamic limit, to within a given precision; the number of bits n for the precision is the sole input to the problem. The complexity of this problem captures how difficult it is for the physicist to measure or compute another digit in the approximation of a physical quantity in the thermodynamic limit. We show that this problem is contained in $\mbox{FEXP}^{\mbox{QMA-EXP}}$ and is hard for $\mbox{FEXP}^{\mbox{NEXP}}$. This means that the problem is doubly exponentially hard in the size of the input. As an ingredient in our construction, we study the problem of computing the ground energy of translationally invariant finite 1D chains. A single Hamiltonian term, which is a fixed parameter of the problem, is applied to every pair of particles in a finite chain. The length of the chain is the sole input to the problem and the task is to compute an approximation of the ground energy. No thresholds are provided as in the standard formulation of the local Hamiltonian problem. We show that this problem is contained in $\mbox{FP}^{\mbox{QMA-EXP}}$ and is hard for $\mbox{FP}^{\mbox{NEXP}}$. Our techniques employ a circular clock in which the ground energy is calibrated by the length of the cycle. This requires more precise expressions for the ground states of the resulting matrices than was required for previous QMA-completeness constructions and even exact analytical bounds for the infinite case which we derive using techniques from spectral graph theory. To our knowledge, this is the first use of the circuit-to-Hamiltonian construction which shows hardness for a function class.
Despite immense progress in quantum Hamiltonian complexity in the past decade, little is known about the computational complexity of quantum physics at the thermodynamic limit. In fact, even defining the problem properly is not straight forward. We study the complexity of estimating the ground energy of a fixed, translationally-invariant (TI) Hamiltonian in the thermodynamic limit, to within a given precision; this precision (given by n the number of bits of the approximation) is the sole input to the problem. Understanding the complexity of this problem captures how difficult it is for a physicist to measure or compute another digit in the approximation of a physical quantity in the thermodynamic limit. We show that this problem is contained in FEXP QMA-EXP and is hard for FEXP NEXP . This means that the problem is doubly exponentially hard in the size of the input. As an ingredient in our construction, we study the problem of computing the ground energy of translationally invariant finite 1D chains. A single Hamiltonian term, which is a fixed parameter of the problem, is applied to every pair of particles in a finite chain. In the finite case, the length of the chain is the sole input to the problem and the task is to compute an approximation of the ground energy. No thresholds are provided as in the standard formulation of the local Hamiltonian problem. We show that this problem is contained in FP QMA-EXP and is hard for FP NEXP . Our techniques employ a circular clock structure in which the ground energy is calibrated by the length of the cycle. This requires more precise expressions for the ground energies of the resulting matrices than were required for previous QMA-completeness constructions and even exact analytical bounds for the infinite case which we derive using techniques from spectral graph theory. To our knowledge, this is the first use of the circuit-to-Hamiltonian construction that shows hardness for a function class.
Predicting observables in equilibrium states is a central yet notoriously hard question in quantum many-body systems. In the physically relevant thermodynamic limit, certain mathematical formulations of this task have even been shown to result in undecidable problems. Using a finite-size scaling of algorithms devised for finite systems often fails due to the lack of certified convergence bounds for this limit. In this work, we design certified algorithms for computing expectation values of observables in the equilibrium states of local quantum Hamiltonians, both at zero and positive temperature. Importantly, our algorithms output rigorous lower and upper bounds on these values. This allows us to show that expectation values of local observables can be approximated in finite time, contrasting related undecidability results. When the Hamiltonian is commuting on a 2-dimensional lattice, we prove fast convergence of the hierarchy at high temperature and as a result for a desired precision ε, local observables can be approximated by a convex optimization program of quasi-polynomial size in 1/ε.
At high temperature, quantum Gibbs states retain several classical features of the maximally mixed state: the absence of entanglement, the absence of magic, analyticity of the partition function, correlation decay, and algorithmic tractability. We prove new and sharp bounds showing that these features persist down to finite temperatures independent of system size, but fail at distinct inverse-temperature scales, forming a hierarchy of classical-to-quantum transitions. Our results hold for long-range Pauli interactions with bounded strength at every site. Despite such all-to-all interactions, we show that the death of entanglement occurs at constant temperature, resolving an open question of Rouze, Franca and Alhambra (STOC'25). We give a polynomial-time classical algorithm that prepares Gibbs states up to the death of entanglement transition. Notably, this is asymptotically colder than temperatures at which quantum Gibbs samplers are known to mix quickly, as well as the original separability temperature of Bakshi et al. (FOCS'24), which we improve to be tight up to constants. At asymptotically even colder temperatures, we show that the Gibbs state remains in the thermodynamic infinite-temperature phase. We give polynomial-time classical algorithms for estimating thermal expectations up to the phase transition (despite both entanglement and magic), and as a corollary resolve a correlation decay conjecture of Harrow, Mehraban and Soleimanifar (STOC'20).