  A fast implementation of the quantum imaginary time evolution (QITE)
algorithm called Fast QITE is proposed. The algorithmic cost of QITE typically
scales exponentially with the number of particles it nontrivially acts on in
each Trotter step. In contrast, a Fast QITE implementation reduces this to only
a linear scaling. It is shown that this speed up leads to a quantum advantage
when sampling diagonal elements of a matrix exponential, which cannot be
achieved using the standard implementation of the QITE algorithm. Finally the
cost of implementing Fast QITE for finite temperature simulations is also
discussed.
