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
Items 101–200 of 283
Introduction to Quantum Information and Computation for Chemistry
Kais, S. (2014) · Advances in chemical physics · doi:10.1002/9781118742631.ch01 · Cited by 40
Aaronson, S. (2009) · Nature Physics · doi:10.1038/nphys1415 · Cited by 25
Martínez-Alonso, C., Vassilev-Galindo, V., Comer, B. M., Abild‐Pedersen, F., Winther, K. T., & LLorca, J. (2024) · Catalysis Science & Technology · doi:10.1039/d4cy00491d · Cited by 25
Nanoscale and ultrafast in situ techniques to probe plasmon photocatalysis
Carlin, C. C., Dai, A., Al-Zubeidi, A., Simmerman, E. M., Oh, H., Gross, N., Lee, S., Link, S., Landes, C. F., da Jornada, F. H., et al. (2023) · Chemical Physics Reviews · doi:10.1063/5.0163354 · Cited by 26
Density functional theory on phase space
Blanchard, P., a, J. M. G. I., & Várilly, J. C. (2011) · International Journal of Quantum Chemistry · doi:10.1002/qua.23101 · Cited by 24
Introduction to Effective Low‐Energy Hamiltonians in Condensed Matter Physics and Chemistry
Powell, B. J. (2011) · Wiley eBooks · doi:10.1002/9780470930779.ch10 · Cited by 27
Rao, A. S. M., Pundir, V. S., Tiwari, A., Padarthi, Y., Rao, N. V. M., Aich, S., & Roy, B. (2017) · Journal of Physics and Chemistry of Solids · doi:10.1016/j.jpcs.2017.10.030 · Cited by 23
Computing the Many-Body Green’s Function with Adaptive Variational Quantum Dynamics
Gomes, N., Williams‐Young, D. B., & de Jong, W. A. (2023) · Journal of Chemical Theory and Computation · doi:10.1021/acs.jctc.3c00150 · Cited by 29
Perturbative gadgets without strong interactions
Cao, Y., & Nagaj, D. (2015) · Quantum Information and Computation · doi:10.26421/qic15.13-14-7 · Cited by 31
“Initially introduced by Kempe, Kitaev and Regev [1] for showing the QMA-hardness of 2-Local Hamiltonian problem and subsequently used and developed further in numerous works [2, 3, 4, 5, 6, 7, 8], perturbative gadgets are convenient tools by which arbitrary many-body effective interactions (which we call the target Ha…”
BackgroundSystematic construction of density functionals based on matrix product state computations
Lubasch, M., Fuks, J. I., Appel, H., Rubio, Á., Cirac, J. I., & Bañuls, M. C. (2016) · New Journal of Physics · doi:10.1088/1367-2630/18/8/083039 · Cited by 26
Liu, Y., & Luo, J. X. (2018) · Journal of Photochemistry and Photobiology A Chemistry · doi:10.1016/j.jphotochem.2018.11.018 · Cited by 22
Piddock, S., & Montanaro, A. (2021) · Communications in Mathematical Physics · doi:10.1007/s00220-021-03940-3 · Cited by 24
“same sign [38]; we achieve this in Theorem3, but in general leave this extension for future work. Another interesting direction is to prove universality for systems with simpler interaction patterns [36,41,38,17], or with less heavily-weighted interactions [13]. 1.2 Related work There has been a substantial amount of…”
BackgroundInfluentialThürlemann, M., & Riniker, S. (2023) · Chemical Science · doi:10.1039/d3sc04317g · Cited by 23
Digital–analog quantum learning on Rydberg atom arrays
Lu, J. Z., Jiao, L., Wolinski, K., Kornjača, M., Hu, H.-Y., Cantu, S., Liu, F., Yelin, S. F., & Wang, S.-T. (2024) · Quantum Science and Technology · doi:10.1088/2058-9565/ad9177 · Cited by 29
High Ground State Overlap via Quantum Embedding Methods
Eraković, M., Witteveen, F., Harley, D., Günther, J., Bensberg, M., Meitei, O. R., Cho, M., Voorhis, T. V., Reiher, M., & Christandl, M. (2025) · PRX Life · doi:10.1103/prxlife.3.013003 · Cited by 25
“The general electronic structure problem is QMA-complete [15,67], meaning that it is likely a hard problem even for quantum computers.”
Ding, T., Wu, Q., Nie, Z., Zheng, M., Wang, Y., & Yang, D. (2022) · Polymer Testing · doi:10.1016/j.polymertesting.2022.107647 · Cited by 20
QMA-hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge
Broadbent, A., & Grilo, A. B. (2020) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs46700.2020.00027 · Cited by 28
“: We note that a number of problems are currently known to be QMAcomplete under Turing reductions, including the N - representability [54] and bosonic N -representability problems [55] as well as the universal functional of density function theory (DFT) [56].”
BackgroundLee, C. H., Pahari, S., Barteau, M. A., & Kwon, J. S. (2024) · Applied Catalysis B: Environmental · doi:10.1016/j.apcatb.2024.124434 · Cited by 20
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 25
Baker, T. E., & Poulin, D. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.043238 · Cited by 27
What the foundations of quantum computer science teach us about chemistry
McClean, J. R., Rubin, N. C., Lee, J., Harrigan, M. P., O’Brien, T. E., Babbush, R., Huggins, W. J., & Huang, H.-Y. (2021) · The Journal of Chemical Physics · doi:10.1063/5.0060367 · Cited by 24
“20–22 In this work, we highlight some of the yet unexplored connections leading up to a perspective on the role both traditional and quantum computers may play in the future of chemistry.”
BackgroundQMA variants with polynomially many provers
Gharibian, S., Sikora, J., & Upadhyay, S. (2013) · Quantum Information and Computation · doi:10.26421/qic13.1-2-8 · Cited by 21
“[6, 7, 8, 9, 10, 11, 12, 13]), with the quantum analogue of classical constraint satisfaction, the physically motivated k-local Hamiltonian problem [5, 14, 15, 16, 17], being the canonical QMA-complete problem.”
BackgroundSeven useful questions in density functional theory
Crisostomo, S., Pederson, R. D., Kozlowski, J., Kalita, B., Cancio, A. C., Datchev, K. R., Wasserman, A., Song, S., & Burke, K. (2023) · Letters in Mathematical Physics · doi:10.1007/s11005-023-01665-z · Cited by 19
Tempel, D. G., & Aspuru-Guzik, A. (2012) · Scientific Reports · doi:10.1038/srep00391 · Cited by 20
Classical simulation of quantum many-body systems
Huang, Y. (2015) · eScholarship (California Digital Library) · Cited by 21
Bootstrapping the Quantum Hall Problem
Gao, Q., Lanzetta, R. A., Ledwith, P., Wang, J., & Khalaf, E. (2025) · Physical Review X · doi:10.1103/csnn-vjhn · Cited by 22
“However, characterizing the set P 2 N , known as the N -representability problem [46], turns out to be a hard problem; determining whether a 2-RDM belongs to P 2 N was proven to be QMA-hard [49].”
Toward density functional theory on quantum computers?
Senjean, B., Yalouz, S., & Saubanère, M. (2023) · SciPost Physics · doi:10.21468/scipostphys.14.3.055 · Cited by 28
“Instead, recent works focus on the challenging construction of accurate exchange-correlation (XC) density functionals – for which the precise determination is QMA-hard [ 37 ] – using matrix product states, machine learning and quantum computers [ 38–43 ] .”
BackgroundPahari, S., Lee, C. H., Johnson, D., Yesudoss, D. K., Shah, P., Barteau, M. A., Djire, A., & Kwon, J. S. (2025) · ACS Catalysis · doi:10.1021/acscatal.5c02077 · Cited by 18
Zero-Knowledge for QMA from Locally Simulatable Proofs.Preprint
Broadbent, A., & Grilo, A. B. (2019) · arXiv (Cornell University) · Cited by 19
Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian Problems.
Parekh, O., & Thompson, K. (2021) · doi:10.2172/1884207 · Cited by 16
Chaffart, D., & Ricardez‐Sandoval, L. (2017) · The Canadian Journal of Chemical Engineering · doi:10.1002/cjce.22912 · Cited by 16
SGO: A fast engine for ab initio atomic structure global optimization by differential evolution
Chen, Z., Jia, W., Jiang, X., Li, S., & Wang, L. (2017) · Computer Physics Communications · doi:10.1016/j.cpc.2017.05.005 · Cited by 18
Computational complexity of time-dependent density functional theory
Whitfield, J. D., Yung, M.-H., Tempel, D. G., Boixo, S., & Aspuru-Guzik, A. (2014) · New Journal of Physics · doi:10.1088/1367-2630/16/8/083035 · Cited by 15
Quantum Information and Computation for Chemistry
Olson, J., Cao, Y., Romero, J., Johnson, P., Dallaire-Demers, P.-L., Sawaya, N., Narang, P., Kivlichan, I., Wasielewski, M., & Aspuru-Guzik, A. (2017) · arXiv · doi:10.48550/arxiv.1706.05413 · Cited by 15
“…used on quantum chemistry problems such as electronic structure calculation (Whitfield, Love, and Aspuru-Guzik, 2013) and density functional theory (Schuch and Verstraete, 2009) to provide a new perspective on the extent to which quantum computers may help current quantum chemical calculations.”
Nie, X., Zhu, X., Fan, Y.-A., Long, X., Liu, H., Huang, K., Cheng, X., Che, L., Zheng, Y., Feng, Y., et al. (2024) · Physical Review Letters · doi:10.1103/physrevlett.133.140602 · Cited by 14
“These steps become increasingly intractable with classical methods when dealing with a larger number of correlated orbitals, owing to the heightened computational complexity [19–21].”
BackgroundCertificates of quantum many-body properties assisted by machine learning
Requena, B., Muñoz-Gil, G., Lewenstein, M., Dunjko, V., & Tura, J. (2023) · Physical Review Research · doi:10.1103/physrevresearch.5.013097 · Cited by 18
Peverati, R. (2020) · International Journal of Quantum Chemistry · doi:10.1002/qua.26379 · Cited by 15
Rearranging the Exponential Wall for Large N -Body Systems
Watson, D. K., & Dunn, M. (2010) · Physical Review Letters · doi:10.1103/physrevlett.105.020402 · Cited by 15
An introduction to effective low-energy Hamiltonians in condensed matter physics and chemistryPreprint
Powell, B. J. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0906.1640 · Cited by 33
Solving lattice gauge theories using the quantum Krylov algorithm and qubitization
Anderson, L. W., Kiffner, M., O’Leary, T., Crain, J. N., & Jaksch, D. (2025) · Quantum · doi:10.22331/q-2025-03-25-1669 · Cited by 25
Density functional theory investigation on triboelectric nanogenerator: A comprehensive review
Rehman, H. U., Wang, N., Shoaib, M., Sun, E., Zhu, Q., Zhao, Z., Farhan, M., & Afzal, A. (2025) · Sensors and Actuators A Physical · doi:10.1016/j.sna.2025.116866 · Cited by 15
Krumnow, C., Veis, L., Eisert, J., & Legeza, Ö. (2021) · Physical review. B./Physical review. B · doi:10.1103/physrevb.104.075137 · Cited by 16
Force field-inspired transformer network assisted crystal density prediction for energetic materials
Jin, J.-X., Ren, G., Hu, J., Liu, Y., Gao, Y., Wu, K., & He, Y. (2023) · Journal of Cheminformatics · doi:10.1186/s13321-023-00736-6 · Cited by 14
Complexity of Fermionic Dissipative Interactions and Applications to Quantum Computing
Shtanko, O., Deshpande, A., Julienne, P. S., & Gorshkov, A. V. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.030350 · Cited by 17
Sun, J., Cheng, L., & Zhang, S. (2025) · Quantum · doi:10.22331/q-2025-06-24-1782 · Cited by 24
“The difficulty stems from the exponential scaling of the Hilbert space di-mension, rendering exact calculations impractical in most cases [1, 2, 3, 4, 5, 6].”
Convex Optimization for Nonequilibrium Steady States on a Hybrid Quantum Processor
Lau, J. W. Z., Lim, K. H., Bharti, K., Kwek, L. C., & Vinjanampathy, S. (2023) · Physical Review Letters · doi:10.1103/physrevlett.130.240601 · Cited by 16
Block Lanczos method for excited states on a quantum computer
Baker, T. E. (2024) · Physical Review A · doi:10.1103/physreva.110.012420 · Cited by 19
Chemically motivated simulation problems are efficiently solvable on a quantum computer
Schleich, P., Kristensen, L. B., Campos-Gonzalez-Angulo, J. A., Aldossary, A., Avagliano, D., Bagherimehrab, M., Gorgulla, C., Fitzsimons, J., & Aspuru‐Guzik, A. (2026) · Digital Discovery · doi:10.1039/d5dd00377f · Cited by 15
The Kitaev–Feynman clock for open quantum systems
Tempel, D. G., & Aspuru‐Guzik, A. (2014) · New Journal of Physics · doi:10.1088/1367-2630/16/11/113066 · Cited by 12
Quantum generative model for sampling many-body spectral functions
Sels, D., & Demler, E. (2021) · Physical review. B./Physical review. B · doi:10.1103/physrevb.103.014301 · Cited by 13
Buchs, G., Beck, T. L., Bennink, R. S., Claudino, D., Delgado, A., Fadel, N. A., Groszkowski, P., Hamilton, K. E., Humble, T. S., Kumar, N., et al. (2026) · Future Generation Computer Systems · doi:10.1016/j.future.2026.108487 · Cited by 16
“…clear winner emerges, the 2D Fermi-Hubbard model describing interacting fermions (e.g., electrons) [156] is a time-tested hard problem for classical computers and it is proved that its ground state problem with local magnetic field is QMA-hard [157], i.e., a hard problem even for quantum computers.”
Computational complexity of nonequilibrium steady states of quantum spin chains
Marzolino, U., & Prosen, T. (2016) · Physical Review A · doi:10.1103/physreva.93.032306 · Cited by 12
Testing Non-isometry Is QMA-Complete
Rosgen, B. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-18073-6_6 · Cited by 11
“…other complete problems for QMA are known, such as local consistency [12] (see also [13, 19]), some problems related to the minimum output entropy [2], testing whether unitary circuits are close to the identity [6] (see also [7]), and finding the ground states of some physical systems [16, 17].”
BackgroundApproximation Algorithms for QMA-Complete Problems
Gharibian, S., & Kempe, J. (2011) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2011.15 · Cited by 13
The commuting local Hamiltonian on locally-expanding graphs is in NPPreprint
Aharonov, D., & Eldar, L. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1311.7378 · Cited by 11
“A key player in QHC is the local Hamiltonian problem (LH) [30], 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 [32, 41, 19], to computational complexity lower bounds on notorious o…”
BackgroundKohn-Sham inversion with mathematical guarantees
Herbst, M. F., Bakkestuen, V. H., & Laestadius, A. (2025) · Physical review. B./Physical review. B · doi:10.1103/physrevb.111.205143 · Cited by 10
“However, one of the key ingredients of DFT, the universal density functional, is not known explicitly [5].”
Lorenzana, J., Ying, Z., & Brosco, V. (2012) · Physical Review B · doi:10.1103/physrevb.86.075131 · Cited by 10
Solver for the ElectronicV-Representation Problem of Time-Dependent Density Functional Theory
Brown, J. C., Yang, J., & Whitfield, J. D. (2020) · Journal of Chemical Theory and Computation · doi:10.1021/acs.jctc.9b00583 · Cited by 10
Oracle Complexity Classes and Local Measurements on Physical Hamiltonians
Gharibian, S., Piddock, S., & Yirka, J. (2019) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.stacs.2020.20 · Cited by 12
“But, there is not always a blow-up in the locality of A , as is shown by this corollary which follows from Theorem 1.6 and [SV09]: Corollary 1.8.”
BackgroundInfluentialLimitations of Hartree–Fock with quantum resources
Gulania, S., & Whitfield, J. D. (2021) · The Journal of Chemical Physics · doi:10.1063/5.0018415 · Cited by 10
Denser hydrogen inferred from first-principles simulations challenges Jupiter’s interior models
Cozza, C., Nakano, K., Howard, S., Xie, H., Helled, R., & Mazzola, G. (2026) · Physical Review Research · doi:10.1103/yrk6-ryps · Cited by 10
“Even within the Born-Oppenheimer approximation, solving the fixed-nuclei Schr¨odinger equation requires computational resources that grow exponentially with N [43].”
On the NP-completeness of the Hartree-Fock method for translationally invariant systems
Whitfield, J. D., & Zimborás, Z. (2014) · The Journal of Chemical Physics · doi:10.1063/1.4903453 · Cited by 9
Ou, L., Chen, Y., & Jin, J. (2016) · RSC Advances · doi:10.1039/c6ra10321a · Cited by 9
Back to The Future: A Roadmap for Quantum Simulation From Vintage Quantum Chemistry
Love, P. J. (2014) · Advances in chemical physics · doi:10.1002/9781118742631.ch02 · Cited by 9
“[84] Norbert Schuch and Frank Verstraete.”
Bi-level identification of governing equations for nonlinear physical systems
Li, Z., Yuan, H., Han, W., Hou, Y., Li, H., Ding, H., Jiang, Z., & Yang, L. (2025) · Nature Computational Science · doi:10.1038/s43588-025-00804-x · Cited by 16
Patra, A., V., A., Sai Shankar, P., Bhat, R., V, R., Maitra, R., & Jaiganesh, G. (2025) · Journal of Chemical Physics · doi:10.1063/5.0338676 · Cited by 11
“With the advent of quantum computers, the accurate simulation of chemically and biologically relevant systems are expected to become increasingly tractable.”
Preparation circuits for matrix product states by classical variational disentanglement
Mansuroglu, R., & Schuch, N. (2026) · Physical Review A · doi:10.1103/7x2g-twkl · Cited by 13
Self-citationSmall InAsN and InN clusters: electronic properties and nitrogen stability belt
Pozhar, L. A. (2010) · The European Physical Journal D · doi:10.1140/epjd/e2010-00067-x · Cited by 8
Going beyond gadgets: the importance of scalability for analogue quantum simulators
Harley, D., Datta, I., Klausen, F. R., Blühm, A., França, D. S., Werner, A. H., & Christandl, M. (2024) · Nature Communications · doi:10.1038/s41467-024-50744-9 · Cited by 15
“…especially focus on the use of gadgets for Hamiltonian locality reduction, though it should be noted that perturbative gadgets can also be used to simplify the structure of the interaction hypergraph 17 and, in general, to reduce Hamiltonians to more restrictive families of interactions 44,56,57 .”
Predicting Crystalline Material Properties with AI: Bridging Molecular to Particle Scales
Chen, W., Li, M., Yao, T., Liu, J., Jia, S., Gao, Z., & Gong, J. (2024) · Industrial & Engineering Chemistry Research · doi:10.1021/acs.iecr.4c03224 · Cited by 10
Extracting the spin excitation spectrum of a fermionic system using a quantum processor
Vilchez-Estevez, L., Santos, R. A., Wang, S. Y., & Gambetta, F. M. (2025) · Physical review. B./Physical review. B · doi:10.1103/ydfw-k83n · Cited by 13
“However, preparing the ground state of inter-acting many-body systems on a quantum simulator is a challenging problem on its own [77, 78] and, in general, costly in terms of circuit implementation [45, 79–81].”
Xu, M. K., Wang, S., He, Y., Li, Y., Zhang, W., Yang, M., Qi, X., Wang, Z., Xu, M., Shang, D., et al. (2025) · Nature Computational Science · doi:10.1038/s43588-025-00844-3 · Cited by 11
“However, the high computational cost of DFT restricts its applicability to large-scale material systems 13–16 .”
Computability and Complexity of Unconventional Computing Devices
Broersma, H. J., Stepney, S., & Wendin, G. P. (2018) · Natural computing series · doi:10.1007/978-3-319-65826-1_11 · Cited by 9
Two-dimensional local Hamiltonian problem with area laws is QMA-complete
Huang, Y. (2021) · Journal of Computational Physics · doi:10.1016/j.jcp.2021.110534 · Cited by 11
The Computational Complexity of Density Functional Theory
Whitfield, J. D., Schuch, N., & Verstraete, F. (2014) · Mathematical physics studies · doi:10.1007/978-3-319-06379-9_14 · Cited by 8
“This chapter is largely an expansion of [20] with additional results regarding Kohn-Sham DFT.”
ResultSelf-citationThe Local Consistency Problem for Stoquastic and 1-D Quantum SystemsPreprint
Liu, Y.-K. (2007) · arXiv (Cornell University) · doi:10.48550/arxiv.0712.1388 · Cited by 8
Seniority-zero wavefunction parameterizations
Calero-Osorio, D. F., & Ayers, P. W. (2025) · Theoretical Chemistry Accounts · doi:10.1007/s00214-025-03245-x · Cited by 8
Recent Results in the Exact Treatment of Fermions at Zero and Finite Temperature
Tubman, N. M., DuBois, J. L., & Alder, B. J. (2012) · ACS symposium series · doi:10.1021/bk-2012-1094.ch004 · Cited by 7
Jiang, H. Y., & Sun, H. (2022) · Elsevier eBooks · doi:10.1016/b978-0-323-90049-2.00002-0 · Cited by 8
Watson, D. K., & Dunn, M. (2012) · Journal of Physics B Atomic Molecular and Optical Physics · doi:10.1088/0953-4075/45/9/095002 · Cited by 7
The Complexity of Local Stoquastic Hamiltonians on 2D Lattices
Waite, G., & Bremner, M. J. (2026) · Quantum · doi:10.22331/q-2026-05-06-2097 · Cited by 6
Miháliková, I., Krejčí, M., & Friák, M. (2025) · Scientific Reports · doi:10.1038/s41598-025-00151-x · Cited by 6
Physically motivated guiding states for local Hamiltonians
Waite, G., Lin, K., Elman, S. J., & Bremner, M. J. (2026) · Physical Review A · doi:10.1103/clj1-v2zz · Cited by 6
Approximate Hessian for acceleratingab initiostructure relaxation by force fitting
Chen, Z., Li, J., Li, S., & Wang, L. (2014) · Physical Review B · doi:10.1103/physrevb.89.144110 · Cited by 6
Superresolution of Green's functions on noisy quantum computers
Cruz, D., & Magano, D. (2023) · Physical Review A · doi:10.1103/physreva.108.012618 · Cited by 7
“Unfortunately, the Green’s functions of many-body strongly-correlated systems are notoriously hard to compute classically [22].”
BackgroundBootstrapping Flatband Superconductors: Rigorous Lower Bounds on Superfluid Stiffness
Gao, Q., Han, Z., & Khalaf, E. (2026) · Physical Review Letters · doi:10.1103/gw85-5r92 · Cited by 6
“This is known as the N -representability problem [46] and is QMA-hard (the quantum analogue of NP-hard) [61].”
Quantum Simulation of Classical Thermal States
Dür, W., & den Nest, M. V. (2011) · Physical Review Letters · doi:10.1103/physrevlett.107.170402 · Cited by 5
2D Local Hamiltonian with Area Laws Is QMA-Complete
Huang, Y. (2020) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit44484.2020.9174029 · Cited by 7
“The field strengths in (15) are upper bounded by a fixed polynomial in n [23]: |hi′ | ≤ p(n) = 1/poly(n) for any i ′.”
BackgroundMethodApproximation, Proof Systems, and Correlations in a Quantum WorldPreprint
Gharibian, S. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.2632 · Cited by 6
“Although these results are interesting from a complexity theoretic perspective, a more natural question from a physics perspective is whether such QMA-hardness results can be shown even if the QMA-hard classes of local Hamiltonians arising in the reductions employed correspond to physical quantum systems in nature [20…”
BackgroundUnderstanding Correlated Materials with DMFTPreprint
Pavarini, E., Koch, E., Lichtenstein, A. I., & Vollhardt, D. (2025) · arXiv (Cornell University) · doi:10.34734/fzj-2025-03722 · Cited by 4
Characterizing maximally many-body entangled fermionic states by using M -body density matrix
Giorgadze, I., Huang, H., Gaines, J., König, E. J., & Väyrynen, J. I. (2025) · Quantum · doi:10.22331/q-2025-06-24-1778 · Cited by 7
“This problem is QMA-hard, highlighting the difficulty of ensuring that ρ (2) is compatible with an antisymmetrized N -particle wave function [48, 49].”
Orthorhombic Structures as Inorganic Halide Perovskite Models for High-Throughput DFT Investigations
Yew, S., Morelock, R. J., & Musgrave, C. B. (2025) · The Journal of Physical Chemistry C · doi:10.1021/acs.jpcc.4c08125 · Cited by 5
Jones, E. B., Winkleblack, C. J., Campbell, C., Rotello, C., Dahl, E. D., Reynolds, M. R., Graf, P. A., & Jones, W. B. (2025) · Physical Review Research · doi:10.1103/physrevresearch.7.023186 · Cited by 6
Top research priorities in quantum computing
Hatay, E. S., Golec, M., Nguyen, H. T., Gill, S. S., Patros, P., Xu, M., Singh, M., RANA, O. F., Abraham, A., Qadir, J., et al. (2025) · Elsevier eBooks · doi:10.1016/b978-0-443-29096-1.00011-8 · Cited by 7
Curved-line search algorithm for ab initio atomic structure relaxation
Chen, Z.-H., Li, J., Li, S.-S., & Wang, L.-W. (2015) · Physical review. B./Physical review. B · doi:10.1103/physrevb.96.115141 · Cited by 4
Wang, H., & Yu, S. (2021) · Quantum Information Processing · doi:10.1007/s11128-020-02984-z · Cited by 6
Introducing LibXC into GAMESS (US)
Gerasimov, I. S., Zahariev, F. E., Leang, S. S., Tesliuk, A., Gordon, M. S., & Medvedev, M. G. (2021) · Mendeleev Communications · doi:10.1016/j.mencom.2021.04.008 · Cited by 5
Wolf, M. M. (2008) · Nature Physics · doi:10.1038/nphys1124 · Cited by 5
Two-dimensional local Hamiltonian problem with area laws is QMA-completePreprint
Huang, Y. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1411.6614 · Cited by 5
“• The 2D Heisenberg and Hubbard models with local magnetic fields are QMA-complete [14].”
MethodReinventing Density Functional Theory with Machine Learning on Integral Features
Zhang, D., Shu, Y., & Truhlar, D. G. (2026) · Journal of Chemical Theory and Computation · doi:10.1021/acs.jctc.6c00999 · Cited by 6
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.