  The second-order Matsubara Green's function method (GF2) is a robust
temperature dependent quantum chemistry approach, extending beyond the
random-phase approximation. However, till now the scope of GF2 applications was
quite limited as they require computer resources which rise steeply with system
size. In each step of the self-consistent GF2 calculation there are two parts:
the estimation of the self-energy from the previous step's Green's function,
and updating the Green's function from the self-energy. The first part formally
scales as the fifth power of the system size while the second has a much
gentler cubic scaling. Here, we develop a stochastic approach to GF2 (sGF2)
which reduces the fifth power scaling of the first step to merely quadratic,
leaving the overall sGF2 scaling as cubic. We apply the method to linear
hydrogen chains containing up to 1000 electrons, showing that the approach is
numerically stable, efficient and accurate. The stochastic errors are very
small, of the order of 0.1% or less of the correlation energy for large
systems, with only a moderate computational effort. The first iteration of GF2
is an MP2 calculation that is done in linear scaling, hence we obtain an
extremely fast stochastic MP2 (sMP2) method as a by-product. While here we
consider finite systems with large band gaps where at low temperatures effects
are negligible, the sGF2 formalism is temperature dependent and general and can
be applied to finite or periodic systems with small gaps at finite
temperatures.
