Computational Difficulty of Global Variations in the Density Matrix Renormalization Group

Abstract

The density matrix renormalization group (DMRG) 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.

5 pages, 1 figure, RevTeX, final version

References in corpus (5)

• Matrix Product Density Operators: Simulation of finite-T and dissipative systems
• Matrix product states represent ground states faithfully
• Lieb-Robinson bounds and the generation of correlations and topological quantum order
• DMRG and periodic boundary conditions: a quantum information perspective
• General entanglement scaling laws from time evolution

Cited by in corpus (29)

• Area laws for the entanglement entropy - a review
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• An Area Law for One Dimensional Quantum Systems
• Training variational quantum algorithms is NP-hard
• Evolution of entanglement entropy following a quantum quench: Analytic results for the XY chain in a transverse magnetic field
• Novel schemes for measurement-based quantum computation
• Measurement-based quantum computation beyond the one-way model
• Finite automata for caching in matrix product algorithms
• Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
• Simulating adiabatic evolution of gapped spin systems
• Statistics dependence of the entanglement entropy
• Complexity of thermal states in quantum spin chains
• Unifying variational methods for simulating quantum many-body systems
• Time evolution of 1D gapless models from a domain-wall initial state: SLE continued?
• The computational difficulty of finding MPS ground states
• Sequentially generated states for the study of two dimensional systems
• Matrix Product State and mean field solutions for one-dimensional systems can be found efficiently
• Obtaining highly excited eigenstates of the localized XX chain via DMRG-X
• Adiabatic preparation without Quantum Phase Transitions
• A variational method based on weighted graph states
• A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians
• An Efficient Algorithm for approximating 1D Ground States
• A QMA-Complete Translationally Invariant Hamiltonian Problem and the Complexity of Finding Ground State Energies in Physical Systems
• Improved numerical methods for infinite spin chains with long-range interactions
• The ground state of a class of noncritical 1D quantum spin systems can be approximated efficiently
• Infinite randomness with continuously varying critical exponents in the random XYZ spin chain
• Sign problem in tensor network contraction
• Physical consequences of P$\ne$NP and the DMRG-annealing conjecture
• PAC-learning of free-fermionic states is NP-hard