The power of matrix product states to describe infinite-size translational-invariant critical spin chains is investigated. At criticality, the accuracy with which they describe ground-state properties of a system is limited by the size $\ensuremath{\chi}$ of the matrices that form the approximation. This limitation is quantified in terms of the scaling of the half-chain entanglement entropy. In the case of the quantum Ising model, we find $S\ensuremath{\sim}\frac{1}{6}\text{log}\text{ }\ensuremath{\chi}$ with high precision. This result can be understood as the emergence of an effective finite correlation length ${\ensuremath{\xi}}_{\ensuremath{\chi}}$ ruling all the scaling properties in the system. We produce six extra pieces of evidence for this finite-$\ensuremath{\chi}$ scaling, namely, the scaling of the correlation length, the scaling of magnetization, the shift of the critical point, the scaling of the entanglement entropy for a finite block of spins, the existence of scaling functions, and the agreement with analogous classical results. All our computations are consistent with a scaling relation of the form ${\ensuremath{\xi}}_{\ensuremath{\chi}}\ensuremath{\sim}{\ensuremath{\chi}}^{\ensuremath{\kappa}}$, with $\ensuremath{\kappa}=2$ for the Ising model. In the case of the Heisenberg model, we find similar results with the value $\ensuremath{\kappa}\ensuremath{\sim}1.37$. We also show how finite-$\ensuremath{\chi}$ scaling allows us to extract critical exponents. These results are obtained using the infinite time evolved block decimation algorithm which works in the thermodynamical limit and are verified to agree with density-matrix renormalization-group results and their classical analog obtained with the corner transfer-matrix renormalization group.
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.
The density-matrix renormalization-group method is very effective at finding ground states of one-dimensional (1D) quantum systems in practice, but it is a heuristic method, and there is no known proof for when it works. In this article we describe an efficient classical algorithm which provably finds a good approximation of the ground state of 1D systems under well-defined conditions. More precisely, our algorithm finds a matrix product state of bond dimension
D whose energy approximates the minimal energy such states can achieve. The running time is exponential in
D, and so the algorithm can be considered tractable even for
D, which is logarithmic in the size of the chain. The result also implies trivially that the ground state of any local commuting Hamiltonian in 1D can be approximated efficiently; we improve this to an exact algorithm.
We present some exact results for the optimal matrix product state (MPS) approximation to the ground state of the infinite isotropic Heisenberg spin-1/2 chain. Our approach is based on the systematic use of Schmidt decompositions to reduce the problem of approximating for the ground state of a spin chain to an analytical minimization. This allows one to show that results of standard simulations, e.g. density matrix renormalization group and infinite time evolving block decimation, do correspond to the result obtained by this minimization strategy and, thus, both methods deliver optimal MPS with the same energy but, otherwise, different properties. We also find that translational and rotational symmetries cannot be maintained simultaneously by the MPS ansatz of minimum energy and present explicit constructions for each case. Furthermore, we analyze symmetry restoration and quantify it to uncover new scaling relations. The method we propose can be extended to any translational invariant Hamiltonian.
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.
We present a matrix product state (MPS) algorithm to approximate ground states of translationally invariant systems with periodic boundary conditions. For a fixed value of the bond dimension
D of the MPS, we discuss how to minimize the computational cost to obtain a seemingly optimal MPS approximation to the ground state. In a chain with
N sites and correlation length $\ensuremath{\xi}$, the computational cost formally scales as $g(D,\ensuremath{\xi}/N){D}^{3}$, where $g(D,\ensuremath{\xi}/N)$ is a nontrivial function. For $\ensuremath{\xi}\ensuremath{\ll}N$, this scaling reduces to
D3, independent of the system size
N, making our method
N times faster than previous proposals. We apply the algorithm to obtain MPS approximations for the ground states of the critical quantum Ising and Heisenberg spin-
1/2 models as well as for the noncritical Heisenberg spin-
1 model. In the critical case, for any chain length
N, we find a model-dependent bond dimension
D(N) above which the polynomial decay of correlations is faithfully reproduced throughout the entire system.