The complexity of many-body quantum systems grows exponentially with the number of particles. This is often prohibitive to treating these systems numerical without further assumptions. In most physical scenarios, however, additional structure is available such as locality of interactions. We analyse algorithms that compute the free energy of one-dimensional and lattice quantum systems and give rigorous bounds on their runtime.