Computational Difficulty of Finding Matrix Product Ground States
Open accessAbstract
We determine the computational difficulty of finding ground states of one-dimensional (1D) Hamiltonians, which are known to be matrix product states (MPS). To this end, we construct a class of 1D frustration-free Hamiltonians with unique MPS ground states and a polynomial gap above, for which finding the ground state is at least as hard as factoring. Without the uniqueness of the ground state, the problem becomes NP complete, and thus for these Hamiltonians it cannot even be certified that the ground state has been found. This poses new bounds on convergence proofs for variational methods that use MPS.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Decoherence and analog timing errors can make a hybrid universal Hamiltonian simulator via the Trotter construction inefficient.
“They found that decoherence and analog timing errors can make this inefficient for a Hamiltonian simulator.”
From Can one trust quantum simulators? (2012) · cites this paper as [138]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Density matrix formulation for quantum renormalization groups
White, S. R. (1992) · Physical Review Letters · doi:10.1103/physrevlett.69.2863 · Cited by 7,702 · see citing works
The density-matrix renormalization group
Schollwöck, U. (2005) · Reviews of Modern Physics · doi:10.1103/revmodphys.77.259 · Cited by 3,323 · see citing works
Brucker, P. (1995) · Springer eBooks · doi:10.1007/978-3-662-03088-2_3 · Cited by 2,296 · see citing works
Classical and Quantum Computation
Kitaev, A., Shen, A., & Vyalyi, M. (2002) · Graduate Studies in Mathematics · doi:10.1090/gsm/047 · Cited by 1,387 · see citing works
An area law for one-dimensional quantum systems
Hastings, M. B. (2007) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2007/08/p08024 · Cited by 1,131 · see citing works
Verstraete, F., Porras, D., & Cirac, J. I. (2004) · Physical Review Letters · doi:10.1103/physrevlett.93.227205 · Cited by 564 · see citing works
Self-citationQuantum NP - A SurveyPreprint
Aharonov, D., & Naveh, T. (2002) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0210077 · Cited by 116 · see citing works
Quantum Simulators, Continuous-Time Automata, and Translationally Invariant Systems
Vollbrecht, K. G. H., & Cirac, J. I. (2008) · Physical Review Letters · doi:10.1103/physrevlett.100.010501 · Cited by 53 · see citing works
Computational Difficulty of Global Variations in the Density Matrix Renormalization Group
Eisert, J. (2006) · Physical Review Letters · doi:10.1103/physrevlett.97.260501 · Cited by 35 · see citing works
Kay, A. (2007) · Physical Review A · doi:10.1103/physreva.76.030307 · Cited by 22 · see citing works
The Complexity of Stoquastic Local Hamiltonian Problems
Bravyi, S., DiVincenzo, D. P., Oliveira, R. I., & Terhal, B. M. (2006) · arXiv · doi:10.48550/arxiv.quant-ph/0606140 · Cited by 15 · see citing works
Flagged first, then by citations
Research works printed but not linked: 6
- S. R. White, Phys. Rev. Lett. 69, 2863 (1992).
- U. Schollwo ¨ck, Rev. Mod. Phys. 77, 259 (2005).
- F. Verstraete, D. Porras, and J. I. Cirac, Phys. Rev. Lett. 93, 227205 (2004).
- J. Eisert, Phys. Rev. Lett. 97, 260501 (2006).
- D. Aharonov, D. Gottesman, S. Irani, and J. Kempe, arXiv:0705.4077. · arXiv
- K. Vollbrecht and I. Cirac, Phys. Rev. Lett. 100, 010501 (2008).
Cited by
Sorted by citations
<i>Colloquium</i> : Area laws for the entanglement entropy
Eisert, J., Cramer, M., & Plenio, M. B. (2010) · Reviews of Modern Physics · doi:10.1103/revmodphys.82.277 · Cited by 2,873 · see citing works
Matrix product states and projected entangled pair states: Concepts, symmetries, theorems
Cirac, J. I., Pérez-Garcı́a, D., Schuch, N., & Verstraete, F. (2021) · Reviews of Modern Physics · doi:10.1103/revmodphys.93.045003 · Cited by 838 · see citing works
Self-citationAdiabatic Quantum Computation Is Equivalent to Standard Quantum Computation
Aharonov, D., van Dam, W., Kempe, J., Landau, Z., Lloyd, S., & Regev, O. (2008) · SIAM Review · doi:10.1137/080734479 · Cited by 395 · see citing works
Renormalization and tensor product states in spin chains and lattices
Cirac, J. I., & Verstraete, F. (2009) · Journal of Physics A Mathematical and Theoretical · doi:10.1088/1751-8113/42/50/504004 · Cited by 417 · see citing works
Self-citationCan one trust quantum simulators?
Hauke, P., Cucchietti, F. M., Tagliacozzo, L., Deutsch, I., & Lewenstein, M. (2012) · Reports on Progress in Physics · doi:10.1088/0034-4885/75/8/082401 · Cited by 315 · see citing works
PEPS as ground states: Degeneracy and topology
Schuch, N., Cirac, I., & Pérez-García, D. (2010) · Annals of Physics · doi:10.1016/j.aop.2010.05.008 · Cited by 313 · see citing works
Self-citationRenormalization and tensor product states in spin chains and lattices
Cirac, J. I., & Verstraete, F. (2009) · MPG.PuRe (Max Planck Society) · Cited by 217 · see citing works
Self-citationGenuine quantum correlations in quantum many-body systems: a review of recent progress
Chiara, G. D., & Sanpera, A. (2018) · Reports on Progress in Physics · doi:10.1088/1361-6633/aabf61 · Cited by 174 · see citing works
PEPS as ground states: Degeneracy and topology
Schuch, N., Pérez García, D., & Cirac, J. I. (2010) · LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas) · Cited by 150 · see citing works
Self-citationQuantum Hamiltonian Complexity
Gharibian, S., Huang, Y., Landau, Z., & Shin, S. W. (2015) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000066 · Cited by 144 · see citing works
A polynomial time algorithm for the ground state of one-dimensional gapped local Hamiltonians
Landau, Z. A., Vazirani, U. V., & Vidick, T. (2015) · Nature Physics · doi:10.1038/nphys3345 · Cited by 142 · see citing works
Many-Body Localization Implies that Eigenvectors are Matrix-Product States
Friesdorf, M., Werner, A. H., Brown, W., Scholz, V. B., & Eisert, J. (2015) · Physical Review Letters · doi:10.1103/physrevlett.114.170505 · Cited by 114 · see citing works
Criticality without Frustration for Quantum Spin-1 Chains
Bravyi, S. B., Caha, L., Movassagh, R., Nagaj, D., & Shor, P. W. (2012) · Physical Review Letters · doi:10.1103/physrevlett.109.207202 · Cited by 113 · see citing works
Out-of-equilibrium dynamics with matrix product states
Wall, M. L., & Carr, L. D. (2012) · New Journal of Physics · doi:10.1088/1367-2630/14/12/125015 · Cited by 114 · see citing works
Skrøvseth, S. O., & Bartlett, S. D. (2009) · Physical Review A · doi:10.1103/physreva.80.022316 · Cited by 74 · see citing works
Computational complexity in electronic structure
Whitfield, J. D., Love, P. J., & Aspuru-Guzik, A. (2013) · Phys. Chem. Chem. Phys. · doi:10.1039/c2cp42695a · Cited by 71 · see citing works
Preparing Thermal States of Quantum Systems by Dimension Reduction
Bilgin, E., & Boixo, S. (2010) · Physical Review Letters · doi:10.1103/physrevlett.105.170405 · Cited by 65 · see citing works
Matrix Product States and Projected Entangled Pair States: Concepts, Symmetries, and TheoremsPreprint
Cirac, I., Pérez-Garcı́a, D., Schuch, N., & Verstraete, F. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2011.12127 · Cited by 59 · see citing works
Self-citationComputations in quantum tensor networks
Huckle, T., Waldherr, K., & Schulte‐Herbrüggen, T. (2012) · Linear Algebra and its Applications · doi:10.1016/j.laa.2011.12.019 · Cited by 56 · see citing works
Quantum Hamiltonian Complexity
Gharibian, S., Huang, Y., Landau, Z. A., & Shin, S. W. (2015) · now publishers, Inc. eBooks · doi:10.1561/9781680830071 · Cited by 70 · see citing works
The Density Matrix Renormalization Group
Feiguin, A. E. (2013) · Springer series in solid-state sciences · doi:10.1007/978-3-642-35106-8_2 · Cited by 43 · see citing works
Concatenated tensor network states
Hübener, R., Nebendahl, V., & Dür, W. (2010) · New Journal of Physics · doi:10.1088/1367-2630/12/2/025004 · Cited by 39 · see citing works
Matrix product state and mean-field solutions for one-dimensional systems can be found efficiently
Schuch, N., & Cirac, J. I. (2010) · Physical Review A · doi:10.1103/physreva.82.012314 · Cited by 35 · see citing works
Self-citationComputational Difficulty of Computing the Density of States
Brown, B., Flammia, S. T., & Schuch, N. (2011) · Physical Review Letters · doi:10.1103/physrevlett.107.040501 · Cited by 31 · see citing works
Self-citationCritical exponents with a multiscale entanglement renormalization Ansatz channel
Montangero, S., Rizzi, M., Giovannetti, V., & Rosario Fazio, B. (2009) · Physical Review B · doi:10.1103/physrevb.80.113103 · Cited by 28 · see citing works
A polynomial-time algorithm for the ground state of 1D gapped local HamiltoniansPreprint
Landau, Z. A., Vazirani, U. V., & Vidick, T. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1307.5143 · Cited by 25 · see citing works
Quantum Adiabatic Computation with a Constant Gap Is Not Useful in One Dimension
Hastings, M. B. (2009) · Physical Review Letters · doi:10.1103/physrevlett.103.050502 · Cited by 22 · see citing works
Efficient algorithm for approximating one-dimensional ground states
Aharonov, D., Arad, I., & Irani, S. (2010) · Physical Review A · doi:10.1103/physreva.82.012315 · Cited by 22 · see citing works
Aharonov, D., Ben-Or, M., Brandão, F. G. S. L., & Sattath, O. (2022) · Quantum · doi:10.22331/q-2022-03-17-668 · Cited by 21 · see citing works
Condensed Matter Applications of Entanglement TheoryPreprint
Schuch, N. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1306.5551 · Cited by 21 · see citing works
Self-citationImproved numerical methods for infinite spin chains with long-range interactions
Nebendahl, V., & Dür, W. (2013) · Physical Review B · doi:10.1103/physrevb.87.075413 · Cited by 20 · see citing works
Coarse-grained belief propagation for simulation of interacting quantum systems at all temperatures
Bilgin, E., & Poulin, D. (2010) · Physical Review B · doi:10.1103/physrevb.81.054106 · Cited by 19 · see citing works
Breaking the curse of dimension for the electronic Schrödinger equation with functional analysis
Anderson, J. S. M., Heidar‐Zadeh, F., & Ayers, P. W. (2018) · Computational and Theoretical Chemistry · doi:10.1016/j.comptc.2018.08.017 · Cited by 18 · see citing works
Spin lattices with two-body Hamiltonians for which the ground state encodes a cluster state
Griffin, T., & Bartlett, S. D. (2008) · Physical Review A · doi:10.1103/physreva.78.062306 · Cited by 18 · see citing works
Local Hamiltonians in Quantum ComputationPreprint
Nagaj, D. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0808.2117 · Cited by 18 · see citing works
Importance of the Spectral gap in Estimating Ground-State Energies
Deshpande, A., Gorshkov, A. V., & Fefferman, B. (2022) · PRX Quantum · doi:10.1103/prxquantum.3.040327 · Cited by 17 · see citing works
Bounding the Joint Numerical Range of Pauli Strings by Graph Parameters
Xu, Z., Schwonnek, R., & Winter, A. (2024) · PRX Quantum · doi:10.1103/prxquantum.5.020318 · Cited by 14 · see citing works
Hamiltonian simulation for low-energy states with optimal time dependence
Zlokapa, A., & Somma, R. D. (2024) · Quantum · doi:10.22331/q-2024-08-27-1449 · Cited by 12 · see citing works
Flexible Ansatz for N-Body Perturbation Theory
Miranda‐Quintana, R. A., Kim, T. D., Lokhande, R. A., Richer, M., Sánchez‐Díaz, G., Gaikwad, P. B., & Ayers, P. W. (2024) · The Journal of Physical Chemistry A · doi:10.1021/acs.jpca.4c00855 · Cited by 11 · see citing works
Tensor network methods with graph enhancement
Hübener, R., Kruszynska, C., Hartmann, L., Dür, W., Plenio, M. B., & Eisert, J. (2011) · Physical Review B · doi:10.1103/physrevb.84.125103 · Cited by 11 · see citing works
Sign Problem in Tensor-Network Contraction
Chen, J., Jiang, J., Hangleiter, D., & Schuch, N. (2025) · PRX Quantum · doi:10.1103/prxquantum.6.010312 · Cited by 10 · see citing works
Self-citationTesting Non-isometry Is QMA-Complete
Rosgen, B. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-18073-6_6 · Cited by 10 · see citing works
Exact renormalization in quantum spin chains
Tu, H.-H., & Sanz, M. (2010) · Physical Review B · doi:10.1103/physrevb.82.104404 · Cited by 8 · see citing works
Hamiltonian Learning from Time Dynamics Using Variational Algorithms
Gupta, R., Selvarajan, R., Sajjan, M., Levine, R. D., & Kais, S. (2023) · The Journal of Physical Chemistry A · doi:10.1021/acs.jpca.2c08993 · Cited by 7 · see citing works
Matrix product representations for spin-(1/2) and spin-(3/2) spontaneous quantum ferrimagnets
Alipour, S., Baghbanzadeh, S., & Karimipour, V. (2008) · Europhysics Letters (EPL) · doi:10.1209/0295-5075/84/67006 · Cited by 6 · see citing works
Physical consequences of P≠NP and the density matrix renormalization group annealing conjecture
Rodríguez-Laguna, J., & Santalla, S. N. (2014) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2014/07/p07006 · Cited by 4 · see citing works
Testing Quantum Circuits and Detecting Insecure Encryption
Rosgen, B. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-35656-8_6 · Cited by 3 · see citing works
PAC-learning of free-fermionic states is NP-hard
Bittel, L., Mele, A. A., Eisert, J., & Leone, L. (2025) · Quantum · doi:10.22331/q-2025-03-20-1665 · Cited by 2 · see citing works
Simulated annealing for tensor network states
Iblisdir, S. (2014) · New Journal of Physics · doi:10.1088/1367-2630/16/10/103022 · Cited by 2 · see citing works
Testing quantum circuits and detecting insecure encryptionPreprint
Rosgen, B. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1108.1052 · Cited by 2 · see citing works
Utilizing Partitioning for Distributed Tensor Network Contraction
Geiger, M., Huang, Q., & Mendl, C. B. (2026) · SIAM Journal on Scientific Computing · doi:10.1137/25m1788488 · Cited by 1 · see citing works
Out-of-Equilibrium Dynamics with Matrix Product States
Wall, M. L. (2015) · Springer theses · doi:10.1007/978-3-319-14252-4_7 · Cited by 1 · see citing works
Azad, F., McRoberts, A. J., Hooley, C., & Green, A. G. (2025) · Physical Review Research · doi:10.1103/physrevresearch.7.l012037 · Cited by 1 · see citing works
Matrix Product States: Foundations
Wall, M. L. (2015) · Springer theses · doi:10.1007/978-3-319-14252-4_6
Bauer, B. (2011)
Disorder-free dynamic localization in non-adiabatic processes: entanglement entropy and OTOC
Mo, Y., Huang, J., & Yao, Y. (2020) · Journal of Physics Condensed Matter · doi:10.1088/1361-648x/ab85f1
Entanglement and quantum information theory in the context of higher dimensional spin systems.
Hadley, C. (2008) · OpenGrey (Institut de l'Information Scientifique et Technique)
Bounding the joint numerical range of Pauli strings by graph parametersPreprint
Xu, Z., Schwonnek, R., & Winter, A. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2308.00753
Simulation of atomic nuclei and their constituents with quantum computers
Guzman, E. A. R. (2023) · theses.fr (ABES) · doi:10.70675/efb16840z58b5z4c76z8eadzfeae7d3faaaa
- Authors
- Schuch, N., Cirac, I., & Verstraete, F.
- Affiliations
- Max Planck Society (DE)
- University of Vienna (AT)
- Venue
- Physical Review Letters
- Publisher
- American Physical Society (APS)
- Published
- 2008-06-27
- Volume
- 100
- Issue
- 25
- Pages
- 250501-250501
- ISSN
- 0031-9007 (ISSN-L)
- 1079-7114
- OpenAlex
- W2105313913
- Cited by
- 60
- References
- 9
- Citations by year
- 2026: 1 · 2025: 3 · 2024: 3 · 2023: 3 · 2022: 2 · 2021: 1 · 2020: 2 · 2018: 2 · 2015: 6 · 2014: 2 · 2013: 5 · 2012: 5
- FWCI
- 4.84
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Physical Review Letters (publishedVersion)
- PubMed (publishedVersion)
- arXiv (Cornell University) (acceptedVersion)
- Ghent University Academic Bibliography (Ghent University) (submittedVersion, other-oa)
- Max Planck Institute for Plasma Physics (submittedVersion)
- MPG.PuRe (Max Planck Society) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Deutsche Forschungsgemeinschaft
- Topics
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Keywords
- matrix product states, ground state calculation, frustration-free Hamiltonians, one-dimensional Hamiltonians, computational complexity, NP-completeness, ground state uniqueness, variational convergence, quantum many-body systems
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
