Locally accurate MPS approximations for ground states of one-dimensional gapped local Hamiltonians

Alexander M. Dalzell1 and Fernando G. S. L. Brandão1,2

1Institute for Quantum Information and Matter, California Institute of Technology, Pasadena, CA 91125, USA
2Google LLC, Venice, CA 90291, USA

Abstract

A key feature of ground states of gapped local 1D Hamiltonians is their relatively low entanglement --- they are well approximated by matrix product states (MPS) with bond dimension scaling polynomially in the length $N$ of the chain, while general states require a bond dimension scaling exponentially. We show that the bond dimension of these MPS approximations can be improved to a constant, independent of the chain length, if we relax our notion of approximation to be more local: for all length-$k$ segments of the chain, the reduced density matrices of our approximations are $\epsilon$-close to those of the exact state. If the state is a ground state of a gapped local Hamiltonian, the bond dimension of the approximation scales like $(k/\epsilon)^{1+o(1)}$, and at the expense of worse but still poly$(k,1/\epsilon)$ scaling of the bond dimension, we give an alternate construction with the additional features that it can be generated by a constant-depth quantum circuit with nearest-neighbor gates, and that it applies generally for any state with exponentially decaying correlations. For a completely general state, we give an approximation with bond dimension $\exp(O(k/\epsilon))$, which is exponentially worse, but still independent of $N$. Then, we consider the prospect of designing an algorithm to find a local approximation for ground states of gapped local 1D Hamiltonians. When the Hamiltonian is translationally invariant, we show that the ability to find $O(1)$-accurate local approximations to the ground state in $T(N)$ time implies the ability to estimate the ground state energy to $O(1)$ precision in $O(T(N)\log(N))$ time.

► References

[1] I. Arad, A. Kitaev, Z. Landau, and U. Vazirani. An area law and sub-exponential algorithm for 1D systems. arXiv preprint arXiv:1301.1162, 2013.
arXiv:1301.1162

[2] I. Arad, Z. Landau, U. Vazirani, and T. Vidick. Rigorous RG algorithms and area laws for low energy eigenstates in 1D. Communications in Mathematical Physics, 356 (1): 65–105, Nov 2017. ISSN 1432-0916. 10.1007/​s00220-017-2973-z.
https:/​/​doi.org/​10.1007/​s00220-017-2973-z

[3] J. Bausch, T. Cubitt, A. Lucia, and D. Perez-Garcia. Undecidability of the spectral gap in one dimension. arXiv preprint arXiv:1810.01858, 2018a.
arXiv:1810.01858

[4] J. Bausch, T. S. Cubitt, A. Lucia, D. Perez-Garcia, and M. M. Wolf. Size-driven quantum phase transitions. Proceedings of the National Academy of Sciences, 115 (1): 19–23, 2018b. ISSN 0027-8424. 10.1073/​pnas.1705042114.
https:/​/​doi.org/​10.1073/​pnas.1705042114

[5] F. G. S. L. Brandão and M. Horodecki. Exponential decay of correlations implies area law. Communications in Mathematical Physics, 333 (2): 761–798, Jan 2015. ISSN 1432-0916. 10.1007/​s00220-014-2213-8.
https:/​/​doi.org/​10.1007/​s00220-014-2213-8

[6] G. K. Brennen, S. S. Bullock, and D. P. O'Leary. Efficient circuits for exact-universal computation with qudits. Quantum Information and Computation, 6 (4-5), 2006. URL http:/​/​www.rintonpress.com/​journals/​qiconline.html#v6n45.
http:/​/​www.rintonpress.com/​journals/​qiconline.html#v6n45

[7] T. S. Cubitt, D. Perez-Garcia, and M. M. Wolf. Undecidability of the spectral gap. Nature, 528 (7581): 207, 2015. 10.1038/​nature16059.
https:/​/​doi.org/​10.1038/​nature16059

[8] M. Fannes, B. Nachtergaele, and R. F. Werner. Abundance of translation invariant pure states on quantum spin chains. Letters in Mathematical Physics, 25 (3): 249–258, Jul 1992a. ISSN 1573-0530. 10.1007/​BF00406552.
https:/​/​doi.org/​10.1007/​BF00406552

[9] M. Fannes, B. Nachtergaele, and R. F. Werner. Finitely correlated states on quantum spin chains. Communications in Mathematical Physics, 144 (3): 443–490, Mar 1992b. ISSN 1432-0916. 10.1007/​BF02099178.
https:/​/​doi.org/​10.1007/​BF02099178

[10] A. Gilchrist, N. K. Langford, and M. A. Nielsen. Distance measures to compare real and ideal quantum processes. Phys. Rev. A, 71: 062310, Jun 2005. 10.1103/​PhysRevA.71.062310.
https:/​/​doi.org/​10.1103/​PhysRevA.71.062310

[11] J. Haegeman, J. I. Cirac, T. J. Osborne, I. Pižorn, H. Verschelde, and F. Verstraete. Time-dependent variational principle for quantum lattices. Phys. Rev. Lett., 107: 070601, Aug 2011. 10.1103/​PhysRevLett.107.070601.
https:/​/​doi.org/​10.1103/​PhysRevLett.107.070601

[12] M. B. Hastings. Lieb-Schultz-Mattis in higher dimensions. Phys. Rev. B, 69: 104431, Mar 2004a. 10.1103/​PhysRevB.69.104431.
https:/​/​doi.org/​10.1103/​PhysRevB.69.104431

[13] M. B. Hastings. Locality in quantum and markov dynamics on lattices and networks. Phys. Rev. Lett., 93: 140402, Sep 2004b. 10.1103/​PhysRevLett.93.140402.
https:/​/​doi.org/​10.1103/​PhysRevLett.93.140402

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

[15] M. B. Hastings and T. Koma. Spectral gap and exponential decay of correlations. Communications in Mathematical Physics, 265 (3): 781–804, Aug 2006. ISSN 1432-0916. 10.1007/​s00220-006-0030-4.
https:/​/​doi.org/​10.1007/​s00220-006-0030-4

[16] Y. Huang. Area law in one dimension: Degenerate ground states and Renyi entanglement entropy. arXiv preprint arXiv:1403.0327, 2014.
arXiv:1403.0327

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

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

[19] M. Kliesch, D. Gross, and J. Eisert. Matrix-product operators and states: NP-hardness and undecidability. Phys. Rev. Lett., 113: 160503, Oct 2014. 10.1103/​PhysRevLett.113.160503.
https:/​/​doi.org/​10.1103/​PhysRevLett.113.160503

[20] A. Klümper, A. Schadschneider, and J. Zittartz. Matrix product ground states for one-dimensional spin-1 quantum antiferromagnets. Europhysics Letters (EPL), 24 (4): 293–297, nov 1993. 10.1209/​0295-5075/​24/​4/​010.
https:/​/​doi.org/​10.1209/​0295-5075/​24/​4/​010

[21] 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, 2015. 10.1038/​NPHYS3345.
https:/​/​doi.org/​10.1038/​NPHYS3345

[22] I. P. McCulloch. Infinite size density matrix renormalization group, revisited. arXiv preprint arXiv:0804.2509, 2008.
arXiv:0804.2509

[23] B. Nachtergaele and R. Sims. Lieb-Robinson bounds and the exponential clustering theorem. Communications in Mathematical Physics, 265 (1): 119–130, Jul 2006. ISSN 1432-0916. 10.1007/​s00220-006-1556-1.
https:/​/​doi.org/​10.1007/​s00220-006-1556-1

[24] S. Östlund and S. Rommer. Thermodynamic limit of density matrix renormalization. Phys. Rev. Lett., 75: 3537–3540, Nov 1995. 10.1103/​PhysRevLett.75.3537.
https:/​/​doi.org/​10.1103/​PhysRevLett.75.3537

[25] D. Perez-García, F. Verstraete, M. M. Wolf, and J. I. Cirac. Matrix product state representations. Quantum Information and Computation, 7 (5-6): 401–430, 2007. URL http:/​/​www.rintonpress.com/​journals/​qiconline.html#v7n56.
http:/​/​www.rintonpress.com/​journals/​qiconline.html#v7n56

[26] B. Roberts, T. Vidick, and O. I. Motrunich. Implementation of rigorous renormalization group method for ground space and low-energy states of local Hamiltonians. Phys. Rev. B, 96: 214203, Dec 2017. 10.1103/​PhysRevB.96.214203.
https:/​/​doi.org/​10.1103/​PhysRevB.96.214203

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

[28] N. Schuch, M. M. Wolf, F. Verstraete, and J. I. Cirac. Entropy scaling and simulability by matrix product states. Phys. Rev. Lett., 100: 030504, Jan 2008. 10.1103/​PhysRevLett.100.030504.
https:/​/​doi.org/​10.1103/​PhysRevLett.100.030504

[29] M. Tomamichel, R. Colbeck, and R. Renner. A fully quantum asymptotic equipartition property. IEEE Transactions on Information Theory, 55 (12): 5840–5847, Dec 2009. 10.1109/​TIT.2009.2032797.
https:/​/​doi.org/​10.1109/​TIT.2009.2032797

[30] A. Uhlmann. The “transition probability” in the state space of a $\star$-algebra. Reports on Mathematical Physics, 9 (2): 273 – 279, 1976. ISSN 0034-4877. 10.1016/​0034-4877(76)90060-4.
https:/​/​doi.org/​10.1016/​0034-4877(76)90060-4

[31] L. Vanderstraeten, J. Haegeman, and F. Verstraete. Tangent-space methods for uniform matrix product states. SciPost Phys. Lect. Notes, page 7, 2019. 10.21468/​SciPostPhysLectNotes.7.
https:/​/​doi.org/​10.21468/​SciPostPhysLectNotes.7

[32] F. Verstraete and J. I. Cirac. Matrix product states represent ground states faithfully. Phys. Rev. B, 73: 094423, Mar 2006. 10.1103/​PhysRevB.73.094423.
https:/​/​doi.org/​10.1103/​PhysRevB.73.094423

[33] G. Vidal. Efficient classical simulation of slightly entangled quantum computations. Phys. Rev. Lett., 91: 147902, Oct 2003. 10.1103/​PhysRevLett.91.147902.
https:/​/​doi.org/​10.1103/​PhysRevLett.91.147902

[34] G. Vidal. Classical simulation of infinite-size quantum lattice systems in one spatial dimension. Phys. Rev. Lett., 98: 070201, Feb 2007. 10.1103/​PhysRevLett.98.070201.
https:/​/​doi.org/​10.1103/​PhysRevLett.98.070201

[35] A. Weichselbaum, F. Verstraete, U. Schollwöck, J. I. Cirac, and J. von Delft. Variational matrix-product-state approach to quantum impurity models. Phys. Rev. B, 80: 165117, Oct 2009. 10.1103/​PhysRevB.80.165117.
https:/​/​doi.org/​10.1103/​PhysRevB.80.165117

[36] S. R. White. Density matrix formulation for quantum renormalization groups. Phys. Rev. Lett., 69: 2863–2866, Nov 1992. 10.1103/​PhysRevLett.69.2863.
https:/​/​doi.org/​10.1103/​PhysRevLett.69.2863

[37] S. R. White. Density-matrix algorithms for quantum renormalization groups. Phys. Rev. B, 48: 10345–10356, Oct 1993. 10.1103/​PhysRevB.48.10345.
https:/​/​doi.org/​10.1103/​PhysRevB.48.10345

[38] V. Zauner-Stauber, L. Vanderstraeten, M. T. Fishman, F. Verstraete, and J. Haegeman. Variational optimization algorithms for uniform matrix product states. Phys. Rev. B, 97: 045145, Jan 2018. 10.1103/​PhysRevB.97.045145.
https:/​/​doi.org/​10.1103/​PhysRevB.97.045145

Cited by

[1] Yijian Zou, Karthik Siva, Tomohiro Soejima, Roger S. K. Mong, and Michael P. Zaletel, "Universal Tripartite Entanglement in One-Dimensional Many-Body Systems", Physical Review Letters 126 12, 120501 (2021).

[2] Yichen Huang, "Two-dimensional local Hamiltonian problem with area laws is QMA-complete", Journal of Computational Physics 443, 110534 (2021).

[3] Karel Van Acoleyen, Andrew Hallam, Matthias Bal, Markus Hauru, Jutho Haegeman, and Frank Verstraete, "Entanglement compression in scale space: From the multiscale entanglement renormalization ansatz to matrix product operators", Physical Review B 102 16, 165131 (2020).

[4] Yichen Huang, "Matrix product state approximations: Bringing theory closer to practice", Quantum Views 3, 26 (2019).

[6] Yichen (溢辰) Huang (黄), "Locally accurate matrix product approximation to thermal states", Science Bulletin (2021).

[7] Zhi-Yuan Wei, Daniel Malz, Alejandro González-Tudela, and J. Ignacio Cirac, "Generation of photonic matrix product states with Rydberg atomic arrays", Physical Review Research 3 2, 023021 (2021).

[9] Ignacio Cirac, David Perez-Garcia, Norbert Schuch, and Frank Verstraete, "Matrix Product States and Projected Entangled Pair States: Concepts, Symmetries, and Theorems", arXiv:2011.12127.

[10] Anurag Anshu, Itai Arad, and David Gosset, "Entanglement subvolume law for 2D frustration-free spin systems", arXiv:1905.11337.

[11] Zongping Gong, Naoto Kura, Masatoshi Sato, and Masahito Ueda, "Lieb-Robinson Bounds on Entanglement Gaps from Symmetry-Protected Topology", arXiv:1904.12464.

The above citations are from Crossref's cited-by service (last updated successfully 2021-10-22 10:55:00) and SAO/NASA ADS (last updated successfully 2021-10-22 10:55:02). The list may be incomplete as not all publishers provide suitable and complete citation data.