Computational complexity of interacting electrons and fundamental limitations of density functional theory
Open accessThe DOI matches its Crossref record; 23 of the 23 references it cites were found in a registry or an index.
Abstract
Using arguments from computational complexity theory, fundamental limitations are found for how efficient it is to calculate the ground-state energy of many-electron systems using density functional theory. One of the central problems in quantum mechanics is to determine the ground-state properties of a system of electrons interacting through the Coulomb potential. Since its introduction1,2, density functional theory has become the most widely used and successful method for simulating systems of interacting electrons. Here, we show that the field of computational complexity imposes fundamental limitations on density functional theory. In particular, if the associated ‘universal functional’ could be found efficiently, this would imply that any problem in the computational complexity class Quantum Merlin Arthur could be solved efficiently. Quantum Merlin Arthur is the quantum version of the class NP and thus any problem in NP could be solved in polynomial time. This is considered highly unlikely. Our result follows from the fact that finding the ground-state energy of the Hubbard model in an external magnetic field is a hard problem even for a quantum computer, but, given the universal functional, it can be computed efficiently using density functional theory. This work illustrates how the field of quantum computing could be useful even if quantum computers were never built.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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?
The cited source says what the claim attributes to it.
In the citing paper
“Although this programme is not yet complete, it has already provided some formal justi fi cation for empirical observations in condensed-matter physics about relative hardness of these problems.”
From Quantum algorithms: an overview (2016) · cites this paper as [81]
In the citing paper
“For systems of electrons, one common methodology to avoid treating the size of the full many-electron wave function is density functional theory (DFT) 77,78 . All degrees of freedom of the electronic system are integrated out, except for the density.”
From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [78]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Self-Consistent Equations Including Exchange and Correlation Effects
Kohn, W., & Sham, L. J. (1965) · Physical Review · doi:10.1103/physrev.140.a1133 · Cited by 64,135 · cited 1×
“As the functional (3) is convex and the physical λi,s,s′ form a convex set in R4N, the minimization in equation (2) (up to polynomial accuracy) can be carried out efficiently16; that is, finding the ground-state energy of the Hubbardmodel is in P.”
BackgroundHohenberg, P., & Kohn, W. (1964) · Physical Review · doi:10.1103/physrev.136.b864 · Cited by 53,541
Density-functional theory of atoms and molecules
Patterson, J. D. (1989) · Annals of Nuclear Energy · doi:10.1016/0306-4549(89)90016-9 · Cited by 12,545
Density Functional Theory of Atoms and Molecules
Parr, R. G. (1980) · Horizons of Quantum Chemistry · doi:10.1007/978-94-009-9027-2_2 · Cited by 11,964 · cited 2×
“V -representability [ 14 ]: given a local density ρ(r), does there exist a potential V (r) such that the Hamiltonian T + I + V [Eq. (1)] has a unique ground state with local density ρ(r)? The lattice version of the problem is the following: Given a local density ρ on the lattice, decide whether there exists a potentia…”
BackgroundMethodElectron correlations in narrow energy bands
Hubbard, J. (1963) · Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences · doi:10.1098/rspa.1963.0204 · Cited by 6,699 · cited 3×
“6, and has been included in the Supplementary Information: in (4), we choose an on-site repulsion U very large as compared to t , and operate the system in the so-called half-occupancy regime where there are as many electrons as sites.”
BackgroundMethodA Simplification of the Hartree-Fock Method
Slater, J. C. (1951) · Physical Review · doi:10.1103/physrev.81.385 · Cited by 4,584 · cited 1×
“As the functional (3) is convex and the physical λi,s,s′ form a convex set in R4N, the minimization in equation (2) (up to polynomial accuracy) can be carried out efficiently16; that is, finding the ground-state energy of the Hubbardmodel is in P.”
BackgroundGeometric Algorithms and Combinatorial Optimization
Grötschel, M., Lovász, L., & Schrijver, A. (1988) · Algorithms and Combinatorics · doi:10.1007/978-3-642-97881-4 · Cited by 3,431 · cited 1×
“As the functional (3) is convex and the physical λ i , s , s ′ form a convex set in , the minimization in equation (2) (up to polynomial accuracy) can be carried out efficientl”
BackgroundDreizler, R. M., & Gross, E. K. U. (1990) · Springer eBooks · doi:10.1007/978-3-642-86105-5 · Cited by 2,570
Interacting Electrons and Quantum Magnetism
Auerbach, A. (1994) · Graduate Texts in Contemporary Physics · doi:10.1007/978-1-4612-0869-3 · Cited by 1,738 · cited 1×
“in [ 2 , 8]. Except for being a special case of interacting electrons, the Hubbard model is of high interest on its own, as it is believed to be the appropriate model for understanding effects like high-temperature superconductivity, quantum magnetism, and heavy fermions.”
BackgroundClassical and Quantum Computation
Kitaev, A., Shen, A., & Vyalyi, M. (2002) · Graduate Studies in Mathematics · doi:10.1090/gsm/047 · Cited by 1,387
Kurth, S., Marques, M. A. L., & Gross, E. K. U. (2005) · Encyclopedia of Condensed Matter Physics · doi:10.1016/b0-12-369401-9/00445-9 · Cited by 1,370
Electron correlations in narrow energy bands. II. The degenerate band case
Hubbard, J. (1964) · Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences · doi:10.1098/rspa.1964.0019 · Cited by 1,195 · cited 4×
“Putting these gadgets together, we have managed to reduce the QMA-complete Hamiltonian (5) to the Heisenberg Hamiltonian in a magnetic field on a sparse lattice.”
BackgroundMethodInfluentialThe Complexity of the Local Hamiltonian Problem
Kempe, J., Kitaev, A., & Regev, O. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539704445226 · Cited by 648
The complexity of quantum spin systems on a two-dimensional square lattice
Oliveira, R. I., & Terhal, B. M. (2008) · Quantum Information and Computation · doi:10.26421/qic8.10-2 · Cited by 362 · cited 1×
“We start off with the Hamiltonian defined on a 2D lattice with N spins, with A ( i j ) and B ( i j ) Pauli matrices and | λ |≤1 , for which it has been proven that finding the ground-state energy up to a polynomial accuracy 1/ q ( N ) is QMA-har”
Density Functional Theory: Advances in Applications
(2018) · De Gruyter eBooks · doi:10.1515/9783110568196 · Cited by 322
Quantum Computational Complexity of the N -Representability Problem: QMA Complete
Liu, Y.-K., Christandl, M., & Verstraete, F. (2007) · Physical Review Letters · doi:10.1103/physrevlett.98.110503 · Cited by 211
Self-citationThe Power of Quantum Systems on a Line
Aharonov, D., Gottesman, D., Irani, S., & Kempe, J. (2009) · Communications in Mathematical Physics · doi:10.1007/s00220-008-0710-3 · Cited by 210
Realizable Hamiltonians for universal adiabatic quantum computers
Biamonte, J. D., & Love, P. J. (2008) · Physical Review A · doi:10.1103/physreva.78.012352 · Cited by 173
The complexity of quantum spin systems on a two-dimensional square lattice
Oliveira, R. I., & Terhal, B. M. (2008) · CERN Document Server (European Organization for Nuclear Research) · doi:10.5555/2016985.2016987 · Cited by 144
Aharonov, D., & Naveh, T. (2002) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0210077 · Cited by 111
Bravyi, S., DiVincenzo, D. P., Loss, D., & Terhal, B. M. (2008) · Physical Review Letters · doi:10.1103/physrevlett.101.070503 · Cited by 93 · cited 1×
“Each step makes use of perturbation-theory constructions (so-called gadgets), such that the original Hamiltonian arises as the effective low-energy theory of the new Hamiltonia”
BackgroundThe Complexity of Quantum Systems on a One-dimensional ChainPreprint
Irani, S. (2007) · arXiv (Cornell University) · doi:10.48550/arxiv.0705.4067 · Cited by 19
The complexity of quantum spin systems on a two-dimensional square latticePreprint
Oliveira, R. I., & Terhal, B. M. (2005) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0504050 · Cited by 14 · cited 1×
“We start off with the Hamiltonian defined on a 2D lattice with N spins, with A ( i j ) and B ( i j ) Pauli matrices and | λ |≤1 , for which it has been proven that finding the ground-state energy up to a polynomial accuracy 1/ q ( N ) is QMA-har”
Cited by
Quantum Chemistry in the Age of Quantum Computing
Cao, Y., Romero, J., Olson, J. P., Degroote, M., Johnson, P. D., Kieferová, M., Kivlichan, I. D., Menke, T., Peropadre, B., Sawaya, N. P. D., et al. (2019) · Chemical Reviews · doi:10.1021/acs.chemrev.8b00803 · Cited by 1,560
“re assembled sequentially to form the complete variational ansatz U VarMG () = YL l=1 UNN(l) VarMG (l) YM i=1 RZ i Z i ; (64) with only one round of variational phase rotations RZ i Z i = eiZi˙iz: (65) The variational state therefore has the form j#TAB#() i= Uy BogU VarMG () YN i=1 Xij0i M; (66) where U Bog is the Wtr…”
BackgroundAlbash, T., & Lidar, D. A. (2018) · Reviews of Modern Physics · doi:10.1103/revmodphys.90.015002 · Cited by 1,546
“(99) and (100) below], fully ferromagnetic and fully antiferromagnetic Heisenberg model with local fields (Schuch and Verstraete, 2009), antiferromagnetic Heisenberg and XY models without local fields (Piddock and Montanaro, 2015).”
BackgroundYu, H. S., He, X., Li, S. L., & Truhlar, D. G. (2016) · Chemical Science · doi:10.1039/c6sc00705h · Cited by 1,278
Quantum algorithms: an overview
Montanaro, A. (2016) · npj Quantum Information · doi:10.1038/npjqi.2015.23 · Cited by 1,071
“One can even go further than this, and attempt to characterise for which families of physical systems calculating ground-state energies is hard, and for which the problem is easy [87, 70].”
Quantum information processing with superconducting circuits: a review
Wendin, G. (2017) · Reports on Progress in Physics · doi:10.1088/1361-6633/aa7e1a · Cited by 890
Metadata
- Authors
- Schuch, N., & Verstraete, F.
- Affiliations
- Max Planck Institute of Quantum Optics (DE)
- University of Vienna (AT)
- Corresponding author
- Schuch, Norbert
- Verstraete, Frank
- Venue
- Nature Physics
- Published
- 2009-08-23
- Volume
- 5
- Issue
- 10
- Pages
- 732-735
- ISSN
- 1745-2473 (ISSN-L)
- 1745-2481
- OpenAlex
- W2153671025
- Cited by
- 260
- References
- 22
- Citations by year
- 2026: 16 · 2025: 27 · 2024: 14 · 2023: 16 · 2022: 17 · 2021: 22 · 2020: 13 · 2019: 10 · 2018: 11 · 2017: 15 · 2016: 17 · 2015: 15 · 2014: 21 · 2013: 14 · 2012: 11
- FWCI
- 11.19
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Licence
- www.springernature.com/gp/researchers/text-and-data-mining (tdm)
- www.springernature.com/gp/researchers/text-and-data-mining (vor)
- Locations
- Nature Physics (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
- Kempe Foundation
- Austrian Science Fund
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Advanced Chemical Physics Studies
- Keywords
- density functional theory, computational complexity, ground state energy, interacting electrons, Coulomb potential, Hubbard model, quantum computing, fundamental limits, NP-hardness
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.