Separability of very noisy mixed states and implications for NMR quantum computing

We give a constructive proof that all mixed states of N qubits in a sufficiently small neighborhood of the maximally mixed state are separable. The construction provides an explicit representation of any such state as a mixture of product states. We give upper and lower bounds on the size of the neighborhood, which show that its extent decreases exponentially with the number of qubits. We also discuss the implications of the bounds for NMR quantum computing.