Shor's algorithm

Shor's algorithm is a quantum computer algorithm for integer factorization. Informally, it solves the following problem: Given an integer N {displaystyle N} , find its prime factors. It was invented in 1994 by the American mathematician Peter Shor.where ⊗ {displaystyle otimes } denotes the tensor product. Shor's algorithm is a quantum computer algorithm for integer factorization. Informally, it solves the following problem: Given an integer N {displaystyle N} , find its prime factors. It was invented in 1994 by the American mathematician Peter Shor. On a quantum computer, to factor an integer N {displaystyle N} , Shor's algorithm runs in polynomial time (the time taken is polynomial in log ⁡ N {displaystyle log N} , the size of the integer given as input). Specifically, it takes quantum gates of order O ( ( log ⁡ N ) 2 ( log ⁡ log ⁡ N ) ( log ⁡ log ⁡ log ⁡ N ) ) {displaystyle O!left((log N)^{2}(log log N)(log log log N) ight)} using fast multiplication, 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 almost exponentially faster than the most efficient known classical factoring algorithm, the general number field sieve, which works in sub-exponential time — O ( e 1.9 ( log ⁡ N ) 1 / 3 ( log ⁡ log ⁡ N ) 2 / 3 ) {displaystyle O!left(e^{1.9(log N)^{1/3}(log log N)^{2/3}} ight)} . The efficiency of Shor's algorithm is due to the efficiency of the quantum Fourier transform, and modular exponentiation by repeated squarings. 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 widely-used RSA scheme. 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. In 2001, Shor's algorithm was demonstrated by a group at IBM, who factored 15 {displaystyle 15} into 3 × 5 {displaystyle 3 imes 5} , using an NMR implementation of a quantum computer with 7 {displaystyle 7} qubits. 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. In 2012, the factorization of 15 {displaystyle 15} was performed with solid-state qubits. Also, in 2012, the factorization of 21 {displaystyle 21} was achieved, setting the record for the largest integer factored with Shor's algorithm. In April 2012, the factorization of 143 = 11 × 13 {displaystyle 143=11 imes 13} was achieved, although this used adiabatic quantum computation rather than Shor's algorithm. In November 2014, it was discovered that this 2012 adiabatic quantum computation had also factored larger numbers, the largest being 56153 {displaystyle 56153} . (This number is equal to 233 × 241 {displaystyle 233 imes 241} .) The problem that we are trying to solve is, given an odd composite number N {displaystyle N} , find an integer d {displaystyle d} , strictly between 1 {displaystyle 1} and N {displaystyle N} , that divides N {displaystyle N} . We are interested in odd values of N {displaystyle N} because any even value of N {displaystyle N} trivially has 2 {displaystyle 2} as a prime factor. Also, any N {displaystyle N} with digits that sum to a multiple of 3 is trivially divisible by 3. Any N {displaystyle N} ending on 5 is also divisible by 5. Excluding those trivial cases, we can use a primality-testing algorithm to ensure that N {displaystyle N} is indeed composite. Moreover, for the algorithm to work, we need N {displaystyle N} not to be any power of a prime. This can be tested by checking that N k {displaystyle {sqrt{N}}} is not an integer for any k ≤ log 2 ( N ) {displaystyle kleq {log _{2}}(N)} . Since N {displaystyle N} is not a power of a prime, it is the product of two coprime integers greater than 1 {displaystyle 1} . As a consequence of the Chinese remainder theorem, the number 1 {displaystyle 1} has at least four distinct square roots modulo N {displaystyle N} , two of which are 1 {displaystyle 1} and − 1 {displaystyle -1} . The aim of the algorithm is to find a square root b {displaystyle b} that is different from 1 {displaystyle 1} and − 1 {displaystyle -1} ; such a b {displaystyle b} will lead to a factorization of N {displaystyle N} , as in other factoring algorithms, like the quadratic sieve. In turn, finding such a b {displaystyle b} is reduced to finding an element a {displaystyle a} of even period with a certain additional property (as explained below, it is required that the condition of Step 6 of the classical part does not hold). The quantum algorithm is used for finding the period of randomly chosen elements a {displaystyle a} , as this is a hard problem on a classical computer.