Matrix Product State and mean field solutions for one-dimensional systems can be found efficiently

Abstract

We consider the problem of approximating ground states of one-dimensional quantum systems within the two most common variational ansatzes, namely the mean field ansatz and Matrix Product States. We show that both for mean field and for Matrix Product States of fixed bond dimension, the optimal solutions can be found in a way which is provably efficient (i.e., scales polynomially). This implies that the corresponding variational methods can be in principle recast in a way which scales provably polynomially. Moreover, our findings imply that ground states of one-dimensional commuting Hamiltonians can be found efficiently.

5 pages; v2: accepted version, Journal-ref added

References in corpus (9)

• An Area Law for One Dimensional Quantum Systems
• Matrix product states represent ground states faithfully
• Area laws in quantum systems: mutual information and correlations
• DMRG and periodic boundary conditions: a quantum information perspective
• Randomizing quantum states: Constructions and applications
• The power of quantum systems on a line
• The computational difficulty of finding MPS ground states
• Computational Difficulty of Global Variations in the Density Matrix Renormalization Group
• An Efficient Algorithm for approximating 1D Ground States

Cited by in corpus (25)

• Efficient quantum state tomography
• Hamiltonian complexity
• Exponential Decay of Correlations Implies Area Law
• Quantum Hamiltonian Complexity
• Algorithms for quantum simulation at finite energies
• Tensor Networks and Quantum Error Correction
• Computations in Quantum Tensor Networks
• Tensor product representation of topological ordered phase: necessary symmetry conditions
• Matrix Product Representation of Locality Preserving Unitaries
• Energy as a detector of nonlocality of many-body spin systems
• Detecting a $Z_2$ topologically ordered phase from unbiased infinite projected entangled-pair state simulations
• A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians
• An Efficient Algorithm for approximating 1D Ground States
• Approximation algorithms for QMA-complete problems
• Computing the Degenerate Ground Space of Gapped Spin Chains in Polynomial Time
• Entanglement marginal problems
• Certificates of quantum many-body properties assisted by machine learning
• Classical simulation of boson sampling with sparse output
• Franck-Condon factors via compressive sensing
• Physical consequences of P$\ne$NP and the DMRG-annealing conjecture
• Approximation, Proof Systems, and Correlations in a Quantum World
• A Simple and General Equation for Matrix Product Unitary Generation
• Compressed sensing enhanced by quantum approximate optimization algorithm
• Effects of Topological Boundary Conditions on Bell Nonlocality
• Tensor network states for the description of quantum many-body systems