A quantum impurity model describes a bath of free fermions coupled to a small interacting subsystem called an impurity. Such models were studied in the 1960s and 1970s (by Anderson, Kondo, Wilson, and others) to investigate the physics of a magnetic impurity embedded in a metal. More recently, they have been used to study strongly correlated materials within an approximation known as dynamical mean field theory.

Quantum impurity models provide a natural arena for studying the computational complexity of fermionic systems in an intermediate regime interpolating between the free and fully interacting cases. In general it is known that approximating the ground energy of a fully interacting fermionic system is a computationally hard problem. In contrast, Hamiltonians describing free fermions are exactly solvable and their ground energy can be computed in polynomial time. In this work we describe a classical algorithm for approximating the ground energy and computing low energy states of quantum impurity models. The runtime of the algorithm is polynomial in the total number of fermi modes and quasipolynomial in the desired approximation error. We anticipate that our algorithm may be used in hybrid quantum-classical simulations of strongly correlated materials. This is joint work with Sergey Bravyi (arXiv:1609.00735).