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

2000/01/31 by S. Parker, M. B. Plenio · 2 citations
Physics and Astronomy · #quant-ph

paper · pdf · doi:10.1103/physrevlett.85.3049

published as Phys. Rev. Lett. 85, 3049 (2000) · 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

arxiv created 2005/11/20 · arxiv updated 2009/12/01

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

Cited by

• Factoring 2048 bit RSA integers with a half-million-qubit modular atomic processor
• Constant-time hybrid compilation of Shor's algorithm with quantum just-in-time compilation