Erratum for the short (PRL) version of "Physical limits of heat-bath algorithmic cooling". ----- There is a numerical error in an example given in the paper. The following sentence appears in paragraph 4 of page 2: "For example, perfect implementation of the PPA on a 5-qubit molecule (4 computation qubits and one refrigerant) would yield a qubit of bias 16 epsilon, implying a 256-fold decrease in scan duration compared to cooling without algorithmic amplification." The sentence should read: "For example, perfect implementation of the PPA on a 5-qubit molecule (4 computation qubits and one refrigerant) would yield a qubit of bias 8 epsilon, implying a 64-fold decrease in scan duration compared to cooling without algorithmic amplification." The long (SICOMP) version of the paper carries the correct sentence.