Efficient factorization with a single pure qubit and $log N$ mixed qubits

S. Parker, M. B. Plenio

Published 2000-01-18, updated 2005-11-20Version 3

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 $log_2 N$ qubits in an arbitrary mixed state is sufficient to implement Shor's factorization algorithm efficiently.