Quantum impurity models describe an atom or molecule embedded in a host material with which it can exchange electrons. They are basic to nanoscience as representations of quantum dots and molecular conductors and play an increasingly important role in the theory of ``correlated electron'' materials as auxiliary problems whose solution gives the ``dynamical mean-field'' approximation to the self-energy and local correlation functions. These applications require a method of solution which provides access to both high and low energy scales and is effective for wide classes of physically realistic models. The continuous-time quantum Monte~Carlo algorithms reviewed in this article meet this challenge. Derivations and descriptions of the algorithms are presented in enough detail to allow other workers to write their own implementations, discuss the strengths and weaknesses of the methods, summarize the problems to which the new methods have been successfully applied, and outline prospects for future applications.

Quantum Monte Carlo simulations, while being efficient for bosons, suffer from the “negative sign problem” when applied to fermions—causing an exponential increase of the computing time with the number of particles. A polynomial time solution to the sign problem is highly desired since it would provide an unbiased and numerically exact method to simulate correlated quantum systems. Here we show that such a solution is almost certainly unattainable by proving that the sign problem is nondeterministic polynomial (NP) hard, implying that a generic solution of the sign problem would also solve all problems in the complexity class NP in polynomial time.

We present a new continuous-time solver for quantum impurity models such as those relevant to dynamical mean field theory. It is based on a stochastic sampling of a perturbation expansion in the impurity-bath hybridization parameter. Comparisons with Monte Carlo and exact diagonalization calculations confirm the accuracy of the new approach, which allows very efficient simulations even at low temperatures and for strong interactions. As examples of the power of the method we present results for the temperature dependence of the kinetic energy and the free energy, enabling an accurate location of the temperature-driven metal-insulator transition.