View source for Shor's algorithm

'''Shor's algorithm''' is a [[quantum computer|quantum]] [[algorithm]] for [[Integer factorization|factoring]] a number ''N'' in [[Big O notation |O]]((log ''N'')<sup>3</sup>) time and O(log ''N'') space, named after [[Peter Shor]].

The algorithm is significant because it implies that [[public key cryptography]] might be easily broken, given a sufficiently large quantum computer. [[RSA]], for example, uses a public key ''N'' which is the product of two large prime numbers. One way to crack RSA encryption is by factoring ''N'', but with classical algorithms, factoring becomes increasingly time-consuming as ''N'' grows large; more specifically, no classical algorithm is known that can factor in time O((log ''N'')<sup>''k''</sup>) for any ''k''. By contrast, Shor's algorithm can crack RSA in polynomial time. It has also been extended to attack many other public key cryptosystems.

Like all quantum computer algorithms, Shor's algorithm is probabilistic: it gives the correct answer with high probability, and the probability of failure can be decreased by repeating the algorithm.

Shor's algorithm was demonstrated in 2001 by a group at [[International Business Machines|IBM]], which factored 15 into 3 and 5, using a quantum computer with 7 [[qubit|qubits]].

=== Procedure ===

The problem we are trying to solve is that, given an [[integer]] ''N'', we try to find another integer ''p'' between ''1'' and ''N'' that divides ''N''.

Shor's algorithm consists of two parts:

# A reduction of the factoring problem to the problem of [[Order (group theory)|order-finding]], which can be done on a classical computer.
# A quantum algorithm to solve the order-finding problem.

==== Classical part ====

<ol>
<li>Pick a pseudo-random number ''a'' &lt; ''N''</li>
<li>Compute [[greatest common divisor|gcd]](''a'', ''N''). This may be done using the [[Euclidean algorithm]].</li>
<li>If gcd(''a'', ''N'') &ne; 1, then there is a nontrivial factor of ''N'', so we are done.</li>
<li>Otherwise, use the period-finding subroutine (below) to find ''r'', the [[periodic function|period]] of the following function:

:<math>f(x) = a^x\ \mbox{mod}\ N</math>,
i.e. the smallest integer ''r'' for which
<math>f(x+r) = f(x)</math>.
</li>
<li>If ''r'' is odd, go back to step 1.</li>
<li>If ''a'' <sup>''r''/2</sup> &equiv; -1 (mod ''N''), go back to step 1.</li>
<li>The factors of ''N'' are gcd(a<sup>''r''/2</sup> &plusmn; 1, ''N''). We are done.</li>
</ol>

==== Quantum part: Period-finding subroutine: ====

<ol>
<li>Start with a pair of input and output [[qubit]] registers with log<sub><small>2</small></sub>''N'' qubits each, and initialize them to

:<math>N^{-1/2} \sum_x \left|x\right\rangle \left|0\right\rangle</math>

where ''x'' runs from 0 to ''N'' - 1.</li>

<li>Construct ''f''(''x'') as a quantum function and apply it to the above state, to obtain

:<math>N^{-1/2} \sum_x \left|x\right\rangle \left|f(x)\right\rangle</math>
</li>

<li>Apply the [[quantum Fourier transform]] on the input register. The
quantum Fourier transform on ''N'' points is defined by:

:<math>U_{QFT} \left|x\right\rangle
= N^{-1/2} \sum_y e^{2\pi i x y/N} \left|y\right\rangle</math>

This leaves us in the following state:

:<math> N^{-1} \sum_x \sum_y e^{2\pi i x y/N} \left|y\right\rangle \left|f(x)\right\rangle</math>
</li>

<li>Perform a measurement.
We obtain some outcome ''y'' in the input register and <math>f(x_0)</math> in the output register.
Since ''f'' is periodic, the probability to measure some ''y'' is given by

:<math> N^{-1} \left| \sum_{x:\, f(x)=f(x_0)} e^{2\pi i x y/N} \right|^2
= N^{-1} \left| \sum_{b} e^{2\pi i (x_0 + r b) y/N} \right|^2
</math>

Analysis now shows that this probability is higher, the closer ''yr/N'' is to an integer.</li>

<li>Turn ''y/N'' into an [[irreducible fraction]], and extract the denominator ''r''&prime;, which is a candidate for ''r''.</li>

<li>Check if ''f''(''x'') = ''f''(''x'' + ''r''&prime;). If so, we are done.</li>

<li>Otherwise, obtain more candidates for ''r'' by using values near ''y'', or multiples of ''r''&prime;. If any candidate works, we are done.</li>

<li>Otherwise, go back to step 1 of the subroutine.</li>
</ol>

=== Explanation of the algorithm ===

The algorithm is composed of two parts. The first part of the algorithm turns the factoring problem into the problem of finding the period of a function, and may be implemented classically. The second part finds the period using the quantum Fourier transform, and is responsible for the quantum speedup.

==== I. Obtaining factors from period ====

The integers less than ''N'' and [[coprime]] with ''N'' form a finite [[group (mathematics)|group]] under multiplication [[modular arithmetic|modulo]] ''N'', which is typically denoted ('''Z'''/''N'''''Z''')<sup>&times;</sup>. By the end of step 3, we have an integer ''a'' in this group. Since the group is finite, ''a'' must have a finite order ''r'', the smallest positive integer such that

:<math>a^r \equiv 1\ \mbox{mod}\ N.\,</math>

Therefore, ''N'' | (''a'' <sup>''r''</sup> &minus; 1). Suppose we are able to obtain ''r'', and it is even. Then

:<math>a^r - 1 = (a^{r/2} - 1) (a^{r/2} + 1) \equiv 0\ \mbox{mod}\ N</math>
:<math>\Rightarrow N\ | (a^{r/2} - 1) (a^{r/2} + 1).\,</math>

''r'' is the ''smallest'' positive integer such that ''a'' <sup>''r''</sup> &equiv; 1, so ''N'' cannot divide (''a'' <sup>''r'' / 2</sup> &minus; 1). If ''N'' also does not divide (''a'' <sup>''r'' / 2</sup> + 1), then ''N'' must have a nontrivial common factor with each of (''a'' <sup>''r'' / 2</sup> &minus; 1) and (''a'' <sup>''r'' / 2</sup> + 1).

'''Proof:''' For simplicity, denote (''a'' <sup>''r'' / 2</sup> &minus; 1) and (''a'' <sup>''r'' / 2</sup> + 1) by ''u'' and ''v'' respectively. ''N'' | ''uv'', so ''kN'' = ''uv'' for some integer ''k''. Suppose gcd(''u'', ''N'') = 1; then ''mu'' + ''nN'' = 1 for some integers ''m'' and ''n'' (this is a property of the [[greatest common divisor]].) Multiplying both sides by ''v'', we find that ''mkN'' + ''nvN'' = ''v'', so ''N'' | ''v''. By contradiction, gcd(''u'', ''N'') &ne; 1. By a similar argument, gcd(''v'', ''N'') &ne; 1.

This supplies us with a factorization of ''N''. If ''N'' is the product of two primes, this is the ''only'' possible factorization.

==== II. Finding the period ====

Shor's period-finding algorithm relies heavily on the ability of a [[quantum computer]] to be in many states simultaneously.
Physicists call this behaviour a "[[Quantum superposition|superposition]]" of states.  To compute the period of a function ''f'', we evaluate the function at all points simultaneously.

Quantum physics does not allow us to access all this information directly, though. A [[measurement in quantum mechanics|measurement]] will yield only one of all possible values, destroying all others.
Therefore we have to carefully transform the superposition to another state that will return the correct answer with high probability.
This is achieved by the [[quantum Fourier transform]].

Shor thus had to solve three "implementation" problems.
All of them had to be implemented "fast", which means that they can be implemented with a number of [[quantum gate]]s that is [[polynomial#Complexity|polynomial]] in <math>\log N</math>.

<ol>
<li> Create a superposition of states.

This can be done by applying [[Hadamard transform|Hadamard]] gates to all qubits in the input register.
Another approach would be to use the quantum Fourier transform (see below).

<li> Implement the function ''f'' as a quantum transform.

To achieve this, Shor used [[Exponentiating by squaring|repeated squaring]] for his modular exponentiation transformation.

<li> Perform a quantum Fourier transform.

By using controlled NOT gates and single qubit rotation gates Shor designed a circuit for the quantum Fourier transform that uses just <math>O((\log N)^2)</math> gates.
</ol>

After all these transformations a measurement will yield an approximation to the period ''r''.
For simplicity assume that there is a ''y'' such that ''yr/N'' is an integer.
Then the probability to measure ''y'' is 1.
To see that we notice that then
:<math>e^{2 \pi i b yr/N} = 1</math>
for all integers ''b''.
Therefore the sum that gives us the probability to measure ''y'' will be ''N/r'' since ''b'' takes roughly ''N/r'' values and thus the probability is ''1/r''.
There are ''r'' ''y'' such that ''yr/N'' is an integer, so the probabilities sum to 1.

Note: another way to explain Shor's algorithm is by noting that it is just the [[quantum phase estimation algorithm]] in disguise.

=== Modifications to Shor's Algorithm ===
There have been many modifications to Shor's algorithm. For example, whereas, an order of twenty to thirty runs are required on a quantum computer in the case of Shor's original algorithm, and with some of the other modifications, in the case of the modification done by David McAnally at the [[University of Queensland]] an order of only four to eight runs on the quantum computer is required. 

=== References ===

Preprint of the original paper by Peter Shor:

* [http://www.arxiv.org/abs/quant-ph/9508027 ''Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer'', Peter W. Shor]

A general textbook on quantum computing:

* ''Quantum Computation and Quantum Information'', Michael A. Nielsen, Isaac L. Chuang, Cambridge University Press, 2000

[[Category:Quantum algorithms]]
[[Category:Integer factorization algorithms]]

[[de:Shor-Algorithmus]]
[[es:Algoritmo de Shor]]
[[fr:Algorithme de Shor]]
[[ko:%EC%87%BC%EC%96%B4_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98]]
[[pl:Algorytm faktoryzacji Shora]]