DFT calculations: Complexity, stability, and quantum advantage

Abstract

In this talk we will discuss algorithmic perspectives of DFT calculations. The first part is dedicated to the computation of the Fermi level and the density matrix in a system of atoms with localized orbitals. We discuss how to compute both of those quantities in the current “matrix-multiplication” time, provably accurately, in the prevailing floating-point model of computation. In the second part we consider nearly linear-scaling algorithms for sparse systems in the real-RAM model of computation, aiming once again for the smallest worst-case asymptotic complexity that can guarantee accurate results. We finally compare with recent state-of-the-art quantum algorithms for the same problems and discuss the possibilities of quantum advantage.