Locally accurate MPS approximations for ground states of one-dimensional gapped local Hamiltonians
1Institute for Quantum Information and Matter, California Institute of Technology, Pasadena, CA 91125, USA
2Google LLC, Venice, CA 90291, USA
| Published: | 2019-09-23, volume 3, page 187 |
| Eprint: | arXiv:1903.10241v3 |
| Doi: | https://doi.org/10.22331/q-2019-09-23-187 |
| Citation: | Quantum 3, 187 (2019). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
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.
► BibTeX data
► 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] Yichen Huang, "Entanglement Dynamics From Random Product States: Deviation From Maximal Entanglement", IEEE Transactions on Information Theory 68 5, 3200 (2022).
[2] Yichen Huang, "Two-dimensional local Hamiltonian problem with area laws is QMA-complete", Journal of Computational Physics 443, 110534 (2021).
[3] Sergey Filippov, "Multipartite Correlations in Quantum Collision Models", Entropy 24 4, 508 (2022).
[4] Yichen Huang, "Matrix product state approximations: Bringing theory closer to practice", Quantum Views 3, 26 (2019).
[5] Álvaro M. Alhambra and J. Ignacio Cirac, "Locally Accurate Tensor Networks for Thermal States and Time Evolution", PRX Quantum 2 4, 040331 (2021).
[6] Kaiyan Yang, Xiao Zeng, Yujing Luo, Guowu Yang, Lan Shu, Miguel Navascués, and Zizhu Wang, "Contextuality in infinite one-dimensional translation-invariant local Hamiltonians", npj Quantum Information 8 1, 89 (2022).
[7] A. Nietner, B. Vanhecke, F. Verstraete, J. Eisert, and L. Vanderstraeten, "Efficient variational contraction of two-dimensional tensor networks with a non-trivial unit cell", Quantum 4, 328 (2020).
[8] Sergey N. Filippov and Ilia A. Luchnikov, "Collisional open quantum dynamics with a generally correlated environment: Exact solvability in tensor networks", Physical Review A 105 6, 062410 (2022).
[9] Or Sharir, Amnon Shashua, and Giuseppe Carleo, "Neural tensor contractions and the expressive power of deep neural quantum states", Physical Review B 106 20, 205136 (2022).
[10] Zhi-Yuan Wei, J. Ignacio Cirac, and Daniel Malz, "Generation of photonic tensor network states with circuit QED", Physical Review A 105 2, 022611 (2022).
[11] L. P. Mayer, "Non-local order parameters for fermion chains via the partial transpose", Journal of Mathematical Physics 64 1, 011903 (2023).
[12] 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).
[13] 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).
[14] Abhinav Deshpande, Alexey V. Gorshkov, and Bill Fefferman, "Importance of the Spectral gap in Estimating Ground-State Energies", PRX Quantum 3 4, 040327 (2022).
[15] Yichen Huang, 2021 IEEE International Symposium on Information Theory (ISIT) 1332 (2021) ISBN:978-1-5386-8209-8.
[16] Yichen Huang, "Locally accurate matrix product approximation to thermal states", Science Bulletin 66 24, 2456 (2021).
[17] 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).
[18] Yichen Huang, 2020 IEEE International Symposium on Information Theory (ISIT) 1927 (2020) ISBN:978-1-7281-6432-8.
[19] J. Ignacio Cirac, David Pérez-García, Norbert Schuch, and Frank Verstraete, "Matrix product states and projected entangled pair states: Concepts, symmetries, theorems", Reviews of Modern Physics 93 4, 045003 (2021).
[20] 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, (2020).
[21] Zongping Gong, Naoto Kura, Masatoshi Sato, and Masahito Ueda, "Lieb-Robinson Bounds on Entanglement Gaps from Symmetry-Protected Topology", arXiv:1904.12464, (2019).
The above citations are from Crossref's cited-by service (last updated successfully 2023-06-05 11:43:19) and SAO/NASA ADS (last updated successfully 2023-06-05 11:43:20). The list may be incomplete as not all publishers provide suitable and complete citation data.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.
Pingback: Perspective in Quantum Views by Yichen Huang "Large Matrix product state approximations: Bringing theory closer to practice"