I will discuss classical algorithms for computing low-energy states of quantum impurity models.  Such models describe a bath of free fermions coupled to a small interacting subsystem called an impurity. Hamiltonians of this form were famously studied by Anderson, Kondo, Wilson and others in 1960s. Impurity models also play the central role in modern material simulation algorithms based on the DMFT method. Quite recently it was suggested that DMFT simulation algorithms may benefit from quantum computers. As a first step,  one may wish to use a quantum computer for preparing the ground state of an impurity model and extracting some information about its dynamics such as the impurity Green's function. This motivates the question of whether ground states of impurity models posses any simple structure and under what conditions they can be prepared efficiently. Here we show that ground states of  impurity models can be approximated by low-rank Gaussian states -- superpositions of a small number of fermionic Gaussian states. As a corollary we obtain a classical algorithm for approximating the ground energy of impurity models. The running time of our algorithm is polynomial in the system size and quasi-polynomial in the inverse approximation error. 

Based on a joint work with David Gosset