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
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
Aspuru-Guzik, A., & Walther, P. (2012) · Nature Physics · doi:10.1038/nphys2253 · Cited by 952
“Recently, Schuch and Verstraete showed that finding an exact density functional for interacting electrons, would be Quantum Merlin Arthur (QMA)-Hard, that is, belonging to a class of problems thought too hard even for quantum computers 30,31 .”
Peverati, R., & Truhlar, D. G. (2014) · Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rsta.2012.0476 · Cited by 734
“A completely universal functional is extremely hard to determine because it is very complicated and non-local, and therefore probably it will never be found [193].”
BackgroundMulticonfiguration Pair-Density Functional Theory
Li Manni, G., Carlson, R. K., Luo, S., Ma, D., Olsen, J., Truhlar, D. G., & Gagliardi, L. (2014) · Journal of Chemical Theory and Computation · doi:10.1021/ct500483t · Cited by 492
Training Variational Quantum Algorithms Is NP-Hard
Bittel, L., & Kliesch, M. (2021) · Physical Review Letters · doi:10.1103/physrevlett.127.120502 · Cited by 398
“Despite being NP-hard [24] it is widely used in many practical calculations.”
BackgroundSimulating Chemistry Using Quantum Computers
Kassal, I., Whitfield, J. D., Perdomo-Ortiz, A., Yung, M.-H., & Aspuru-Guzik, A. (2011) · Annual Review of Physical Chemistry · doi:10.1146/annurev-physchem-032210-103512 · Cited by 352
Perspective: Kohn-Sham density functional theory descending a staircase
Yu, H. S., Li, S. L., & Truhlar, D. G. (2016) · The Journal of Chemical Physics · doi:10.1063/1.4963168 · Cited by 317
Temme, K., Osborne, T. J., Vollbrecht, K. G., Poulin, D., & Verstraete, F. (2011) · Nature · doi:10.1038/nature09770 · Cited by 305
Self-citationProvably efficient machine learning for quantum many-body problems
Huang, H.-Y., Kueng, R., Torlai, G., Albert, V. V., & Preskill, J. (2022) · Science · doi:10.1126/science.abk3333 · Cited by 228
DFT exchange: sharing perspectives on the workhorse of quantum chemistry and materials science
Teale, A. M., Helgaker, T., Savin, A., Adamo, C., Aradi, B., Arbuznikov, A. V., Ayers, P. W., Baerends, E. J., Barone, V., Calaminici, P., et al. (2022) · Physical Chemistry Chemical Physics · doi:10.1039/d2cp02827a · Cited by 289
Hybrid Quantum-Classical Approach to Correlated Materials
Bauer, B., Wecker, D., Millis, A. J., Hastings, M. B., & Troyer, M. (2016) · Physical Review X · doi:10.1103/physrevx.6.031045 · Cited by 243
“[2] Norbert Schuch and Frank Verstraete, “Computational complexity of interacting electrons and fundamental limitations of density functional theory,” Nature Physics 5, 732–735 (2009).”
BackgroundQuantum Algorithms: A Survey of Applications and End-to-end Complexities
Dalzell, A. M., McArdle, S., Berta, M., Bienias, P., Chen, C.-F., Gilyén, A., Hann, C. T., Kastoryano, M. J., Khabiboulline, E. T., Kubica, A., et al. (2023) · RWTH Publications (RWTH Aachen) · doi:10.18154/rwth-2026-02888 · Cited by 361
Combining Wave Function Methods with Density Functional Theory for Excited States
Ghosh, S., Verma, P., Cramer, C. J., Gagliardi, L., & Truhlar, D. G. (2018) · Chemical Reviews · doi:10.1021/acs.chemrev.8b00193 · Cited by 253
Standard model physics and the digital quantum revolution: thoughts about the interface
Klco, N., Roggero, A., & Savage, M. J. (2022) · Reports on Progress in Physics · doi:10.1088/1361-6633/ac58a4 · Cited by 166
Emerging quantum computing algorithms for quantum chemistry
Motta, M., & Rice, J. E. (2022) · WIREs Computational Molecular Science · doi:10.1002/wcms.1580 · Cited by 173
“(5) grows combinatorially with the size of the studied system [44, 45].”
BackgroundAdiabatic Quantum Simulation of Quantum Chemistry
Babbush, R., Love, P. J., & Aspuru-Guzik, A. (2014) · Scientific Reports · doi:10.1038/srep06603 · Cited by 191
Ab initio computations of molecular systems by the auxiliary‐field quantum Monte Carlo method
Motta, M., & Zhang, S. (2018) · WIREs Computational Molecular Science · doi:10.1002/wcms.1364 · Cited by 160
Quantum Computing: Lecture NotesPreprint
de Wolf, R. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1907.09415 · Cited by 221
Osborne, T. J. (2012) · Reports on Progress in Physics · doi:10.1088/0034-4885/75/2/022001 · Cited by 165
“The original QMA results developed above have been used to show that ground-state simulation problem is QMA hard for both fermions [83] and bosons [90].”
MethodQuantum Chemical Calculations and Experimental Investigations of Molecular Actinide Oxides
Kovács, A., Konings, R. J. M., Gibson, J. K., Infante, I., & Gagliardi, L. (2015) · Chemical Reviews · doi:10.1021/cr500426s · Cited by 147
Quantum 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
Guest column: the quantum PCP conjecture
Aharonov, D., Arad, I., & Vidick, T. (2013) · ACM SIGACT News · doi:10.1145/2491533.2491549 · Cited by 104
“To mention a few: the equivalence of quantum computation and adiabatic quantum computation [16], extensions of QMA-hardness to restricted classes of Hamiltonians [16, 17, 18] including the counterintuitive discovery that even local Hamiltonians acting on nearest-neighbor particles arranged on a line are QMA-hard [19],…”
BackgroundUniversal quantum Hamiltonians
Cubitt, T. S., Montanaro, A., & Piddock, S. (2018) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1804949115 · Cited by 177
“tional complexity of the ground state energy problem for the Heisenberg model with arbitrarily varying local fields was shown to be the maximum possible (QMA-complete [KSV02]) by Schuch and Verstraete [SV09]. The availability of local fields breaks the symmetry of the model, simplifying the analysis. The complexity of t…”
BackgroundJohnson, T. H., Clark, S. R., & Jaksch, D. (2014) · EPJ Quantum Technology · doi:10.1140/epjqt10 · Cited by 127
Xu, X., Zhang, W., Tang, M., & Truhlar, D. G. (2015) · Journal of Chemical Theory and Computation · doi:10.1021/acs.jctc.5b00081 · Cited by 134
Complexity Classification of Local Hamiltonian Problems
Cubitt, T. S., & Montanaro, A. (2016) · SIAM Journal on Computing · doi:10.1137/140998287 · Cited by 173
“Schuch and Verstraete [10] previously proved QMAhardness of the Heisenberg model where arbitrary 1-local terms are also allowed, or in other words QMA-hardness of {XX + Y Y + ZZ}-HAMILTONIAN WITH LOCAL TERMS.”
BackgroundMethodInfluentialSimple universal models capture all classical spin physics
Cuevas, G. D. L., & Cubitt, T. S. (2016) · Science · doi:10.1126/science.aab3326 · Cited by 128
Powell, B. J. (2015) · Coordination Chemistry Reviews · doi:10.1016/j.ccr.2015.02.008 · Cited by 114
Complexity of Quantum Impurity Problems
Bravyi, S., & Gosset, D. (2017) · Communications in Mathematical Physics · doi:10.1007/s00220-017-2976-9 · Cited by 84
“Formally, this problem is complete for the complexity class QMA – a quantum analogue of NP [11, 12].”
BackgroundElectronic Structure Calculations and the Ising Hamiltonian
Xia, R., Bian, T., & Kais, S. (2018) · The Journal of Physical Chemistry B · doi:10.1021/acs.jpcb.7b10371 · Cited by 96
Quantum algorithms for quantum dynamics
Miessen, A., Ollitrault, P. J., Tacchino, F., & Tavernelli, I. (2022) · Nature Computational Science · doi:10.1038/s43588-022-00374-2 · Cited by 130
“In general, however, this can be a hard task even for quantum computers 11,12 .”
BackgroundSimulating quantum materials with digital quantum computers
Oftelie, L. B., Urbánek, M., Metcalf, M., Carter, J. T., Kemper, A. F., & de Jong, W. A. (2021) · Quantum Science and Technology · doi:10.1088/2058-9565/ac1ca6 · Cited by 101
On Complexity of the Quantum Ising Model
Bravyi, S. B., & Hastings, M. B. (2016) · Communications in Mathematical Physics · doi:10.1007/s00220-016-2787-4 · Cited by 110
“d state energy for certain physically-motivated quantum models such as Hamiltonians with nearest-neighbor interactions on the two-dimensional [2] and one-dimensional [3,4] lattices, the Hubbard model [5,6], and the Heisenberg model [5,7]. In contrast, a broad class of Hamiltonians known as sign-free or stoquastic [8]…”
MethodVariational benchmarks for quantum many-body problems
Wu, D., Rossi, R., Vicentini, F., Astrakhantsev, N., Becca, F., Cao, X., Carrasquilla, J., Ferrari, F., Georges, A., Hibat-Allah, M., et al. (2024) · Science · doi:10.1126/science.adg9774 · Cited by 79
“However, it is generally not straightforward to compute the mean-field energy as it is in itself an NP-hard problem [64], there exist many variants of mean-field theory, and it could make weak-coupling calculations beyond mean-field theory artificially hard.”
BackgroundQuantum Algorithms: A Survey of Applications and End-to-end Complexities
Dalzell, A. M., McArdle, S., Berta, M., Bienias, P., Chen, C.-F., Gilyén, A., Hann, C. T., Kastoryano, M. J., Khabiboulline, E. T., Kubica, A., et al. (2025) · Cambridge University Press eBooks · doi:10.1017/9781009639651 · Cited by 146
Pure non-local machine-learned density functional theory for electron correlation
Margraf, J. T., & Reuter, K. (2021) · Nature Communications · doi:10.1038/s41467-020-20471-y · Cited by 88
“(3)) can be determined in closed form, for a given training set (see Supplementary Note 3).”
BackgroundTheoretical methods for small-molecule ro-vibrational spectroscopy
Lodi, L., & Tennyson, J. (2010) · Journal of Physics B Atomic Molecular and Optical Physics · doi:10.1088/0953-4075/43/13/133001 · Cited by 87
Quantum Algorithms for Scientific Computing and Approximate Optimization
Hadfield, S. (2018) · arXiv (Cornell University) · doi:10.7916/d8x650c9 · Cited by 31
“On the other hand, there are a number of recent results in discrete complexity theory suggesting that many eigenvalue problems are very hard even for quantum computers because they are QMAcomplete [61, 148, 205, 243].”
BackgroundComputational 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
Quantum Hamiltonian Complexity
Gharibian, S., Huang, Y., Landau, Z. A., & Shin, S. W. (2015) · now publishers, Inc. eBooks · doi:10.1561/9781680830071 · Cited by 72
Quantum computing with and for many-body physics
Ayral, T., Besserve, P., Lacroix, D., & Guzman, E. A. R. (2023) · The European Physical Journal A · doi:10.1140/epja/s10050-023-01141-1 · Cited by 84
Na, G. S., & Chang, H. (2022) · npj Computational Materials · doi:10.1038/s41524-022-00897-2 · Cited by 85
“However, although DFT achieved numerous successes as a generally applicable method to analyze the crystalline systems, the applicability of DFT is still limited to the materials of small unit cells due to exponential computational costs in huge unit cells 15,16 .”
MethodDifferentiable but exact formulation of density-functional theory
Kvaal, S., Ekström, U., Teale, A. M., & Helgaker, T. U. (2014) · The Journal of Chemical Physics · doi:10.1063/1.4867005 · Cited by 67
QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge
Broadbent, A., & Grilo, A. B. (2022) · SIAM Journal on Computing · doi:10.1137/21m140729x · Cited by 78
Communication: Relating the pure and ensemble density matrix functional
Schilling, C. (2018) · The Journal of Chemical Physics · doi:10.1063/1.5080088 · Cited by 78
Kang, Y., Li, L., & Li, B. (2020) · Journal of Energy Chemistry · doi:10.1016/j.jechem.2020.05.044 · Cited by 67
Interacting Boson Problems Can Be QMA Hard
Wei, T.-C., Mosca, M., & Nayak, A. (2010) · Physical Review Letters · doi:10.1103/physrevlett.104.040501 · Cited by 55
Introduction to Quantum Algorithms for Physics and Chemistry
Yung, M., Whitfield, J. D., Boixo, S., Tempel, D. G., & Aspuru‐Guzik, A. (2014) · Advances in Chemical Physics · doi:10.1002/9781118742631.ch03 · Cited by 50
“For recent developments in the connections between DFT and quantum complexity 14 see Schuch & Verstraete (2009b), while for applications of DFT to adiabatic quantum computation see Gaitan & Nori (2009).”
BackgroundDiverging Exchange Force and Form of the Exact Density Matrix Functional
Schilling, C., & Schilling, R. (2019) · Physical Review Letters · doi:10.1103/physrevlett.122.013001 · Cited by 70
“matically proven complexity of the ground state problem [49, 50] and the complexity is just shifted from the set of underlying 1RDMs to the derivation of the functional Fe and/or its minimization [51].”
BackgroundThe Quantum PCP ConjecturePreprint
Aharonov, D., Arad, I., & Vidick, T. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1309.7495 · Cited by 70
“a proof that a famous problem in physics (known as the \universal functional" 5 problem, and related to nding the groundstate of electrons interacting through the Coulomb potential) is QMA-hard [SV09]. However, viewed from a wider perspective, the current situation in quantum Hamiltonian complexity can be compare…”
BackgroundProduct-state approximations to quantum ground states
Brandão, F. G. S. L., & Harrow, A. W. (2013) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2488608.2488719 · Cited by 104
“Since then there have been several developments showing that simpler classes of local Hamiltonians are still hard [32, 36, 46], culminating in the QMA-completeness of the problem for Hamiltonians on a line [4] even when all the local terms are the same and the only input is the length of the line expressed in unary [2…”
BackgroundThe complexity of antiferromagnetic interactions and 2D lattices
Piddock, S., & Montanaro, A. (2017) · Quantum Information and Computation · doi:10.26421/qic17.7-8-6 · Cited by 55
“A number of subsequent works have therefore attempted to show that Local Hamiltonian remains QMA-complete, even with more physically realistic restrictions on the interactions [21, 3, 26, 25, 12, 10].”
BackgroundMethodIntractability of Electronic Structure in a Fixed Basis
O’Gorman, B., Irani, S., Whitfield, J. D., & Fefferman, B. (2022) · PRX Quantum · doi:10.1103/prxquantum.3.020322 · Cited by 59
Quantum-Merlin-Arthur–complete problems for stoquastic Hamiltonians and Markov matrices
Jordan, S. P., Gosset, D., & Love, P. J. (2010) · Physical Review A · doi:10.1103/physreva.81.032331 · Cited by 41
“In addition to its intrinsic interest this subject has many connections to issues of practical relevance to physical science, such as the difficulty of computing properties of quantum systems using either quantum or classical devices [11, 19, 24].”
BackgroundApproximation Algorithms for QMA-Complete Problems
Gharibian, S., & Kempe, J. (2012) · SIAM Journal on Computing · doi:10.1137/110842272 · Cited by 61
“In the last few years, the quantum analog of the class NP, the class QMA [KSV02], has been extensively studied, and several QMA-complete problems have been found [Liu06, Bra06, LCV07, BS07, Ros09, JGL10, SV09, WMN10].”
BackgroundGuaranteed Convergence of the Kohn-Sham Equations
Wagner, L. O., Stoudenmire, E. M., Burke, K., & White, S. R. (2013) · Physical Review Letters · doi:10.1103/physrevlett.111.093003 · Cited by 60
“[36] Norbert Schuch and Frank Verstraete, “Computational complexity of interacting electrons and fundamental limitations of density functional theory,” Nat.”
BackgroundUniversal Adiabatic Quantum Computation via the Space-Time Circuit-to-Hamiltonian Construction
Gosset, D., Terhal, B. M., & Vershynina, A. (2015) · Physical Review Letters · doi:10.1103/physrevlett.114.140501 · Cited by 47
Resource efficient gadgets for compiling adiabatic quantum optimization problems
Babbush, R., O'Gorman, B., & Aspuru‐Guzik, A. (2013) · Annalen der Physik · doi:10.1002/andp.201300120 · Cited by 33
“[23] N.”
MethodProduct-state Approximations to Quantum Ground StatesPreprint
Brandão, F. G. S. L., & Harrow, A. W. (2013) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 44
Shukla–Eliasson attractive force: Revisited
Akbari-Moghanjoughi, M. (2012) · Journal of Plasma Physics · doi:10.1017/s0022377812000839 · Cited by 43
“[43] Schuch, N & Verstraete, F 2009 Computational complexity of interacting electrons and fundamental limitations of density functional theory Nature Phys.”
BackgroundComplexity Classification of Local Hamiltonian Problems
Cubitt, T. S., & Montanaro, A. (2014) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2014.21 · Cited by 47
Hamiltonian Operator Approximation for Energy Measurement and Ground-State Preparation
Bespalova, T. A., & Kyriienko, O. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.030318 · Cited by 55
“We note that the problem of preparing exact ground state of the many-body Hamiltonian is QMAcomplete [97].”
BackgroundEntanglement Theory and the Quantum Simulation of Many-Body PhysicsPreprint
Brandão, F. G. S. L. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0810.0026 · Cited by 54
Hashimoto, W., Tsuji, Y., & Yoshizawa, K. (2020) · The Journal of Physical Chemistry C · doi:10.1021/acs.jpcc.0c01106 · Cited by 42
Product-State Approximations to Quantum States
Brandão, F. G. S. L., & Harrow, A. W. (2016) · Communications in Mathematical Physics · doi:10.1007/s00220-016-2575-1 · Cited by 68
“Since then there have been several developments showing that simpler classes of local Hamiltonians are still hard [34,40,49], culminating in the QMA-completeness of the problem for Hamiltonians on a line [5] even when all the local terms are the same and the only input is the length of the line expressed in unary [25].”
BackgroundQuantum de Finetti Theorem under Fully-One-Way Adaptive Measurements
Li, K., & Smith, G. (2015) · Physical Review Letters · doi:10.1103/physrevlett.114.160503 · Cited by 41
Gharibian, S., & Gall, F. L. (2022) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3519935.3519991 · Cited by 79
Bookatz, A. D. (2012) · Cited by 38
Space-time circuit-to-Hamiltonian construction and its applications
Breuckmann, N. P., & Terhal, B. M. (2014) · Journal of Physics A Mathematical and Theoretical · doi:10.1088/1751-8113/47/19/195304 · Cited by 49
“This result goes beyond the perturbative approach used in [26] as all terms in the Hamiltonians here are of strength O(1).”
BackgroundHamiltonian gadgets with reduced resource requirements
Cao, Y., Babbush, R., Biamonte, J., & Kais, S. (2015) · Physical Review A · doi:10.1103/physreva.91.012315 · Cited by 35
“Hamiltonian gadgets were also used to characterize the complexity of density functional theory [13] and are required components in current proposals related to error correction on an adiabatic quantum computer [14] and the adiabatic and ground state quantum simulator [9, 10].”
MethodUnmasking Static Correlation Error in Hybrid Kohn–Sham Density Functional Theory
Zhang, D., & Truhlar, D. G. (2020) · Journal of Chemical Theory and Computation · doi:10.1021/acs.jctc.0c00585 · Cited by 35
Shukla, P. K., Eliasson, B., & Akbari-Moghanjoughi, M. (2013) · Physical Review E · doi:10.1103/physreve.87.037101 · Cited by 35
Quantum Davidson algorithm for excited states
Tkachenko, N. V., Cincio, Ł., Boldyrev, A. I., Tretiak, S., Dub, P. A., & Zhang, Y. (2024) · Quantum Science and Technology · doi:10.1088/2058-9565/ad3a97 · Cited by 57
Clocks in Feynman's computer and Kitaev's local Hamiltonian: Bias, gaps, idling, and pulse tuning
Caha, L., Landau, Z. A., & Nagaj, D. (2018) · Physical Review A · doi:10.1103/physreva.97.062306 · Cited by 42
Chaffart, D., & Ricardez‐Sandoval, L. (2017) · Journal of Process Control · doi:10.1016/j.jprocont.2017.07.002 · Cited by 33
How Well Can the M06 Suite of Functionals Describe the Electron Densities of Ne, Ne6+, and Ne8+?
Wang, Y., Wang, X., Truhlar, D. G., & He, X. D. (2017) · Journal of Chemical Theory and Computation · doi:10.1021/acs.jctc.7b00865 · Cited by 33
Lanczos recursion on a quantum computer for the Green's function and ground state
Baker, T. E. (2021) · Physical Review A · doi:10.1103/physreva.103.032404 · Cited by 48
“This a task that has seen rapid development recently, so other sources may be useful for this [4, 5].”
BackgroundInfluentialThe northeast materials database for magnetic materials
Itani, S., Zhang, Y., & Zang, J. (2025) · Nature Communications · doi:10.1038/s41467-025-64458-z · Cited by 39
“Does it allow you to identify sections of articles that contain data you wish to extract?”
The complexity of simulating local measurements on quantum systems
Gharibian, S., & Yirka, J. (2019) · Quantum · doi:10.22331/q-2019-09-30-189 · Cited by 39
“firstopenquestionabovebyshowing[33]that APX-SIM remains PQMA[log]-complete for any family of local Hamiltonians which can simulate “spatiallysparse”[51]Hamiltonians. This,inturn,implies(e.g. using[53],[58],[54])thatAPX-SIM remainsPQMA[log]-completeevenonphysicallymotivatedmodels,suchastheHeisenberginteraction ona2Dsqua…”
MethodGharibian, S., & Gall, F. L. (2023) · SIAM Journal on Computing · doi:10.1137/22m1513721 · Cited by 47
Computational 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
Self-citationŠmíd, Š., Meister, R., Berta, M., & Bondesan, R. (2025) · Nature Communications · doi:10.1038/s41467-025-65765-1 · Cited by 50
Uncomputability of phase diagrams
Bausch, J., Cubitt, T. S., & Watson, J. D. (2021) · Nature Communications · doi:10.1038/s41467-020-20504-6 · Cited by 42
Bao, J. L., Zhang, X., Xu, X., & Truhlar, D. G. (2017) · Physical Chemistry Chemical Physics · doi:10.1039/c6cp08896a · Cited by 35
Machine learning predictions of superalloy microstructure
Taylor, P., & Conduit, G. J. (2021) · Computational Materials Science · doi:10.1016/j.commatsci.2021.110916 · Cited by 30
The Bose-Hubbard model is QMA-completePreprint
Childs, A. M., Gosset, D., & Webb, Z. (2013) · Cited by 30
Rapidly predicting Kohn–Sham total energy using data-centric AI
Kurban, H., Kurban, M., & Dalkilic, M. M. (2022) · Scientific Reports · doi:10.1038/s41598-022-18366-7 · Cited by 31
Quantum Many-body BootstrapPreprint
Han, X. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.06002 · Cited by 43
“In general, the problem is intrinsically difficult [1] and advances are often made with the aid of symmetries, approximations and numerics.”
BackgroundImportance 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 35
“[63] N.”
MethodMeasures of quantum computing speedup
Papageorgiou, A., & Traub, J. F. (2013) · Physical Review A · doi:10.1103/physreva.88.022316 · Cited by 30
Warming Up Density Functional Theory
Smith, J. C., Sagredo, F., & Burke, K. (2017) · Springer eBooks · doi:10.1007/978-981-10-5651-2_11 · Cited by 28
“on energy and bond length(s). A substantially more sophisticated test occurs when a highly accurate calculation is performed such as QMC[CKB79; NU99] or DMRG[W92], and an inversion of the KS equations[SV09], so that essentially exact KS potentials, eigenvalues, orbitals, etc, can all be deduced. This is a much more po…”
MethodThe Bose-Hubbard Model is QMA-complete
Childs, A. M., Gosset, D., & Webb, Z. (2014) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-43948-7_26 · Cited by 18
“There are also frustration-free states where two of the three particles are located in the same two-qubit gadget J ∈ [M ] and one of the particles is located in a diagram element L1 from a different component of the graph.”
BackgroundBookatz, A. D. (2014) · Quantum Information and Computation · doi:10.26421/qic14.5-6-1 · Cited by 26
“In quantum chemistry, density functional theory (DFT) is a method for approximating the ground-state energy of an electron system (see [34] and the references therein).”
MethodInfluentialThürlemann, M., Böselt, L., & Riniker, S. (2023) · Journal of Chemical Theory and Computation · doi:10.1021/acs.jctc.2c00661 · Cited by 33
Aharonov, D., & Eldar, L. (2014) · Quantum Information Processing · doi:10.1007/s11128-014-0877-9 · Cited by 31
“A key player in QHC is the local Hamiltonian problem (LH) [27], whose study had led to various unexpected discoveries, ranging from the universality of adiabatic computation [5], to the QMA hardness of one-dimensional systems [6], to quantum gadgets [16,29,31], to computational complexity lower bounds on notorious ope…”
BackgroundGradDFT. A software library for machine learning enhanced density functional theory
Casares, P. A. M., Baker, J. S., Medvidović, M., dos Reis, R., & Arrazola, J. M. (2024) · The Journal of Chemical Physics · doi:10.1063/5.0181037 · Cited by 25
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.