Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory

Abstract

One of the central problems in quantum mechanics is to determine the ground state properties of a system of electrons interacting via the Coulomb potential. Since its introduction by Hohenberg, Kohn, and Sham, Density Functional Theory (DFT) has become the most widely used and successful method for simulating systems of interacting electrons, making their original work one of the most cited in physics. In this letter, we show that the field of computational complexity imposes fundamental limitations on DFT, as an efficient description of the associated universal functional would allow to solve any problem in the class QMA (the quantum version of NP) and thus particularly any problem in NP in polynomial time. This 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, while given the universal functional it can be computed efficiently using DFT. This provides a clear illustration how the field of quantum computing is useful even if quantum computers would never be built.

8 pages, 3 figures. v2: Version accepted at Nature Physics; differs significantly from v1 (including new title). Includes an extra appendix (not contained in the journal version) on the NP-completeness of Hartree-Fock, which is taken from v1

References in corpus (6)

• The power of quantum systems on a line
• N-representability is QMA-complete
• Realizable Hamiltonians for Universal Adiabatic Quantum Computers
• Quantum NP - A Survey
• Simulation of Many-Body Hamiltonians using Perturbation Theory with Bounded-Strength Interactions
• The Complexity of Quantum Systems on a One-dimensional Chain

Cited by in corpus (123)

• Adiabatic Quantum Computing
• Quantum Chemistry in the Age of Quantum Computing
• Quantum algorithms: an overview
• Quantum information processing with superconducting circuits: a review
• Training variational quantum algorithms is NP-hard
• Simulating chemistry using quantum computers
• Quantum Metropolis Sampling
• Hybrid quantum-classical approach to correlated materials
• Provably efficient machine learning for quantum many-body problems
• Adiabatic Quantum Simulation of Quantum Chemistry
• Emerging quantum computing algorithms for quantum chemistry
• Standard Model Physics and the Digital Quantum Revolution: Thoughts about the Interface
• Hamiltonian complexity
• Ab initio computations of molecular systems by the auxiliary-field quantum Monte Carlo method
• Quantum Hamiltonian Complexity
• Simple universal models capture all classical spin physics
• Theories of phosphorescence in organo-transition metal complexes - from relativistic effects to simple models and design principles for organic light-emitting diodes
• Universal Quantum Hamiltonians
• Complexity of quantum impurity problems
• Simulating Quantum Materials with Digital Quantum Computers
• Variational Benchmarks for Quantum Many-Body Problems
• Computational Complexity in Electronic Structure
• Relating the pure and ensemble density matrix functional
• Differentiable but exact formulation of density-functional theory
• Diverging exchange force and form of the exact density matrix functional
• Interacting boson problems are QMA-hard
• Introduction to Quantum Algorithms for Physics and Chemistry
• Guaranteed convergence of the Kohn-Sham equations
• Universal adiabatic quantum computation via the space-time circuit-to-Hamiltonian construction
• Shukla-Eliasson Attractive Force: Revisited
• QMA-complete problems for stoquastic Hamiltonians and Markov matrices
• Hamiltonian gadgets with reduced resource requirements
• Quantum de Finetti theorem under fully-one-way adaptive measurements
• Quantum Computing: Lecture Notes
• Comment on "On Novel attractive forces between ions in quantum plasmas -- failure of linearized quantum hydrodynamics"
• Computational Difficulty of Computing the Density of States
• Resource Efficient Gadgets for Compiling Adiabatic Quantum Optimization Problems
• The Feynman-Kitaev computer's clock: bias, gaps, idling and pulse tuning
• The Quantum PCP Conjecture
• Product-state Approximations to Quantum Ground States
• Lanczos recursion on a quantum computer for the Green's function and ground state
• Hamiltonian operator approximation for energy measurement and ground state preparation
• Measures of quantum computing speedup
• Space-Time Circuit-to-Hamiltonian Construction and Its Applications
• Density functional theory on phase space
• QMA-hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge
• Approximation algorithms for QMA-complete problems
• Hybrid Classical/Machine-Learning Force Fields for the Accurate Description of Molecular Condensed-Phase Systems
• Systematic construction of density functionals based on matrix product state computations
• Importance of the spectral gap in estimating ground-state energies
• Grad DFT: a software library for machine learning enhanced density functional theory
• The Bose-Hubbard model is QMA-complete
• Uncomputability of Phase Diagrams
• SGO: An ultrafast engine for ab initio atomic structure global optimization by differential evolution
• Seven Useful Questions in Density Functional Theory
• What the foundations of quantum computer science teach us about chemistry
• Computational complexity of time-dependent density functional theory
• The Northeast Materials Database for Magnetic Materials
• High ground state overlap via quantum embedding methods
• Effective dimension reduction with mode transformations: Simulating two-dimensional fermionic condensed matter systems
• Density functionals and Kohn-Sham potentials with minimal wavefunction preparations on a quantum computer
• The complexity of simulating local measurements on quantum systems
• Complexity of Fermionic Dissipative Interactions and Applications to Quantum Computing
• Computational complexity of non-equilibrium steady states of quantum spin chains
• Self-Consistent Determination of Single-Impurity Anderson Model Using Hybrid Quantum-Classical Approach on a Spin Quantum Simulator
• Density functional theory with adaptive pair density
• Solver for the electronic V-representation problem of time-dependent density functional theory
• Convex Optimization for Nonequilibrium Steady States on a Hybrid Quantum Processor
• Bootstrapping the Quantum Hall problem
• Certificates of quantum many-body properties assisted by machine learning
• Feynman's Clock for open quantum systems
• Complexity classification of local Hamiltonian problems
• Limitations of Hartree-Fock with quantum resources
• Quantum generative model for sampling many-body spectral functions
• Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
• On the NP-completeness of the Hartree-Fock method for translationally invariant systems
• Digital-analog quantum learning on Rydberg atom arrays
• On complexity of the quantum Ising model
• Quantum Many-body Bootstrap
• Stabilizer ground states for simulating quantum many-body physics: theory, algorithms, and applications
• The computational complexity of density functional theory
• Super-resolution of Green's functions on noisy quantum computers
• Quantum simulation of classical thermal states
• Kohn-Sham inversion with mathematical guarantees
• The Local Consistency Problem for Stoquastic and 1-D Quantum Systems
• Two-dimensional local Hamiltonian problem with area laws is QMA-complete
• Electronic Structure in a Fixed Basis is QMA-complete
• Polynomial Time Quantum Gibbs Sampling for Fermi-Hubbard Model at any Temperature
• The commuting local Hamiltonian on locally-expanding graphs is in NP
• Solving lattice gauge theories using the quantum Krylov algorithm and qubitization
• A curved line search algorithm for atomic structure relaxation
• Perturbative gadgets without strong interactions
• The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute
• Efficient state initialization by a quantum spectral filtering algorithm
• Complexity of the XY antiferromagnet at fixed magnetization
• Going Beyond Gadgets: The Importance of Scalability for Analogue Quantum Simulators
• Quantum Zeno approach for molecular energies with maximum commuting initialHamiltonians
• Oracle complexity classes and local measurements on physical Hamiltonians
• Semicoherent Symmetric Quantum Processes: Theory and Applications
• Approximation, Proof Systems, and Correlations in a Quantum World
• The Levy-Lieb embedding of density functional theory and its Quantum Kernel: Illustration for the Hubbard Dimer using near-term quantum algorithms
• Learning Density Functionals from Noisy Quantum Data
• Computability and Complexity of Unconventional Computing Devices
• PAC-learning of free-fermionic states is NP-hard
• Preparation Circuits for Matrix Product States by Classical Variational Disentanglement
• Testing quantum circuits and detecting insecure encryption
• Extracting the spin excitation spectrum of a fermionic system using a quantum processor
• Chemically Motivated Simulation Problems are Efficiently Solvable by a Quantum Computer
• Block Lanczos method for excited states on a quantum computer
• Characterizing maximally many-body entangled fermionic states by using $M$-body density matrix
• Toward Density Functional Theory on Quantum Computers?
• Quantum Phase Recognition via Quantum Attention Mechanism
• Perspective on Moreau-Yosida Regularization in Density-Functional Theory
• Electronic Structure Calculations and the Ising Hamiltonian
• Bootstrapping Flat-band Superconductors: Rigorous Lower Bounds on Superfluid Stiffness
• A Denser Hydrogen Inferred from First-Principles Simulations Challenges Jupiter's Interior Models
• Approximating Ground and Excited State Energies on a Quantum Computer
• Bundled matrix product states represent low-energy excitations faithfully
• Classification on the Computational Complexity of Spin Models
• A penalty-free quantum algorithm to find energy eigenstates
• Electronic Structure Calculatins and the Ising Machine
• Warming Up Density Functional Theory
• Non-NP-Hardness of Translationally-Invariant Spin-Model Problems