Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Efficient factorization with a single pure qubit

Scott Parker, Martin Bodo Plenio

Published Jan 18, 2000• 4 citations
OpenAlex

Abstract

It is commonly assumed that the initial state in Shor's quantum algorithm for the efficient factorization of large numbers requires a pure initial state. Here we demonstrate that a single pure qubit together with a collection of qubits in an arbitrary mixed state is sufficient to implement Shor's factorization algorithm efficiently.

Related papers

Efficient Factorization with a Single Pure Qubit and logN Mixed Qubits

S. Parker, Martin Bodo Plenio

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.

arXiv:quant-ph/0001066•Physical Review Letters•Oct 2, 2000•134 citations

Entanglement simulations of Shor's algorithm

S. Parker, Martin Bodo Plenio

We demonstrate that, in the case of Shor's algorithm for factoring, highly mixed states will allow efficient quantum computation, indeed factorization can be achieved efficiently with just one initial pure qubit and a supply of initially maximally mixed qubits (Parker, S. and Plenio, M. B., 2000, Phys. Rev. Lett., 85, 3049). This leads us to ask how this affects the entanglement in the algorithm. We thus investigate the behaviour of entanglement in Shor's algorithm for small numbers of qubits by classical computer simulation of the quantum computer at different stages of the algorithm. We find that entanglement is an intrinsic part of the algorithm and that the entanglement through the algorithm appears to be closely related to the amount of mixing. Furthermore, if the computer is in a highly mixed state any attempt to remove entanglement by further mixing of the algorithm results in a significant decrease in its efficiency.

arXiv:quant-ph/0102136•Journal of Modern Optics•Jul 1, 2002•33 citations

Shor’s factoring algorithm and modern cryptography. An illustration of the capabilities inherent in quantum computers

E. Gerjuoy

The security of messages encoded via the widely used RSA public key encryption system rests on the enormous computational effort required to find the prime factors of a large number N using classical (conventional) computers. In 1994 Peter Shor showed that for sufficiently large N, a quantum computer could perform the factoring with much less computational effort. This paper endeavors to explain, in a fashion comprehensible to the nonexpert, the RSA encryption protocol; the various quantum computer manipulations constituting the Shor algorithm; how the Shor algorithm performs the factoring; and the precise sense in which a quantum computer employing Shor’s algorithm can be said to accomplish the factoring of very large numbers with less computational effort than a classical computer. It is made apparent that factoring N generally requires many successive runs of the algorithm. Our analysis reveals that the probability of achieving a successful factorization on a single run is about twice as large as commonly quoted in the literature.

arXiv:quant-ph/0411184•American Journal of Physics•May 13, 2005•101 citations

Experimental realisation of Shor's quantum factoring algorithm using qubit recycling

Enrique Martín-López, Anthony Laing, Thomas Lawson +3 more

Quantum algorithms are computational routines that exploit quantum mechanics to solve problems exponentially faster than the best classical algorithms. Shor's quantum factoring algorithm is a key example and the prime motivator in the international effort to realise a quantum computer. However, due to the large number of resources required, to date, there have been only four small scale demonstrations. Here we address this resource demand and demonstrate a scalable version of Shor's algorithm in which then qubit control register is replaced by a single qubit that is recycled n times: the total number of qubits is one third of that required in the standard protocol. Encoding the work register in higher-dimensional states, we implement a two-photon compiled algorithm to factor N = 21. Significantly, the algorithmic output exhibits structure that is distinguishable from noise, in contrast to previous demonstrations.

Conference on Lasers and Electro-Optics Europe & European Quantum Electronics Conference (CLEO/Europe-EQEC)•May 1, 2013•8 citations

Shor’s factorization algorithm with a single control qubit and imperfections

Ignacio García-Mata, Klaus M. Frahm, Dima L. Shepelyansky

We formulate and numerically simulate the single control qubit Shor algorithm for the case of static imperfections induced by residual couplings between qubits. This allows us to study the accuracy of Shor's algorithm with respect to these imperfections using numerical simulations of realistic quantum computations with up to ${n}_{q}=18$ computational qubits allowing to factor numbers up to $N=205\phantom{\rule{0.2em}{0ex}}193$. We confirm that the algorithm remains operational up to a critical coupling strength ${ϵ}_{c}$ which drops only polynomially with ${\mathrm{log}}_{2}\phantom{\rule{0.2em}{0ex}}N$. The obtained numerical dependence of ${ϵ}_{c}$ on ${\mathrm{log}}_{2}\phantom{\rule{0.2em}{0ex}}N$ is in a good agreement with the analytical estimates that allows to obtain the scaling for functionality of Shor's algorithm on realistic quantum computers with a large number of qubits.

arXiv:0809.4416•Physical Review A•Dec 12, 2008•14 citations

Experimental realization of a Shor-type quantum algorithm

Isaac L. Chuang

I will describe our recent implementation of a five-qubit NMR quantum computer capable of executing a quantum algorithm for order-finding. This is the first demonstration of a quantum algorithm with the structure of Shor's algorithm for efficient prime factorization, a key step in the experimental realization of quantum computers because its structure appears to be common to all quantum algorithms that achieve an exponential speed-up over their classical counterparts. The experiment was made possible by the synthesis of a 5-spin molecule with remarkable NMR properties, and by the introduction of new techniques for state initialization and quantum control.

Optical Fiber Communication Conference•Jan 1, 2001•1 citation
It is commonly assumed that the initial state in Shor's quantum algorithm for the efficient factorization of large numbers requires a pure initial state. Here we demonstrate that a single pure qubit together with a collection of qubits in an arbitrary mixed state is sufficient to implement Shor's factorization algorithm efficiently.
We demonstrate that, in the case of Shor's algorithm for factoring, highly mixed states will allow efficient quantum computation, indeed factorization can be achieved efficiently with just one initial pure qubit and a supply of initially maximally mixed qubits (Parker, S. and Plenio, M. B., 2000, Phys. Rev. Lett., 85, 3049). This leads us to ask how this affects the entanglement in the algorithm. We thus investigate the behaviour of entanglement in Shor's algorithm for small numbers of qubits by classical computer simulation of the quantum computer at different stages of the algorithm. We find that entanglement is an intrinsic part of the algorithm and that the entanglement through the algorithm appears to be closely related to the amount of mixing. Furthermore, if the computer is in a highly mixed state any attempt to remove entanglement by further mixing of the algorithm results in a significant decrease in its efficiency.
The security of messages encoded via the widely used RSA public key encryption system rests on the enormous computational effort required to find the prime factors of a large number N using classical (conventional) computers. In 1994 Peter Shor showed that for sufficiently large N, a quantum computer could perform the factoring with much less computational effort. This paper endeavors to explain, in a fashion comprehensible to the nonexpert, the RSA encryption protocol; the various quantum computer manipulations constituting the Shor algorithm; how the Shor algorithm performs the factoring; and the precise sense in which a quantum computer employing Shor’s algorithm can be said to accomplish the factoring of very large numbers with less computational effort than a classical computer. It is made apparent that factoring N generally requires many successive runs of the algorithm. Our analysis reveals that the probability of achieving a successful factorization on a single run is about twice as large as commonly quoted in the literature.
Quantum algorithms are computational routines that exploit quantum mechanics to solve problems exponentially faster than the best classical algorithms. Shor's quantum factoring algorithm is a key example and the prime motivator in the international effort to realise a quantum computer. However, due to the large number of resources required, to date, there have been only four small scale demonstrations. Here we address this resource demand and demonstrate a scalable version of Shor's algorithm in which then qubit control register is replaced by a single qubit that is recycled n times: the total number of qubits is one third of that required in the standard protocol. Encoding the work register in higher-dimensional states, we implement a two-photon compiled algorithm to factor N = 21. Significantly, the algorithmic output exhibits structure that is distinguishable from noise, in contrast to previous demonstrations.
We formulate and numerically simulate the single control qubit Shor algorithm for the case of static imperfections induced by residual couplings between qubits. This allows us to study the accuracy of Shor's algorithm with respect to these imperfections using numerical simulations of realistic quantum computations with up to nq=18{n}_{q}=18nq​=18 computational qubits allowing to factor numbers up to N=205193N=205\phantom{\rule{0.2em}{0ex}}193N=205193. We confirm that the algorithm remains operational up to a critical coupling strength ϵc{ϵ}_{c}ϵc​ which drops only polynomially with log2N{\mathrm{log}}_{2}\phantom{\rule{0.2em}{0ex}}Nlog2​N. The obtained numerical dependence of ϵc{ϵ}_{c}ϵc​ on log2N{\mathrm{log}}_{2}\phantom{\rule{0.2em}{0ex}}Nlog2​N is in a good agreement with the analytical estimates that allows to obtain the scaling for functionality of Shor's algorithm on realistic quantum computers with a large number of qubits.
I will describe our recent implementation of a five-qubit NMR quantum computer capable of executing a quantum algorithm for order-finding. This is the first demonstration of a quantum algorithm with the structure of Shor's algorithm for efficient prime factorization, a key step in the experimental realization of quantum computers because its structure appears to be common to all quantum algorithms that achieve an exponential speed-up over their classical counterparts. The experiment was made possible by the synthesis of a 5-spin molecule with remarkable NMR properties, and by the introduction of new techniques for state initialization and quantum control.