Given a gapped Hamiltonian of a spin chain, we give a polynomial-time algorithm for finding the degenerate ground space projector.The output is an orthonormal set of matrix product states that approximate the true ground space projector up to an inverse polynomial error in any Schatten norm, with a runtime exponential in the degeneracy.Our algorithm is an extension of the recent algorithm of Landau, Vazirani, and Vidick [17] for the nondegenerate case, and it includes the recent improvements due to Huang [13].The main new idea is to incorporate the local distinguishability of ground states on the half-chain to ensure that the algorithm returns a complete set of global ground states.
Computing ground states of local Hamiltonians is a fundamental problem in condensed matter physics. The problem is known to be QMA-complete, even for one-dimensional Hamiltonians [1]. This means that we do not even expect that there is a sub-exponential size description of the ground state that allows efficient computation of local observables such as the energy. In sharp contrast, the heuristic density matrix renormalization group (DMRG) algorithm invented two decades ago [5] has been remarkably successful in practice on one-dimensional problems. The situation is reminiscent of the unexplained success of the simplex algorithm before the advent of ellipsoid and interior-point methods. Is there a principled explanation for this, in the form of a large class of one-dimensional Hamiltonians whose ground states can be provably efficiently approximated? Here we give such an algorithm for gapped one-dimensional Hamiltonians: our algorithm outputs an (inverse-polynomial) approximation to the ground state, expressed as a matrix product state (MPS) of polynomial bond dimension. The running time of the algorithm is polynomial in the number of qudits n and the approximation quality δ, for a fixed local dimension d and gap Δ > 0.
We give an improved analysis of approximate ground space projectors (AGSPs) to obtain a sharp error reduction bound in the setting a degenerate ground space. The improved tools imply that the recently proven 2D area law directly extends to sub-exponentially degenerate ground spaces and also yields a sub-exponential-time classical algorithm to compute the ground states. This time complexity cannot be improved beyond sub-exponential, even for the special case of classical unfrustrated systems in 2D.
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)) , 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.
We begin by deriving bounds for the entanglement of a spin with an (adjacent and non-adjacent) interval of spins in an arbitrary pure Finitely Correlated States (FCS). The bounds we derive become exact in the case where one considers the entanglement of a single spin with a half-infinite chain to the right of it. Our result permits a more efficient calculation, numerically and in some cases even analytically, of the entanglement in arbitrary finitely correlated quantum spin chains. We continue the study of entanglement in the setting of ground states of Hamiltonians with a spectral gap. In particular, for
V a finite subset of
Zd, we let
HV denote a Hamiltonian on
V with finite range, finite strength interactions and a unique ground state with a non-vanishing spectral gap. For a density matrix
ρA that describes the finite-volume restriction to a region
A of the unique ground state, we provide a detailed version of a proof by M. Hastings, that the entropy of
ρA is bounded by a uniform constant
C. Moreover, we provide a detailed generalization of the 1-dimensional construction of Hastings' approximation to the ground state in dimensions 2 and higher. Finally, we turn our attention to the study of a conjecture central to Quantum Information Theory, the multiplicativity of the maximal output Schatten
p-norm of quantum channels, for
p>1. In particular, we study the output 2-norm for a special class of quantum channels, the depolarized Werner-Holevo channels, and show that multiplicativity holds for a product of two identical channels in this class.
The success of polynomial-time tensor network methods for computing ground states of certain quantum local Hamiltonians has recently been given a sound theoretical basis by Arad et al. [Math. Phys. 356, 65 (2017)]. The convergence proof, however, relies on ``rigorous renormalization group'' (RRG) techniques which differ fundamentally from existing algorithms. We introduce a practical adaptation of the RRG procedure which, while no longer theoretically guaranteed to converge, finds matrix product state ansatz approximations to the ground spaces and low-lying excited spectra of local Hamiltonians in realistic situations. In contrast to other schemes, RRG does not utilize variational methods on tensor networks. Rather, it operates on subsets of the system Hilbert space by constructing approximations to the global ground space in a treelike manner. We evaluate the algorithm numerically, finding similar performance to density matrix renormalization group (DMRG) in the case of a gapped nondegenerate Hamiltonian. Even in challenging situations of criticality, large ground-state degeneracy, or long-range entanglement, RRG remains able to identify candidate states having large overlap with ground and low-energy eigenstates, outperforming DMRG in some cases.