  Fluctuation theorems provide a correspondence between properties of quantum
systems in thermal equilibrium and a work distribution arising in a
non-equilibrium process that connects two quantum systems with Hamiltonians
$H_0$ and $H_1=H_0+V$. Building upon these theorems, we present a quantum
algorithm to prepare a purification of the thermal state of $H_1$ at inverse
temperature $\beta \ge 0$ starting from a purification of the thermal state of
$H_0$. The complexity of the quantum algorithm, given by the number of uses of
certain unitaries, is $\tilde {\cal O}(e^{\beta (\Delta \! A- w_l)/2})$, where
$\Delta \! A$ is the free-energy difference between $H_1$ and $H_0,$ and $w_l$
is a work cutoff that depends on the properties of the work distribution and
the approximation error $\epsilon>0$. If the non-equilibrium process is
trivial, this complexity is exponential in $\beta \|V\|$, where $\|V\|$ is the
spectral norm of $V$. This represents a significant improvement of prior
quantum algorithms that have complexity exponential in $\beta \|H_1\|$ in the
regime where $\|V\|\ll \|H_1\|$. The dependence of the complexity in $\epsilon$
varies according to the structure of the quantum systems. It can be exponential
in $1/\epsilon$ in general, but we show it to be sublinear in $1/\epsilon$ if
$H_0$ and $H_1$ commute, or polynomial in $1/\epsilon$ if $H_0$ and $H_1$ are
local spin systems. The possibility of applying a unitary that drives the
system out of equilibrium allows one to increase the value of $w_l$ and improve
the complexity even further. To this end, we analyze the complexity for
preparing the thermal state of the transverse field Ising model using different
non-equilibrium unitary processes and see significant complexity improvements.
