The density matrix renormalization group approach is arguably the most successful method to numerically find ground states of quantum spin chains. It amounts to iteratively locally optimizing matrix-product states, aiming at better and better approximating the true ground state. To date, both a proof of convergence to the globally best approximation and an assessment of its complexity are lacking. Here we establish a result on the computational complexity of an approximation with matrix-product states: The surprising result is that when one globally optimizes over several sites of local Hamiltonians, avoiding local optima, one encounters in the worst case a computationally difficult NP-hard problem (hard even in approximation). The proof exploits a novel way of relating it to binary quadratic programming. We discuss intriguing ramifications on the difficulty of describing quantum many-body systems.
The density matrix renormalization group approach is arguably the most successful method to numerically find ground states of quantum spin chains. It amounts to iteratively locally optimizing matrix-product states, aiming at better and better approximating the true ground state. To date, both a proof of convergence to the globally best approximation and an assessment of its complexity are lacking. Here we establish a result on the computational complexity of an approximation with matrix-product states: The surprising result is that when one globally optimizes over several sites of local Hamiltonians, avoiding local optima, one encounters in the worst case a computationally difficult NP-hard problem (hard even in approximation). The proof exploits a novel way of relating it to binary quadratic programming. We discuss intriguing ramifications on the difficulty of describing quantum many-body systems.
The density matrix renormalization group (DMRG) approach is arguably the most successful method to numerically approximate ground states of quantum spin chains. It essentially amounts to iteratively locally optimizing matrix-product states, aiming at better and better approximating the true ground state. Despite considerable effort, to date both a proof of convergence of this procedure to the globally best approximation and an assessment of its complexity are lacking. Here, we rigorously establish a statement on the classical complexity of an approximation with matrix-product states: the surprising result is that when one globally optimizes matrix-product states with respect to several sites simultaneously - to find the optimal approximation over several sites at once, avoiding local optima - one encounters in the worst case a computationally difficult NP-hard problem. We prove this by exploiting a novel way of polynomially relating it to binary quadratic programming. This is true even for translationally invariant local hamiltonians. This result gives rise to intriguing ramifications on the difficulty of describing quantum many-body systems, which we discuss.
Density matrix renormalization group (DMRG) algorithm has been extremely successful for computing the ground states of one-dimensional quantum many-body systems. For problems concerned with mixed quantum states, however, it is less successful in that either such an algorithm does not exist yet or that it may return unphysical solutions. Here we propose a positive matrix product ansatz for mixed quantum states which preserves positivity by construction. More importantly, it allows one to build a DMRG algorithm which, the same as the standard DMRG for ground states, iteratively reduces the global optimization problem to local ones of the same type, with the energy converging monotonically in principle. This algorithm is applied for computing both the equilibrium states and the nonequilibrium steady states and its advantages are numerically demonstrated.
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.
We determine the computational difficulty of finding ground states of one-dimensional (1D) Hamiltonians, which are known to be matrix product states (MPS). To this end, we construct a class of 1D frustration-free Hamiltonians with unique MPS ground states and a polynomial gap above, for which finding the ground state is at least as hard as factoring. Without the uniqueness of the ground state, the problem becomes NP complete, and thus for these Hamiltonians it cannot even be certified that the ground state has been found. This poses new bounds on convergence proofs for variational methods that use MPS.
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.
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).