This thesis develops new algorithms and theoretical frameworks for quantum many-body physics on near-term, noisy quantum simulators. The first half introduces dissipative "cooling algorithms" based on engineered dissipation to robustly prepare ground and thermal states. These protocols are demonstrated experimentally on Google's superconducting qubit processor, and analysed theoretically via effective quasiparticle theory and developments in connection to quantum detailed balance. The second half studies "mixed state phases" in classical non-equilibrium dynamics, and their connection to the conditional mutual information. A new numerical algorithm based on matrix-product states is introduced to compute this quantity for classical systems, and applied in the settings of spin systems quenched to high temperatures, and diffusive particle dynamics, providing new information-theoretic descriptions of non-equilibrium universality classes.