Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2403.10018 · Physical review. B./Physical review. B

Sample complexity of matrix product states at finite temperature

Atsushi Iwaki, Chisa Hotta

Published Jun 7, 2024• 2 citations
arXivHTMLPDF

Abstract

For quantum many-body systems in one dimension, computational complexity theory reveals that the evaluation of ground-state energy remains elusive on quantum computers, contrasting the existence of a classical algorithm for temperatures higher than the inverse logarithm of the system size. This highlights a qualitative difference between low- and high-temperature states in terms of computational complexity. Here, we describe finite-temperature states using the matrix product state formalism. Within the framework of random samplings, we derive an analytical formula for the required number of samples which provides both quantitative and qualitative measures of computational complexity. At high and low temperatures, its scaling behavior with system size is linear and quadratic, respectively, demonstrating a distinct crossover between these numerically difficult regimes of quantitative difference.

DOI
10.1103/physrevb.109.224410

Related papers

Pure state thermodynamics with matrix product states

Silvano Garnerone

We extend the formalism of pure state thermodynamics to matrix product states. In pure state thermodynamics finite-temperature properties of quantum systems are derived without the need of statistical mechanic ensembles, but instead using typical properties of random pure states. We show that this formalism can be useful from a computational point of view when combined with tensor network algorithms. In particular, a recently introduced Monte Carlo algorithm is considered which samples matrix product states at random for the estimation of finite-temperature observables. Here we analytically justify the effectiveness of this algorithm, and we prove that sampling one single state is in principle sufficient to obtain a very good estimation of finite-temperature expectation values. These results provide a substantial computational improvement with respect to similar algorithms for one-dimensional quantum systems based on uniformly distributed pure states. The analytical calculations are numerically supported, simulating finite-temperature interacting spin systems of size up to 100 qubits.

arXiv:1309.0851•Physical Review B•Oct 30, 2013•11 citations

Finite-Temperature Matrix Product State Algorithms and Applications

Michael L. Wall, Lincoln D. Carr

We review the basic theory of matrix product states (MPS) as a nu-merical variational ansatz for time evolution, and present two methods to simulate finite temperature systems with MPS: the ancilla method and the minimally entangled typical thermal state method. A sample calculation with the Bose-Hubbard model is provided. The dimension of the Hilbert space for a general many-body system in-creases exponentially with the system size, severely restricting the sizes which are amenable to straightforward numerical study. Several techniques have been developed to deal with this fact, such as the stochastic sam-

Cold atoms•Mar 18, 2013•1 citation

Polynomial-time classical sampling of high-temperature quantum Gibbs states

Chao Nan Yin, Andrew Lucas

The computational complexity of simulating quantum many-body systems generally scales exponentially with the number of particles. This enormous computational cost prohibits first principles simulations of many important problems throughout science, ranging from simulating quantum chemistry to discovering the thermodynamic phase diagram of quantum materials or high-density neutron stars. We present a classical algorithm that samples from a high-temperature quantum Gibbs state in a computational (product state) basis. The runtime grows polynomially with the number of particles, while error vanishes polynomially. This algorithm provides an alternative strategy to existing quantum Monte Carlo methods for overcoming the sign problem. Our result implies that measurement-based quantum computation on a Gibbs state can provide exponential speed up only at sufficiently low temperature, and further constrains what tasks can be exponentially faster on quantum computers.

arXiv:2305.18514•May 29, 2023•1 citation

Classical simulation of quantum many-body systems

Yichen Huang

Classical simulation of quantum many-body systems is in general a challenging problem for the simple reason that the dimension of the Hilbert space grows exponentially with the system size. In particular, merely encoding a generic quantum many-body state requires an exponential number of bits. However, condensed matter physicists are mostly interested in local Hamiltonians and especially their ground states, which are highly non-generic. Thus, we might hope that at least some physical systems allow efficient classical simulation.Starting with one-dimensional (1D) quantum systems (i.e., the simplest nontrivial case), the first basic question is: Which classes of states have efficient classical representations? It turns out that this question is quantitatively related to the amount of entanglement in the state, for states with ``little entanglement'' are well approximated by matrix product states (a data structure that can be manipulated efficiently on a classical computer). At a technical level, the mathematical notion for ``little entanglement'' is area law, which has been proved for unique ground states in 1D gapped systems. We establish an area law for constant-fold degenerate ground states in 1D gapped systems and thus explain the effectiveness of matrix-product-state methods in (e.g.) symmetry breaking phases. This result might not be intuitively trivial as degenerate ground states in gapped systems can be long-range correlated.Suppose an efficient classical representation exists. How can one find it efficiently? The density matrix renormalization group is the leading numerical method for computing ground states in 1D quantum systems. However, it is a heuristic algorithm and the possibility that it may fail in some cases cannot be completely ruled out. Recently, a provably efficient variant of the density matrix renormalization group has been developed for frustration-free 1D gapped systems. We generalize this algorithm to all (i.e., possibly frustrated) 1D gapped systems. Note that the ground-state energy of 1D gapless Hamiltonians is computationally intractable even in the presence of translational invariance.It is tempting to extend methods and tools in 1D to two and higher dimensions (2+D), e.g., matrix product states are generalized to tensor network states. Since an area law for entanglement (if formulated properly) implies efficient matrix product state representations in 1D, an interesting question is whether a similar implication holds in 2+D. Roughly speaking, we show that an area law for entanglement (in any reasonable formulation) does not always imply efficient tensor network representations of the ground states of 2+D local Hamiltonians even in the presence of translational invariance. It should be emphasized that this result does not contradict with the common sense that in practice quantum states with more entanglement usually require more space to be stored classically; rather, it demonstrates that the relationship between entanglement and efficient classical representations is still far from being well understood.Excited eigenstates participate in the dynamics of quantum systems and are particularly relevant to the phenomenon of many-body localization (absence of transport at finite temperature in strongly correlated systems). We study the entanglement of excited eigenstates in random spin chains and expect that its singularities coincide with dynamical quantum phase transitions. This expectation is confirmed in the disordered quantum Ising chain using both analytical and numerical methods.Finally, we study the problem of generating ground states (possibly with topological order) in 1D gapped systems using quantum circuits. This is an interesting problem both in theory and in practice. It not only characterizes the essential difference between the entanglement patterns that give rise to trivial and nontrivial topological order, but also quantifies the difficulty of preparing quantum states with a quantum computer (in experiments).

•Jan 1, 2015•19 citations

One-dimensional quantum systems at finite temperatures can be simulated efficiently on classical computers

Thomas Barthel

It is by now well-known that ground states of gapped one-dimensional (1d) quantum-many body systems with short-range interactions can be studied efficiently using classical computers and matrix product state techniques. A corresponding result for finite temperatures was missing. Using the replica trick in 1+1d quantum field theory, it is shown here that the cost for the classical simulation of 1d systems at finite temperatures grows in fact only polynomially with the inverse temperature and is system-size independent -- even for gapless systems. In particular, we show that the thermofield double state (TDS), a purification of the equilibrium density operator, can be obtained efficiently in matrix-product form. The argument is based on the scaling behavior of Rényi entanglement entropies in the TDS. At finite temperatures, they obey the area law. For gapless systems with central charge $c$, the entanglement is found to grow only logarithmically with inverse temperature, $S_α\sim \frac{c}{6}(1+1/α)\log β$. The field-theoretical results are tested and confirmed by quasi-exact numerical computations for integrable and non-integrable spin systems, and interacting bosons.

arXiv:1708.09349•Aug 30, 2017•21 citations

Tensor Network Formulation of Dequantized Algorithms for Ground State Energy Estimation

Hidetaka Manabe, Takanori Sugimoto, Keisuke Fujii

Verifying quantum advantage for practical problems, particularly the ground state energy estimation (GSEE) problem, is one of the central challenges in quantum computing theory. For that purpose, dequantization algorithms play a central role in providing a clear theoretical framework to separate the complexity of quantum and classical algorithms. However, existing dequantized algorithms typically rely on sampling procedures, leading to prohibitively large computational overheads and hindering their practical implementation on classical computers. In this work, we propose a tensor network-based dequantization framework for GSEE that eliminates the sampling process while preserving the asymptotic complexity of prior dequantized algorithms. In our formulation, the overhead arising from sampling is replaced by the growth of the bond dimension required to represent Chebyshev vectors as tensor network states. Consequently, physical structure, such as entanglement and locality, is naturally reflected in the computational cost. By combining this approach with tensor network approximations, such as Matrix Product States (MPS), we construct a practical dequantization algorithm that is executable within realistic computational resources. Numerical simulations demonstrate that our method can efficiently construct high-degree polynomials up to $d=10^4$ for Hamiltonians with up to $100$ qubits, explicitly revealing the crossover between classically tractable and quantum advantaged regimes. These results indicate that tensor network-based dequantization provides a crucial tool toward the rigorous, quantitative verification of quantum advantage in realistic many-body systems.

quant-pharXiv:2512.13548•Dec 16, 2025•0 citations
For quantum many-body systems in one dimension, computational complexity theory reveals that the evaluation of ground-state energy remains elusive on quantum computers, contrasting the existence of a classical algorithm for temperatures higher than the inverse logarithm of the system size. This highlights a qualitative difference between low- and high-temperature states in terms of computational complexity. Here, we describe finite-temperature states using the matrix product state formalism. Within the framework of random samplings, we derive an analytical formula for the required number of samples which provides both quantitative and qualitative measures of computational complexity. At high and low temperatures, its scaling behavior with system size is linear and quadratic, respectively, demonstrating a distinct crossover between these numerically difficult regimes of quantitative difference.
We extend the formalism of pure state thermodynamics to matrix product states. In pure state thermodynamics finite-temperature properties of quantum systems are derived without the need of statistical mechanic ensembles, but instead using typical properties of random pure states. We show that this formalism can be useful from a computational point of view when combined with tensor network algorithms. In particular, a recently introduced Monte Carlo algorithm is considered which samples matrix product states at random for the estimation of finite-temperature observables. Here we analytically justify the effectiveness of this algorithm, and we prove that sampling one single state is in principle sufficient to obtain a very good estimation of finite-temperature expectation values. These results provide a substantial computational improvement with respect to similar algorithms for one-dimensional quantum systems based on uniformly distributed pure states. The analytical calculations are numerically supported, simulating finite-temperature interacting spin systems of size up to 100 qubits.
We review the basic theory of matrix product states (MPS) as a nu-merical variational ansatz for time evolution, and present two methods to simulate finite temperature systems with MPS: the ancilla method and the minimally entangled typical thermal state method. A sample calculation with the Bose-Hubbard model is provided. The dimension of the Hilbert space for a general many-body system in-creases exponentially with the system size, severely restricting the sizes which are amenable to straightforward numerical study. Several techniques have been developed to deal with this fact, such as the stochastic sam-
The computational complexity of simulating quantum many-body systems generally scales exponentially with the number of particles. This enormous computational cost prohibits first principles simulations of many important problems throughout science, ranging from simulating quantum chemistry to discovering the thermodynamic phase diagram of quantum materials or high-density neutron stars. We present a classical algorithm that samples from a high-temperature quantum Gibbs state in a computational (product state) basis. The runtime grows polynomially with the number of particles, while error vanishes polynomially. This algorithm provides an alternative strategy to existing quantum Monte Carlo methods for overcoming the sign problem. Our result implies that measurement-based quantum computation on a Gibbs state can provide exponential speed up only at sufficiently low temperature, and further constrains what tasks can be exponentially faster on quantum computers.
Classical simulation of quantum many-body systems is in general a challenging problem for the simple reason that the dimension of the Hilbert space grows exponentially with the system size. In particular, merely encoding a generic quantum many-body state requires an exponential number of bits. However, condensed matter physicists are mostly interested in local Hamiltonians and especially their ground states, which are highly non-generic. Thus, we might hope that at least some physical systems allow efficient classical simulation.Starting with one-dimensional (1D) quantum systems (i.e., the simplest nontrivial case), the first basic question is: Which classes of states have efficient classical representations? It turns out that this question is quantitatively related to the amount of entanglement in the state, for states with ``little entanglement'' are well approximated by matrix product states (a data structure that can be manipulated efficiently on a classical computer). At a technical level, the mathematical notion for ``little entanglement'' is area law, which has been proved for unique ground states in 1D gapped systems. We establish an area law for constant-fold degenerate ground states in 1D gapped systems and thus explain the effectiveness of matrix-product-state methods in (e.g.) symmetry breaking phases. This result might not be intuitively trivial as degenerate ground states in gapped systems can be long-range correlated.Suppose an efficient classical representation exists. How can one find it efficiently? The density matrix renormalization group is the leading numerical method for computing ground states in 1D quantum systems. However, it is a heuristic algorithm and the possibility that it may fail in some cases cannot be completely ruled out. Recently, a provably efficient variant of the density matrix renormalization group has been developed for frustration-free 1D gapped systems. We generalize this algorithm to all (i.e., possibly frustrated) 1D gapped systems. Note that the ground-state energy of 1D gapless Hamiltonians is computationally intractable even in the presence of translational invariance.It is tempting to extend methods and tools in 1D to two and higher dimensions (2+D), e.g., matrix product states are generalized to tensor network states. Since an area law for entanglement (if formulated properly) implies efficient matrix product state representations in 1D, an interesting question is whether a similar implication holds in 2+D. Roughly speaking, we show that an area law for entanglement (in any reasonable formulation) does not always imply efficient tensor network representations of the ground states of 2+D local Hamiltonians even in the presence of translational invariance. It should be emphasized that this result does not contradict with the common sense that in practice quantum states with more entanglement usually require more space to be stored classically; rather, it demonstrates that the relationship between entanglement and efficient classical representations is still far from being well understood.Excited eigenstates participate in the dynamics of quantum systems and are particularly relevant to the phenomenon of many-body localization (absence of transport at finite temperature in strongly correlated systems). We study the entanglement of excited eigenstates in random spin chains and expect that its singularities coincide with dynamical quantum phase transitions. This expectation is confirmed in the disordered quantum Ising chain using both analytical and numerical methods.Finally, we study the problem of generating ground states (possibly with topological order) in 1D gapped systems using quantum circuits. This is an interesting problem both in theory and in practice. It not only characterizes the essential difference between the entanglement patterns that give rise to trivial and nontrivial topological order, but also quantifies the difficulty of preparing quantum states with a quantum computer (in experiments).
It is by now well-known that ground states of gapped one-dimensional (1d) quantum-many body systems with short-range interactions can be studied efficiently using classical computers and matrix product state techniques. A corresponding result for finite temperatures was missing. Using the replica trick in 1+1d quantum field theory, it is shown here that the cost for the classical simulation of 1d systems at finite temperatures grows in fact only polynomially with the inverse temperature and is system-size independent -- even for gapless systems. In particular, we show that the thermofield double state (TDS), a purification of the equilibrium density operator, can be obtained efficiently in matrix-product form. The argument is based on the scaling behavior of Rényi entanglement entropies in the TDS. At finite temperatures, they obey the area law. For gapless systems with central charge ccc, the entanglement is found to grow only logarithmically with inverse temperature, Sα∼c6(1+1/α)log⁡βS_α\sim \frac{c}{6}(1+1/α)\log βSα​∼6c​(1+1/α)logβ. The field-theoretical results are tested and confirmed by quasi-exact numerical computations for integrable and non-integrable spin systems, and interacting bosons.
Verifying quantum advantage for practical problems, particularly the ground state energy estimation (GSEE) problem, is one of the central challenges in quantum computing theory. For that purpose, dequantization algorithms play a central role in providing a clear theoretical framework to separate the complexity of quantum and classical algorithms. However, existing dequantized algorithms typically rely on sampling procedures, leading to prohibitively large computational overheads and hindering their practical implementation on classical computers. In this work, we propose a tensor network-based dequantization framework for GSEE that eliminates the sampling process while preserving the asymptotic complexity of prior dequantized algorithms. In our formulation, the overhead arising from sampling is replaced by the growth of the bond dimension required to represent Chebyshev vectors as tensor network states. Consequently, physical structure, such as entanglement and locality, is naturally reflected in the computational cost. By combining this approach with tensor network approximations, such as Matrix Product States (MPS), we construct a practical dequantization algorithm that is executable within realistic computational resources. Numerical simulations demonstrate that our method can efficiently construct high-degree polynomials up to d=104d=10^4d=104 for Hamiltonians with up to 100100100 qubits, explicitly revealing the crossover between classically tractable and quantum advantaged regimes. These results indicate that tensor network-based dequantization provides a crucial tool toward the rigorous, quantitative verification of quantum advantage in realistic many-body systems.