Matrix product state approximations: Bringing theory closer to practice

This is a Perspective on "Locally accurate MPS approximations for ground states of one-dimensional gapped local Hamiltonians" by Alexander M. Dalzell and Fernando G. S. L. Brandão, published in Quantum 3, 187 (2019).

By Yichen Huang (Center for Theoretical Physics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA).

Classical simulation of quantum many-body systems is a fundamental challenge in condensed matter physics. Part of the difficulty stems from the fact that the dimension of the Hilbert space grows exponentially with the system size so that a generic many-body state cannot even be represented in polynomial space. Fortunately, ground states of local Hamiltonians (and many other physically interesting states) are non-generic and occupy only a tiny corner of the Hilbert space. It may be possible to avoid the “curse of dimensionality” for some of these states.

In one-dimensional quantum systems such as spin chains, the density matrix renormalization group (DMRG) [9] is a popular and the most powerful numerical method for computing ground states. It is essentially a variational algorithm that minimizes the energy over matrix product states (MPS). As the name suggests, an MPS is a data structure representing a many-body state by products of matrices. The dimension of the matrices is called the “bond dimension” and determines the space complexity of the MPS.

Due to its prevalence, it is important to understand the empirical success of the DMRG. In a remarkable paper [2], Hastings proved efficient MPS approximations to ground-state wave functions of one-dimensional gapped Hamiltonians: There exists an MPS with polynomial (in the system size) bond dimension such that the overlap with the true ground state is close to unity. Subsequently, it was shown [6,3] that a variant of the DMRG can find such MPS approximations in polynomial time, avoiding local minima should they exist.

In DMRG calculations, we may not have to increase the bond dimension with the system size. An extreme example is the infinite DMRG, which minimizes the energy density over translationally invariant MPS directly in the thermodynamic limit. It is empirically observed that a constant bond dimension is sufficient for computing expectation values of local observables. This observation cannot be explained by the aforementioned theory of MPS approximations [2], where the required bond dimension grows with the system size and diverges in the thermodynamic limit. It remains an open problem (despite the progress [8,4,7]) to justify the common practice of using MPS with constant bond dimension as a variational ansatz in the DMRG.

In a paper published in Quantum [1], Alexander M. Dalzell and Fernando G. S. L. Brandão at the Institute for Quantum Information and Matter, California Institute of Technology solve this decade-old problem and thus bring the theory of MPS approximations closer to practice. (Similar results are obtained in simultaneous and independent work [5].) For various classes of states summarized in Table 1, MPS with bond dimension independent of the system size are constructed such that all local properties are well approximated.

Table 1: Bond dimension of the MPS approximating all local reduced density matrices of $k=O(1)$ consecutive sites to accuracy $\epsilon$. For a state with exponential decay of correlations, there is a bonus: The MPS can be generated from a product state by a $\mathrm{poly} (k/\epsilon)$-depth quantum circuit with nearest-neighbor gates [1].
class of states in one dimension bond dimension
ground states of gapped Hamiltonians $O(k/\epsilon)^{1.001}$
states with exponential decay of correlations $\mathrm{poly}(k/\epsilon)$
arbitrary states $e^{O(k/\epsilon)}$

The next step is to study the algorithmic aspects of the problem. For ground states of one-dimensional gapped Hamiltonians, is it possible to compute local properties provably faster than using the algorithm in [6,3] to compute wave functions? Assuming translational invariance and a well-defined thermodynamic limit, can expectation values of local observables be computed in time independent of the system size? These and other related questions remain unanswered, but the authors present a rigorous study of the relationship between them [1].

In summary, the work of Dalzell and Brandão is an important contribution to the theory of MPS approximations, for it justifies the common practice of using MPS with constant bond dimension as a variational ansatz in the DMRG.

► BibTeX data

► References

[1] A. M. Dalzell and F. G. S. L. Brandão. Locally accurate MPS approximations for ground states of one-dimensional gapped local Hamiltonians. Quantum, 3: 187, 2019. 10.22331/​q-2019-09-23-187.
https:/​/​doi.org/​10.22331/​q-2019-09-23-187

[2] M. B. Hastings. An area law for one-dimensional quantum systems. Journal of Statistical Mechanics: Theory and Experiment, 2007 (08): P08024, 2007. 10.1088/​1742-5468/​2007/​08/​P08024.
https:/​/​doi.org/​10.1088/​1742-5468/​2007/​08/​P08024

[3] Y. Huang. A polynomial-time algorithm for the ground state of one-dimensional gapped Hamiltonians. arXiv:1406.6355, 2014.

[4] Y. Huang. Computing energy density in one dimension. arXiv:1505.00772, 2015.

[5] Y. Huang. Approximating local properties by tensor network states with constant bond dimension. arXiv:1903.10048, 2019.

[6] Z. Landau, U. Vazirani, and T. Vidick. A polynomial time algorithm for the ground state of one-dimensional gapped local Hamiltonians. Nature Physics, 11 (7): 566-569, 2015. 10.1038/​nphys3345.
https:/​/​doi.org/​10.1038/​nphys3345

[7] N. Schuch and F. Verstraete. Matrix product state approximations for infinite systems. arXiv:1711.06559, 2017.

[8] F. Verstraete and J. I. Cirac. Matrix product states represent ground states faithfully. Physical Review B, 73 (9): 094423, 2006. 10.1103/​PhysRevB.73.094423.
https:/​/​doi.org/​10.1103/​PhysRevB.73.094423

[9] S. R. White. Density matrix formulation for quantum renormalization groups. Physical Review Letters, 69 (19): 2863-2866, 1992. 10.1103/​PhysRevLett.69.2863.
https:/​/​doi.org/​10.1103/​PhysRevLett.69.2863

Cited by

On Crossref's cited-by service no data on citing works was found (last attempt 2019-11-13 06:20:08). On SAO/NASA ADS no data on citing works was found (last attempt 2019-11-13 06:20:08).