  Controlled preparation of highly pure quantum states is at the core of
practical applications of quantum information science, from the state
initialization of most quantum algorithms to a reliable supply of ancilla
qubits that satisfy the fault-tolerance threshold for quantum error correction.
Heat-bath algorithmic cooling has been shown to purify qubits by controlled
redistribution of entropy and multiple contact with a bath, not only for
ensemble implementations but also for technologies with strong but imperfect
measurements. However, an implicit restriction about the interaction with the
bath has been assumed in previous work. In this paper, we show that better
purification can be achieved by removing that restriction. More concretely, we
include correlations between the system and the bath, and we take advantage of
these correlations to pump entropy out of the system into the bath. We
introduce a tool for cooling algorithms, which we call "state-reset", obtained
when the coupling to the environment is generalized from individual-qubits
relaxation to correlated-qubit relaxation. We present improved cooling
algorithms which lead to an increase of purity beyond all the previous work,
and relate our results to the Nuclear Overhauser Effect.
