# Do we know anything about the computational complexity of the exchange-correlation functional?

Density functional theory is based on the Hohenberg-Kohn (HK) theorems and aims to compute the ground-state many-body wavefunction of a physical material and/or molecules.

To put it simply, the HK theorems show that there is a unique one-to-one mapping between a many-body Hamiltonian $$\mathcal{H}$$ (like you'd encounter in quantum chemistry or in the solid-state), and the electron density $$\rho(\mathbf{r})$$. This relationship is quite surprising, especially since you reduce the information of the wavefunction $$\psi$$ with $$3N$$ variables to a function of just $$3$$ variables.

The catch here is that extracting information from $$\rho(\mathbf{r})$$ is quite difficult, and you can only really do it exactly if you know the exchange-correlation functional term $$\frac{\delta E_{xc}[\rho]}{\delta \rho(\mathbf{r})}$$, but no one knows what this functional looks like exactly.

My question is the following:

Do we know anything about the computational complexity of evaluating the exchange-correlation functional in either the classical or quantum computing cases?

## 1 Answer

Computing the exchange-correlation functional to sufficiently high accuracy is QMA-hard, where QMA is the quantum version of NP. In particular, this means that it is will all likelihood hard even for a quantum computer.

• This is actually quite surprising (at least for my naive self)! Thank you for your answer. Is it right to conclude that this means that dealing with the true exchange correlation functional will forever be impractical? – user157879 Sep 21 '20 at 1:26