The computational difficulty of finding MPS ground states

Abstract

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. By lifting the requirement of a unique ground state, we obtain a class for which finding the ground state solves an NP-complete problem. Therefore, for these Hamiltonians it is not even possible to certify that the ground state has been found. Our results thus imply that in order to prove convergence of variational methods over MPS, as the Density Matrix Renormalization Group, one has to put more requirements than just MPS ground states and a polynomial spectral gap.

5 pages. v2: accepted version, Journal-Ref added

References in corpus (6)

• The density-matrix renormalization group
• An Area Law for One Dimensional Quantum Systems
• DMRG and periodic boundary conditions: a quantum information perspective
• Quantum simulators, continuous-time automata, and translationally invariant systems
• Computational Difficulty of Global Variations in the Density Matrix Renormalization Group
• A QMA-Complete Translationally Invariant Hamiltonian Problem and the Complexity of Finding Ground State Energies in Physical Systems

Cited by in corpus (39)

• Area laws for the entanglement entropy - a review
• Matrix Product States and Projected Entangled Pair States: Concepts, Symmetries, and Theorems
• Renormalization and tensor product states in spin chains and lattices
• Can One Trust Quantum Simulators?
• PEPS as ground states: degeneracy and topology
• Genuine quantum correlations in quantum many-body systems: a review of recent progress
• Quantum Hamiltonian Complexity
• Many-body localisation implies that eigenvectors are matrix-product states
• Criticality without frustration for quantum spin-1 chains
• Out of equilibrium dynamics with Matrix Product States
• Phase transitions and localizable entanglement in cluster-state spin chains with Ising couplings and local fields
• Preparing thermal states of quantum systems by dimension reduction
• Computational Complexity in Electronic Structure
• Computations in Quantum Tensor Networks
• Computational Difficulty of Computing the Density of States
• Matrix Product State and mean field solutions for one-dimensional systems can be found efficiently
• Concatenated tensor network states
• Critical exponents of one-dimensional quantum critical models by means of MERA tensor network
• A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians
• The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings
• An Efficient Algorithm for approximating 1D Ground States
• Quantum Adiabatic Computation With a Constant Gap is Not Useful in One Dimension
• Condensed Matter Applications of Entanglement Theory
• Improved numerical methods for infinite spin chains with long-range interactions
• Coarse grained belief propagation for simulation of interacting quantum systems at all temperatures
• Importance of the spectral gap in estimating ground-state energies
• Spin lattices with two-body Hamiltonians for which the ground state encodes a cluster state
• Local Hamiltonians in Quantum Computation
• Bounding the joint numerical range of Pauli strings by graph parameters
• Hamiltonian simulation for low-energy states with optimal time dependence
• Tensor network methods with graph enhancement
• Sign problem in tensor network contraction
• Hamiltonian learning from time dynamics using variational algorithms
• Exact renormalization in quantum spin chains
• Exact symmetry breaking ground states for quantum spin chains
• Physical consequences of P$\ne$NP and the DMRG-annealing conjecture
• Testing quantum circuits and detecting insecure encryption
• PAC-learning of free-fermionic states is NP-hard
• A Generalised Haldane Map from the Matrix Product State Path Integral to the Critical Theory of the $J_1$-$J_2$ Chain