Shor's algorithm is a quantum algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor.^[1][2] It is one of the few known quantum algorithms with compelling potential applications and strong evidence of superpolynomial speedup compared to best known classical (non-quantum) algorithms.^[3] On the other hand, factoring numbers of practical significance requires far more qubits than available in the near future.^[4] Another concern is that noise in quantum circuits may undermine results,^[5] requiring additional qubits for quantum error correction.

Shor proposed multiple similar algorithms for solving the factoring problem, the discrete logarithm problem, and the period-finding problem. "Shor's algorithm" usually refers to the factoring algorithm, but may refer to any of the three algorithms. The discrete logarithm algorithm and the factoring algorithm are instances of the period-finding algorithm, and all three are instances of the hidden subgroup problem.

On a quantum computer, to factor an integer ${\displaystyle N}$, Shor's algorithm runs in polynomial time, meaning the time taken is polynomial in ${\displaystyle \log N}$, the size of the integer given as input.^[6] Specifically, it takes quantum gates of order ${\displaystyle O\!\left((\log N)^{2}(\log \log N)(\log \log \log N)\right)}$ using fast multiplication,^[7] or even ${\displaystyle O\!\left((\log N)^{2}(\log \log N)\right)}$ 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: ${\displaystyle O\!\left(e^{1.9(\log N)^{1/3}(\log \log N)^{2/3}}\right)}$.^[9]

Feasibility and impact

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

• The RSA scheme
• The Finite Field Diffie-Hellman key exchange
• The Elliptic Curve Diffie-Hellman key exchange^[10]

RSA is based on the assumption that factoring large integers is computationally intractable. As far as is known, this assumption is valid for classical (non-quantum) computers; no classical algorithm is known that can factor integers in polynomial time. 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.

Physical implementation

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.

In 2001, Shor's algorithm was demonstrated by a group at IBM, who factored ${\displaystyle 15}$ into ${\displaystyle 3\times 5}$, using an NMR implementation of a quantum computer with seven qubits.^[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.^[12][13] In 2012, the factorization of ${\displaystyle 15}$ was performed with solid-state qubits.^[14] Later, in 2012, the factorization of ${\displaystyle 21}$ was achieved.^[15] In 2019, an attempt was made to factor the number ${\displaystyle 35}$ using Shor's algorithm on an IBM Q System One, but the algorithm failed because of accumulating errors.^[16] However, due to the lack of number of qubits, all these demonstrations were compiled version, which is based on the prior knowledge of the answer.^[17] Though larger numbers have been factored by quantum computers using other algorithms,^[18] these algorithms are similar to classical brute-force checking of factors, so unlike Shor's algorithm, they are not expected to ever perform better than classical factoring algorithms.^[19]

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.^[5] These primes ${\displaystyle p}$ have the property that ${\displaystyle p-1}$ has a prime factor larger than ${\displaystyle p^{2/3}}$, and have a positive density in the set of all primes. Hence error-correction will be needed to be able to factor all numbers with Shor's algorithm.

Algorithm

The problem that we are trying to solve is: given an odd composite number ${\displaystyle N}$, find its integer factors.

To achieve this, Shor's algorithm consists of two parts:

1. A classical reduction of the factoring problem to the problem of order-finding. This reduction is similar to that used for other factoring algorithms, such as the quadratic sieve.
2. A quantum algorithm to solve the order-finding problem.

Classical reduction

A complete factoring algorithm is possible if we're able to efficiently factor arbitrary ${\displaystyle N}$ into just two integers ${\displaystyle p}$ and ${\displaystyle q}$ greater than 1, since if either ${\displaystyle p}$ or ${\displaystyle q}$ are not prime then the factoring algorithm can in turn be run on those until only primes remain.

A basic observation is that, using Euclid's algorithm, we can always compute the GCD between two integers efficiently. In particular, this means we can check efficiently whether ${\displaystyle N}$ is even, in which case 2 is trivially a factor. Let us thus assume that ${\displaystyle N}$ is odd for the remainder of this discussion. Afterwards, we can use efficient classical algorithms to check if ${\displaystyle N}$ is a prime power.^[20] For prime powers, efficient classical factorization algorithms exist,^[21] hence the rest of the quantum algorithm may assume that ${\displaystyle N}$ is not a prime power.

If those easy cases do not produce a nontrivial factor of ${\displaystyle N}$, the algorithm proceeds to handle the remaining case. We pick a random integer ${\displaystyle 2\leq a<N}$. A possible nontrivial divisor of ${\displaystyle N}$ can be found by computing ${\displaystyle \gcd(a,N)}$, which can be done classically and efficiently using the Euclidean algorithm. If this produces a nontrivial factor (meaning ${\displaystyle \gcd(a,N)\neq 1}$), the algorithm is finished, and the other nontrivial factor is ${\textstyle {\frac {N}{\gcd(a,N)}}}$. If a nontrivial factor was not identified, then that means that ${\displaystyle N}$ and the choice of ${\displaystyle a}$ are coprime, so ${\displaystyle a}$ is contained in the multiplicative group of integers modulo ${\displaystyle N}$, having a multiplicative inverse modulo ${\displaystyle N}$. Thus, ${\displaystyle a}$ has a multiplicative order ${\displaystyle r}$ modulo ${\displaystyle N}$, meaning

${\displaystyle a^{r}\equiv 1{\bmod {N}}}$

and ${\displaystyle r}$ is the smallest positive integer satisfying this congruence.

The quantum subroutine finds ${\displaystyle r}$. It can be seen from the congruence that ${\displaystyle N}$ divides ${\displaystyle a^{r}-1}$, written ${\displaystyle N\mid a^{r}-1}$. This can be factored using difference of squares:

Since we have factored the expression in this way, the algorithm doesn't work for odd ${\displaystyle r}$ (because ${\displaystyle a^{r/2}}$ must be an integer), meaning the algorithm would have to restart with a new ${\displaystyle a}$. Hereafter we can therefore assume ${\displaystyle r}$ is even. It cannot be the case that ${\displaystyle N\mid a^{r/2}-1}$, since this would imply ${\displaystyle a^{r/2}\equiv 1{\bmod {N}}}$, which would contradictorily imply that ${\textstyle {\frac {r}{2}}}$ would be the order of ${\displaystyle a}$, which was already $$Zdroj:https://en.wikipedia.org?pojem=Shor's_algorithm
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.

---