Physical limits of heat-bath algorithmic cooling

Simultaneous near-certain preparation of qubits (quantum bits) in their ground states is a key hurdle in quantum computing proposals as varied as liquid-state NMR and ion traps. "Closed-system" cooling mechanisms are of limited applicability due to the need for a continual supply of ancillas for fault tolerance, and to the high initial temperatures of some systems. "Open-system" mechanisms are therefore required. We describe a new, efficient initialization procedure for such open systems. With this procedure, an n-qubit device that is originally maximally mixed, but is in contact with a heat bath of bias epsilon>2(-n), can be almost perfectly initialized. This performance is optimal due to a newly discovered threshold effect: for bias epsilon<2(-n) no cooling procedure can, even in principle (running indefinitely without any decoherence), significantly initialize even a single qubit.