Shor's algorithm
[3] On the other hand, factoring numbers of practical significance requires far more qubits than available in the near future.
utilizing the asymptotically fastest multiplication algorithm currently known due to Harvey and Van Der Hoven,[8] thus demonstrating that the integer factorization problem can be efficiently solved on a quantum computer and is consequently in the complexity class BQP.
This is significantly faster than the most efficient known classical factoring algorithm, the general number field sieve, which works in sub-exponential time:
[9] If a quantum computer with a sufficient number of qubits could operate without succumbing to quantum noise and other quantum-decoherence phenomena, then Shor's algorithm could be used to break public-key cryptography schemes, such as RSA can be broken if factoring large integers is computationally feasible.
However, Shor's algorithm shows that factoring integers is efficient on an ideal quantum computer, so it may be feasible to defeat RSA by constructing a large quantum computer.
It was also a powerful motivator for the design and construction of quantum computers, and for the study of new quantum-computer algorithms.
It has also facilitated research on new cryptosystems that are secure from quantum computers, collectively called post-quantum cryptography.
Given the high error rates of contemporary quantum computers and too few qubits to use quantum error correction, laboratory demonstrations obtain correct results only in a fraction of attempts.
[11] After IBM's implementation, two independent groups implemented Shor's algorithm using photonic qubits, emphasizing that multi-qubit entanglement was observed when running the Shor's algorithm circuits.
[20] Theoretical analyses of Shor's algorithm assume a quantum computer free of noise and errors.
However, near-term practical implementations will have to deal with such undesired phenomena (when more qubits are available, quantum error correction can help).
In 2023, Jin-Yi Cai showed that in the presence of noise, Shor's algorithm fails asymptotically almost surely for large semiprimes that are products of two primes in OEIS sequence A073024.
Hence error correction will be needed to be able to factor all numbers with Shor's algorithm.
A basic observation is that, using Euclid's algorithm, we can always compute the GCD between two integers efficiently.
[2] In practice, a single call to the quantum order-finding subroutine is enough to completely factor
[23] The goal of the quantum subroutine of Shor's algorithm is, given coprime integers
To achieve this, Shor's algorithm uses a quantum circuit involving two registers.
The size of the first register determines how accurate of an approximation the circuit produces.
The algorithm consists of two main steps: The connection with quantum phase estimation was not discussed in the original formulation of Shor's algorithm,[2] but was later proposed by Kitaev.
For the purposes of quantum order-finding, we employ this strategy using the unitary defined by the action
is not crucial to the functioning of the algorithm, but needs to be included to ensure that the overall transformation is a well-defined quantum gate.
This can be accomplished via modular exponentiation, which is the slowest part of the algorithm.
This probability can be made arbitrarily close to 1 using extra qubits.
was measured[2] (which can be made arbitrarily likely by using extra bits and truncating the output).
This can be remedied by rerunning the quantum order-finding subroutine an arbitrary number of times, to produce a list of fraction approximations
In practice, a single run of the quantum order-finding subroutine is in general enough if more advanced post-processing is used.
qubits is sufficient to guarantee that the optimal bitstring measured from phase estimation (meaning the
before measurement in Shor's algorithm represents a superposition of integers approximating
The simplest and (currently) most practical approach is to mimic conventional arithmetic circuits with reversible gates, starting with ripple-carry adders.
Alternative techniques asymptotically improve gate counts by using quantum Fourier transforms, but are not competitive with fewer than 600 qubits owing to high constants.
