Efficient factorization with a single pure qubit and $logN$ mixed qubits

Abstract

It is commonly assumed that Shor's quantum algorithm for the efficient factorization of a large number $N$ requires a pure initial state. Here we demonstrate that a single pure qubit together with a collection of $lo{g}_{2}N$ qubits in an arbitrary mixed state is sufficient to implement Shor's factorization algorithm efficiently.

5 pages including 2 figures. Final version submitted to PRL. Now includes additional comments on entanglement and mixedness as algorithm proceeds. Added references to work by Mosca