SCIENCE@home

Computational complexity of interacting electrons and fundamental limitations of density functional theory

N. Schuch,F. Verstraete

Published 2007 in Nature Physics

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.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-19 of 19 references · Page 1 of 1

CITED BY

Showing 1-100 of 256 citing papers · Page 1 of 3

123
Next