Efficient Factorization with a Single Pure Qubit and<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:mi>log</mml:mi><mml:mi mathvariant="italic">N</mml:mi></mml:math>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 log 2N qubits in an arbitrary mixed state, is sufficient to implement Shor's factorization algorithm efficiently.