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:1907.04862

A polynomial-time algorithm for ground states of spin trees

Nilin Abrahamsen

Published Jul 10, 2019• 11 citations
arXivHTMLPDF

Abstract

We prove that the ground states of a local Hamiltonian satisfy an area law and can be computed in polynomial time when the interaction graph is a tree with discrete fractal dimension $β<2$. This condition is met for generic trees in the plane and for established models of hyperbranched polymers in 3D. This work is the first to prove an area law and exhibit a provably polynomial-time classical algorithm for local Hamiltonian ground states beyond the case of spin chains. Our algorithm outputs the ground state encoded as a multi-scale tensor network on the META-tree, which we introduce as an analogue of Vidal's MERA. Our results hold for polynomially degenerate and frustrated ground states, matching the state of the art for local Hamiltonians on a line.

DOI
10.48550/arxiv.1907.04862

Related papers

Ground states of unfrustrated spin Hamiltonians satisfy an area law

Niel de Beaudrap, Tobias J. Osborne, Jens Eisert

We show that ground states of unfrustrated quantum spin-1/2 systems on general lattices satisfy an entanglement area law, provided that the Hamiltonian can be decomposed into nearest-neighbor interaction terms that have entangled excited states. The ground state manifold can be efficiently described as the image of a low-dimensional subspace of low Schmidt measure, under an efficiently contractible tree-tensor network. This structure gives rise to the possibility of efficiently simulating the complete ground space (which is in general degenerate). We briefly discuss 'non-generic' cases, including highly degenerate interactions with product eigenbases, using a relationship to percolation theory. We finally assess the possibility of using such tree tensor networks to simulate almost frustration-free spin models.

arXiv:1009.3051•New Journal of Physics•Sep 16, 2010•30 citations

Rigorous RG Algorithms and Area Laws for Low Energy Eigenstates in 1D

Itai Arad, Zeph Landau, Umesh Vazirani +1 more

One of the central challenges in the study of quantum many-body systems is the complexity of simulating them on a classical computer. A recent advance (Landau et al. in Nat Phys, 2015) gave a polynomial time algorithm to compute a succinct classical description for unique ground states of gapped 1D quantum systems. Despite this progress many questions remained unsolved, including whether there exist efficient algorithms when the ground space is degenerate (and of polynomial dimension in the system size), or for the polynomially many lowest energy states, or even whether such states admit succinct classical descriptions or area laws. In this paper we give a new algorithm, based on a rigorously justified RG type transformation, for finding low energy states for 1D Hamiltonians acting on a chain of n particles. In the process we resolve some of the aforementioned open questions, including giving a polynomial time algorithm for poly(n) degenerate ground spaces and an n O(log n) algorithm for the poly(n) lowest energy states (under a mild density condition). For these classes of systems the existence of a succinct classical description and area laws were not rigorously proved before this work. The algorithms are natural and efficient, and for the case of finding unique ground states for frustration-free Hamiltonians the running time is $${\tilde{O}(nM(n))}$$ , where M(n) is the time required to multiply two n × n matrices.

arXiv:1602.08828•Communications in Mathematical Physics•Aug 2, 2017•92 citations

Polynomial-time degenerate ground state approximation of gapped 1D Hamiltonians.

Christopher T. Chubb, Steven T. Flammia

In spite of a plethora of no-go results that prevent classically efficient simulation of quantum systems in general, heuristic methods[1] have seen great success, proving typically efficient in practice. The downside of these heuristic methods is that we lack a rigorous understanding of how, and for which systems, they fail[2]. Provably efficient algorithms – even if practically surpassed by heuristic methods – are of key importance for understanding the true worst-case complexity of simulation. The cutting edge for provably efficient simulation is the ground state approximation of 1D spin systems. Under the assumption of a gap, there exists a provably efficient algorithm[3, 4] for approximation of a unique ground state of such systems; we present ongoing work to extend this algorithm to work for degenerate systems. This result comes in the wake of a recent degenerate extension of the area law[5], an important structural bound on the complexity of ground states. In practice this algorithm is no match for heuristic analogues such as the density matrix renormalisation group. However, it does add to the increasing understanding of the systems for which provably efficient simulation is attainable, and might hopefully lead to a future algorithm that is both provably and practically efficient.

•Jan 1, 2014•0 citations

Simulation of two-dimensional quantum systems using a tree tensor network that exploits the entropic area law

Luca Tagliacozzo, Glen Evenbly, Guifré Vidal

This work explores the use of a tree tensor network ansatz to simulate the ground state of a local Hamiltonian on a two-dimensional lattice. By exploiting the entropic area law, the tree tensor network ansatz seems to produce quasiexact results in systems with sizes well beyond the reach of exact diagonalization techniques. We describe an algorithm to approximate the ground state of a local Hamiltonian on a $L\ifmmode\times\else\texttimes\fi{}L$ lattice with the topology of a torus. Accurate results are obtained for $L={4,6,8}$, whereas approximate results are obtained for larger lattices. As an application of the approach, we analyze the scaling of the ground-state entanglement entropy at the quantum critical point of the model. We confirm the presence of a positive additive constant to the area law for half a torus. We also find a logarithmic additive correction to the entropic area law for a square block. The single copy entanglement for half a torus reveals similar corrections to the area law with a further term proportional to $1/L$.

arXiv:0903.5017•Physical Review B•Dec 18, 2009•298 citations

2D Local Hamiltonian with Area Laws Is QMA-Complete

Yichen Huang

We show that the 2D local Hamiltonian problem with the constraint that the ground state obeys area laws is QMA-complete. We also prove similar results in 2D translation- invariant systems and for the 3D Heisenberg and Hubbard models with local magnetic fields. Consequently, unless MA = QMA, not all ground states of 2D local Hamiltonians with area laws have efficient classical representations that support efficient computation of local expectation values. In the future, even if area laws are proved for ground states of 2D gapped systems, the computational complexity of these systems remains unclear.

arXiv:1411.6614•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•6 citations

Area laws and tensor networks for maximally mixed ground states

Itai Arad, Raz Firanko, Rahul Jain

We show an area law in the mutual information for the maximally-mixed state $Ω$ in the ground space of general Hamiltonians, which is independent of the underlying ground space degeneracy. Our result assumes the existence of a `good' approximation to the ground state projector (a good AGSP), a crucial ingredient in previous area-law proofs. Such approximations have been explicitly derived for 1D gapped local Hamiltonians and 2D frustration-free locally-gapped Hamiltonians. As a corollary, we show that in 1D gapped local Hamiltonians, for any $\varepsilon>0$ and any bi-partition $L\cup L^c$ of the system, \begin{align*} \mathrm I_{\max}^\varepsilon (L:L^c)_Ω \le \mathrm O \big( \log (|L|\log(d))+\log(1/\varepsilon)\big), \end{align*} where $|L|$ represents the number of sites in $L$, $d$ is the dimension of a site and $ \mathrm I_{\max}^\varepsilon (L:L^c)_Ω $ represents the $\varepsilon$-\emph{smoothed maximum mutual information} with respect to the $L:L^c$ partition in $Ω$. From this bound we then conclude $\mathrm I (L:L^c)_Ω \le \mathrm O\big(\log(|L|\log(d))\big)$ -- an area law for the mutual information in 1D systems with a logarithmic correction. In addition, we show that $Ω$ can be approximated in trace norm up to $\varepsilon$ with a state of Schmidt rank of at most $\mathrm{poly}(|L|/\varepsilon)$, leading to a good MPO approximation for $Ω$ with polynomial bond dimension. Similar corollaries are derived for the mutual information of 2D frustration-free and locally-gapped local Hamiltonians.

arXiv:2310.19028•Oct 29, 2023•1 citation
We prove that the ground states of a local Hamiltonian satisfy an area law and can be computed in polynomial time when the interaction graph is a tree with discrete fractal dimension β<2β<2β<2. This condition is met for generic trees in the plane and for established models of hyperbranched polymers in 3D. This work is the first to prove an area law and exhibit a provably polynomial-time classical algorithm for local Hamiltonian ground states beyond the case of spin chains. Our algorithm outputs the ground state encoded as a multi-scale tensor network on the META-tree, which we introduce as an analogue of Vidal's MERA. Our results hold for polynomially degenerate and frustrated ground states, matching the state of the art for local Hamiltonians on a line.
We show that ground states of unfrustrated quantum spin-1/2 systems on general lattices satisfy an entanglement area law, provided that the Hamiltonian can be decomposed into nearest-neighbor interaction terms that have entangled excited states. The ground state manifold can be efficiently described as the image of a low-dimensional subspace of low Schmidt measure, under an efficiently contractible tree-tensor network. This structure gives rise to the possibility of efficiently simulating the complete ground space (which is in general degenerate). We briefly discuss 'non-generic' cases, including highly degenerate interactions with product eigenbases, using a relationship to percolation theory. We finally assess the possibility of using such tree tensor networks to simulate almost frustration-free spin models.
One of the central challenges in the study of quantum many-body systems is the complexity of simulating them on a classical computer. A recent advance (Landau et al. in Nat Phys, 2015) gave a polynomial time algorithm to compute a succinct classical description for unique ground states of gapped 1D quantum systems. Despite this progress many questions remained unsolved, including whether there exist efficient algorithms when the ground space is degenerate (and of polynomial dimension in the system size), or for the polynomially many lowest energy states, or even whether such states admit succinct classical descriptions or area laws. In this paper we give a new algorithm, based on a rigorously justified RG type transformation, for finding low energy states for 1D Hamiltonians acting on a chain of n particles. In the process we resolve some of the aforementioned open questions, including giving a polynomial time algorithm for poly(n) degenerate ground spaces and an n O(log n) algorithm for the poly(n) lowest energy states (under a mild density condition). For these classes of systems the existence of a succinct classical description and area laws were not rigorously proved before this work. The algorithms are natural and efficient, and for the case of finding unique ground states for frustration-free Hamiltonians the running time is O~(nM(n)){\tilde{O}(nM(n))}O~(nM(n)) , where M(n) is the time required to multiply two n × n matrices.
In spite of a plethora of no-go results that prevent classically efficient simulation of quantum systems in general, heuristic methods[1] have seen great success, proving typically efficient in practice. The downside of these heuristic methods is that we lack a rigorous understanding of how, and for which systems, they fail[2]. Provably efficient algorithms – even if practically surpassed by heuristic methods – are of key importance for understanding the true worst-case complexity of simulation. The cutting edge for provably efficient simulation is the ground state approximation of 1D spin systems. Under the assumption of a gap, there exists a provably efficient algorithm[3, 4] for approximation of a unique ground state of such systems; we present ongoing work to extend this algorithm to work for degenerate systems. This result comes in the wake of a recent degenerate extension of the area law[5], an important structural bound on the complexity of ground states. In practice this algorithm is no match for heuristic analogues such as the density matrix renormalisation group. However, it does add to the increasing understanding of the systems for which provably efficient simulation is attainable, and might hopefully lead to a future algorithm that is both provably and practically efficient.
This work explores the use of a tree tensor network ansatz to simulate the ground state of a local Hamiltonian on a two-dimensional lattice. By exploiting the entropic area law, the tree tensor network ansatz seems to produce quasiexact results in systems with sizes well beyond the reach of exact diagonalization techniques. We describe an algorithm to approximate the ground state of a local Hamiltonian on a $L\ifmmode\times\else\texttimes\fi{}L$ lattice with the topology of a torus. Accurate results are obtained for L=4,6,8L={4,6,8}L=4,6,8, whereas approximate results are obtained for larger lattices. As an application of the approach, we analyze the scaling of the ground-state entanglement entropy at the quantum critical point of the model. We confirm the presence of a positive additive constant to the area law for half a torus. We also find a logarithmic additive correction to the entropic area law for a square block. The single copy entanglement for half a torus reveals similar corrections to the area law with a further term proportional to 1/L1/L1/L.
We show that the 2D local Hamiltonian problem with the constraint that the ground state obeys area laws is QMA-complete. We also prove similar results in 2D translation- invariant systems and for the 3D Heisenberg and Hubbard models with local magnetic fields. Consequently, unless MA = QMA, not all ground states of 2D local Hamiltonians with area laws have efficient classical representations that support efficient computation of local expectation values. In the future, even if area laws are proved for ground states of 2D gapped systems, the computational complexity of these systems remains unclear.
We show an area law in the mutual information for the maximally-mixed state ΩΩΩ in the ground space of general Hamiltonians, which is independent of the underlying ground space degeneracy. Our result assumes the existence of a `good' approximation to the ground state projector (a good AGSP), a crucial ingredient in previous area-law proofs. Such approximations have been explicitly derived for 1D gapped local Hamiltonians and 2D frustration-free locally-gapped Hamiltonians. As a corollary, we show that in 1D gapped local Hamiltonians, for any ε>0\varepsilon>0ε>0 and any bi-partition L∪LcL\cup L^cL∪Lc of the system, \begin{align*} \mathrm I_{\max}^\varepsilon (L:L^c)_Ω \le \mathrm O \big( \log (|L|\log(d))+\log(1/\varepsilon)\big), \end{align*} where ∣L∣|L|∣L∣ represents the number of sites in LLL, ddd is the dimension of a site and $ \mathrm I_{\max}^\varepsilon (L:L^c)_Ω $ represents the ε\varepsilonε-\emph{smoothed maximum mutual information} with respect to the L:LcL:L^cL:Lc partition in ΩΩΩ. From this bound we then conclude I(L:Lc)Ω≤O(log⁡(∣L∣log⁡(d)))\mathrm I (L:L^c)_Ω \le \mathrm O\big(\log(|L|\log(d))\big)I(L:Lc)Ω​≤O(log(∣L∣log(d))) -- an area law for the mutual information in 1D systems with a logarithmic correction. In addition, we show that ΩΩΩ can be approximated in trace norm up to ε\varepsilonε with a state of Schmidt rank of at most poly(∣L∣/ε)\mathrm{poly}(|L|/\varepsilon)poly(∣L∣/ε), leading to a good MPO approximation for ΩΩΩ with polynomial bond dimension. Similar corollaries are derived for the mutual information of 2D frustration-free and locally-gapped local Hamiltonians.