en>Rjwilmsi: Journal cites, added 1 DOI using AWB (9904)

2014-02-03T19:48:15Z

Journal cites, added 1 DOI using AWB (9904)

New page

'''Shor's algorithm''', named after mathematician [[Peter Shor]], is a [[quantum algorithm]] (an [[algorithm]] which runs on a [[quantum computer]]) for [[integer factorization]] formulated in 1994. Informally it solves the following problem: Given an integer ''N'', find its [[prime factor]]s.

On a quantum computer, to factor an integer ''N'', Shor's algorithm runs in [[polynomial time]] (the time taken is polynomial in log ''N'', which is the size of the input).<ref>See also [[Pseudo-polynomial time]].</ref> Specifically it takes time {{math|[[Big O notation|O]]((log ''N'')3)}}, demonstrating that the integer factorization problem can be efficiently solved on a quantum computer and is thus in the [[complexity class]] '''[[BQP]]'''. This is substantially faster than the most efficient known classical factoring algorithm, the [[general number field sieve]], which works in [[sub-exponential time]] — about {{math|O(e1.9 (log N)1/3 (log log N)2/3)}}.<ref>[http://mathworld.wolfram.com/NumberFieldSieve.html MathWorld: Number Field Sieve]</ref> The efficiency of Shor's algorithm is due to the efficiency of the [[quantum Fourier transform]], and [[modular exponentiation]] by [[exponentiation by squaring|squarings]].

If a quantum computer with a sufficient number of [[qubits]] could operate without succumbing to [[noise]] and other quantum interference phenomena, Shor's algorithm could be used to break [[public-key cryptography]] schemes such as the widely used [[RSA (algorithm)|RSA]] scheme. RSA is based on the assumption that factoring large numbers is computationally infeasible. So far as is known, this assumption is valid for classical (non-quantum) computers; no classical algorithm is known that can factor in polynomial time. However, Shor's algorithm shows that factoring 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 into 3 × 5, using an [[Nuclear magnetic resonance (NMR) quantum computing|NMR implementation]] of a quantum computer with 7 [[qubits]].<ref name="VSBYSC01">{{Citation |last=Vandersypen |first=Lieven M. K. |last2=Steffen |first2=Matthias |last3=Breyta |first3=Gregory |last4=Yannoni |first4=Costantino S. |last5=Sherwood |first5=Mark H. |last6=Chuang |first6=Isaac L. |lastauthoramp=yes |year=2001 |title=Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance |journal=[[Nature (journal)|Nature]] |volume=414 |issue=6866 |pages=883–887 |doi=10.1038/414883a |pmid=11780055 |arxiv = quant-ph/0112176 |bibcode = 2001Natur.414..883V |url=http://cryptome.org/shor-nature.pdf |format=PDF}}</ref>
However, some doubts have been raised as to whether IBM's experiment was a true demonstration of quantum computation, since no [[quantum entanglement|entanglement]] was observed.<ref name="BCJLPS99">{{Citation |last=Braunstein |first=S. L. |last2=Caves |first2=C. M. |last3=Jozsa |first3=R. |last4=Linden |first4=N. |last5=Popescu |first5=S. |last6=Schack |first6=R. |lastauthoramp= |year=1999 |title=Separability of Very Noisy Mixed States and Implications for NMR Quantum Computing |journal=Phys. Rev. Lett |volume=83 |issue=5 |pages=1054–1057 |doi=10.1103/PhysRevLett.83.1054 |bibcode=1999PhRvL..83.1054B|arxiv = quant-ph/9811018 }}</ref>
Since IBM's implementation, several other groups have implemented Shor's algorithm using photonic qubits, emphasizing that entanglement was observed.<ref name="LBYP07">{{Citation |last=Lu |first=Chao-Yang |last2=Browne |first2=Daniel E. |last3=Yang |first3=Tao |last4=Pan |lastauthoramp=yes |year=2007 |title=Demonstration of a Compiled Version of Shor's Quantum Factoring Algorithm Using Photonic Qubits |journal=[[Physical Review Letters]] |volume=99 |issue=25 |page=250504 |doi=10.1103/PhysRevLett.99.250504 |first4=Jian-Wei |bibcode=2007PhRvL..99y0504L|arxiv = 0705.1684 }}</ref><ref name="LWLBJGW07">{{Citation |last=Lanyon |first=B. P. |last2=Weinhold |first2=T. J. |last3=Langford |first3=N. K. |last4=Barbieri |first4=M. |last5=James |first5=D. F. V. |last6=Gilchrist |first6=A. |last7=White |first7=A. G. |lastauthoramp=yes |year=2007 |title=Experimental Demonstration of a Compiled Version of Shor's Algorithm with Quantum Entanglement |journal=Physical Review Letters |volume=99 |issue=25 |page=250505 |doi=10.1103/PhysRevLett.99.250505 |bibcode=2007PhRvL..99y0505L|arxiv = 0705.1398 }}</ref> In 2012, the factorization of 15 was repeated.<ref>http://arxiv.org/pdf/1202.5707v1.pdf - Computing prime factors with a Josephson phase qubit quantum processor</ref> Also in 2012, the factorization of 21 was achieved, setting the record for the largest number factored with a quantum computer.<ref>{{cite journal|last=Martín-López|first=Enrique|coauthors=Enrique Martín-López, Anthony Laing, Thomas Lawson, Roberto Alvarez, Xiao-Qi Zhou & Jeremy L. O'Brien|title=Experimental realization of Shor's quantum factoring algorithm using qubit recycling|journal=Nature Photonics|date=12 October 2012|url=http://www.nature.com/nphoton/journal/vaop/ncurrent/full/nphoton.2012.259.html|accessdate=October 23, 2012}}</ref> In April 2012, the factorization of 143 was achieved. [http://phys.org/news/2012-04-largest-factored-quantum-algorithm.html]

== Procedure ==
The problem we are trying to solve is: given an odd [[composite number]] <math>N</math>, find an integer <math>d</math>, strictly between <math>1</math> and <math>N</math>, that divides <math>N</math>. We are interested in odd values of <math>N</math> because any even value of <math>N</math> trivially has the number <math>2</math> as a prime factor. We can use a [[primality testing]] algorithm to make sure that <math>N</math> is indeed composite.

Moreover, for the algorithm to work, we need <math>N</math> not to be the power of a prime. This can be tested by taking square, cubic, ..., <math>k</math>-roots of <math>N</math>, for <math>k \le \log_{2}(N)</math>, and checking that none of these is an integer. (This actually excludes that <math>N = M^{k}</math> for some integer <math>M</math> and <math>k > 1</math>.)

Since <math>N</math> is not a power of a prime, it is the product of two [[coprime]] numbers greater than <math>1</math>. As a consequence of the [[Chinese remainder theorem]], the number <math>1</math> has at least four distinct roots [[modular arithmetic|modulo]] <math>N</math>, two of them being <math>1</math> and <math>-1</math>. The aim of the algorithm is to find a square root <math>b</math> of one, other than <math>1</math> and <math>-1</math>; such a <math>b</math> will lead to a factorization of <math>N</math>, as in other [[integer factorization|factoring algorithms]] like the [[quadratic sieve]].

In turn, finding such a <math>b</math> is reduced to finding an element <math>a</math> 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 <math>a</math>, as order-finding is a hard problem on a classical computer.

Shor's algorithm consists of two parts:

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

=== Classical part ===
{{ordered list
| Pick a random number ''a'' < ''N''.
| Compute [[greatest common divisor|gcd]](''a'', ''N''). This may be done using the [[Euclidean algorithm]].
| If gcd(''a'', ''N'') ≠ 1, then there is a [[nontrivial]] factor of ''N'', so we are done.
| Otherwise, use the period-finding subroutine (below) to find ''r'', the [[periodic function|period]] of the following function:
:<math>f(x) = a^x \bmod N,</math>
i.e. the [[order (group theory)|order]] <math>r</math> of <math>a</math> in [[Multiplicative group of integers modulo n|<math>(\mathbb{Z}_N)^\times</math>]], which is the smallest positive integer ''r'' for which <math>f(x+r) = f(x)</math>, or <math>f(x+r) = a^{x+r} \bmod N = a^x \bmod N.</math>
| If ''r'' is odd, go back to step 1.
| If ''a'' ''r'' /2 ≡ −1 ([[Modular arithmetic|mod]] ''N''), go back to step 1.
| gcd(a''r''/2 ± 1, ''N'') is a nontrivial factor of ''N''. We are done.
}}

For example: <math>N = 15, a = 2, r = 4</math>, gcd(4 ± 1, ''N'').

=== Quantum part: Period-finding subroutine ===
The quantum circuits used for this algorithm are custom designed for each choice of ''N'' and the random ''a'' used in ''f''(''x'') = ''a''''x'' [[Modulo operation|mod]] ''N''. Given ''N'', find ''Q'' = 2''q'' such that <math>N^2 \le Q < 2N^2</math>, which implies <math>Q/r > N</math>. The input and output [[qubit]] registers need to hold superpositions of values from 0 to ''Q'' − 1, and so have ''q'' qubits each. Using what might appear to be twice as many qubits as necessary guarantees that there are at least ''N'' different ''x'' which produce the same ''f''(''x''), even as the period ''r'' approaches ''N''/2.

Proceed as follows:

<ol>
<li>Initialize the registers to

:<math>Q^{-1/2} \sum_{x=0}^{Q-1} \left|x\right\rangle \left|0\right\rangle</math>

where ''x'' runs from 0 to ''Q'' − 1. This initial state is a superposition of ''Q'' states.</li>

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

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

This is still a superposition of ''Q'' states.
</li>

<li>Apply the [[quantum Fourier transform]] to the input register. This transform (operating on a superposition of power-of-two ''Q'' = 2''q'' states)
uses a ''Q''th [[root of unity]] [[Imaginary unit#i and −i|such as]] <math>\omega = e^{2 \pi i /Q}</math> to distribute the amplitude of any given <math>\left|x\right\rangle</math> state equally among all ''Q'' of the <math>\left|y\right\rangle</math> states, and to do so in a different way for each different ''x''.
* Let ''y'' be one of the ''r'' possible integers modulo ''N'' such that ''yr/Q'' is an integer; then

:<math>U_{QFT} \left|x\right\rangle
= Q^{-1/2} \sum_y \omega^{x y} \left|y\right\rangle.</math>

This leads to the final state
:<math> Q^{-1} \sum_x \sum_y \omega^{x y} \left|y\right\rangle \left|f(x)\right\rangle.</math>

This is a superposition of many more than ''Q'' states, but many fewer than ''Q''2 states. Although there are ''Q''2 terms in the sum, the state <math>\left|y\right\rangle \left|f(x_0)\right\rangle</math> can be factored out whenever ''x''0 and ''x'' produce the same value. Let
* <math>\omega = e^{2 \pi i /Q}</math> be a ''Q''th root of unity,
* ''r'' be the period of ''f'',
* ''x''0 be the smallest of a set of ''x'' which yield the same given ''f''(''x'') (we have ''x''0 < ''r''), and
* ''b'' run from 0 to <math>\lfloor(Q-x_0-1)/r\rfloor</math> so that <math>x_0 + rb < Q.</math>
Then <math>\omega^{ry}</math> is a unit vector in the complex plane (<math>\omega</math> is a root of unity and ''r'' and ''y'' are integers), and the coefficient of <math>Q^{-1}\left|y\right\rangle \left|f(x_0)\right\rangle</math> in the final state is
:<math> \sum_{x:\, f(x)=f(x_0)} \omega^{x y} = \sum_{b} \omega^{(x_0 + r b) y} = \omega^{x_0y} \sum_{b} \omega^{r b y}.</math>
Each term in this sum represents a ''different path to the same result'', and quantum [[Interference (wave propagation)|interference]] occurs—constructive when the unit vectors <math>\omega^{ryb}</math> point in nearly the same direction in the complex plane, which requires that <math>\omega^{ry}</math> point along the positive real axis.
</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 of measuring some pair ''y'' and <math>f(x_0)</math> is given by

:<math> \left| Q^{-1} \sum_{x:\, f(x)=f(x_0)} \omega^{x y} \right|^2
= Q^{-2} \left| \sum_{b} \omega^{(x_0 + r b) y} \right|^2 = Q^{-2} \left| \sum_{b} \omega^{ b r y} \right|^2.
</math>

Analysis now shows that this probability is higher the closer the unit vector <math>\omega^{ry}</math> is to the positive real axis, or the closer ''yr/Q'' is to an integer. Unless r is a power of 2, it won't be a factor of Q.</li>

<li>Perform [[Continued fraction|continued fraction expansion]] on ''y/Q'' to make an approximation of it, and produce some ''c/r''′ by it that satisfies two conditions:
* A: r′<N
* B: |y/Q - c/r′| < 1/2Q.
By satisfaction of these conditions, ''r''′ would be the appropriate period ''r'' with high probability.</li>

<li>Check if ''f''(''x'') = ''f''(''x'' + ''r''′) <math>\Leftrightarrow</math> <math>a^r \equiv 1 \pmod{N}</math> If so, we are done.</li>

<li>Otherwise, obtain more candidates for ''r'' by using values near ''y'', or multiples of ''r''′. 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.

=== Obtaining factors from period ===
The integers less than ''N'' and [[coprime]] with ''N'' form a finite Abelian [[group (mathematics)|group]] <math>G</math> under multiplication [[modular arithmetic|modulo]] ''N''. The size is given by [[Euler's totient function]] <math>\phi(N)</math>.
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'' [[divides]] (also written | ) ''a'' ''r'' − 1 . Suppose we are able to obtain ''r'', and it is even. (If ''r'' is odd, see step 5.) Now <math>b \equiv a^{r/2} \pmod{N}</math> is a square root of 1 modulo <math>N</math>, different from 1. This is because <math>r</math> is the order of <math>a</math> modulo <math>N</math>, so <math>a^{r/2} \not\equiv 1 \pmod{N}</math>, else the order of <math>a</math> in this group would be <math>r/2</math>. If <math>a^{r/2} \equiv -1 \pmod{N}</math>, by step 6 we have to restart the algorithm with a different random number <math>a</math>.

Eventually, we must hit an <math>a</math>, of order <math>r</math> in <math>G</math>, such that <math>b \equiv a^{r/2} \not\equiv 1, -1 \pmod{N}</math>. This is because such a <math>b</math> is a square root of 1 modulo <math>N</math>, other than 1 and <math>-1</math>, whose existence is guaranteed by the Chinese remainder theorem, since <math>N</math> is not a prime power.

We claim that <math>d = \operatorname{gcd}(b-1, N)</math> is a proper factor of <math>N</math>, that is, <math>d \ne 1, N</math>. In fact if <math>d = N</math>, then <math>N</math> divides <math>b - 1</math>, so that <math>b \equiv 1 \pmod{N}</math>, against the construction of <math>b</math>. If on the other hand <math>d = \operatorname{gcd}(b-1, N) = 1</math>, then by [[Bézout's identity]] there are integers <math>u, v</math> such that
:<math>(b-1) u + N v = 1</math>.
Multiplying both sides by <math>b+1</math> we obtain
:<math>(b^{2}-1) u + N(b+1) v = b+1</math>.
Since <math>N</math> divides <math>b^{2} - 1 \equiv a^{r} - 1 \pmod{N}</math>, we obtain that <math>N</math> divides <math>b+1</math>, so that <math>b \equiv -1 \pmod{N}</math>, again contradicting the construction of <math>b</math>.

Thus <math>d</math> is the required proper factor of <math>N</math>.

=== 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 behavior 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. If not for the [[no cloning theorem]], we could first measure ''f''(''x'') without measuring ''x'', and then make a few copies of the resulting state (which is a superposition of states all having the same ''f''(''x'')). Measuring ''x'' on these states would provide different ''x'' values which give the same ''f''(''x''), leading to the period. Because we cannot [[Quantum cloning|make exact copies of a quantum state]], this method does not work. 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. It is important to note that this step is more difficult to implement than the quantum Fourier transform, in that it requires ancillary qubits and substantially more gates to accomplish.

<li> Perform a quantum Fourier transform.

By using controlled rotation gates and Hadamard gates, Shor designed a circuit for the quantum Fourier transform (with ''Q'' = 2''q'') that uses just <math>q(q-1)/2 = O((\log Q)^2)</math> gates.<ref>{{Harvnb|Shor|1999|p=14}}.</ref>
</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/Q'' 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/Q} = 1\,</math>
for all integers ''b''. Therefore the sum whose square gives us the probability to measure ''y'' will be ''Q/r'' since ''b'' takes roughly ''Q/r'' values and thus the probability is <math>1/r^2</math>. There are ''r'' ''y'' such that ''yr/Q'' is an integer and also ''r'' possibilities for <math>f(x_0)</math>, 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.

=== The bottleneck ===
The runtime bottleneck of Shor's algorithm is quantum [[modular exponentiation]], which is by far slower than the [[quantum Fourier transform]] and classical pre-/post-processing. There are several approaches to constructing and optimizing circuits for modular exponentiation. The simplest and (currently) most practical approach is to mimic conventional arithmetic circuits with [[reversible computing|reversible gates]], starting with ripple-carry adders. Knowing the base and the modulus of exponentiation facilitates further optimizations.<ref>{{cite journal |first=Igor L. |last=Markov |first2=Mehdi |last2=Saeedi |title=Constant-Optimized Quantum Circuits for Modular Multiplication and Exponentiation |journal=Quantum Information and Computation |volume=12 |issue=5–6 |pages=361–394 |year=2012 |arxiv=1202.6614 |bibcode = 2012arXiv1202.6614M }}</ref><ref>{{cite journal |first=Igor L. |last=Markov |first2=Mehdi |last2=Saeedi |title=Faster Quantum Number Factoring via Circuit Synthesis |journal=Phys. Rev. A |volume=87 |issue= |pages=012310 |year=2013 |arxiv=1301.3210 |bibcode = 2013PhRvA..87a2310M |doi = 10.1103/PhysRevA.87.012310 }}</ref> Reversible circuits typically use on the order of <math>n^3</math> gates for <math>n</math> qubits. Alternative techniques asymptotically improve gate counts by using [[quantum Fourier transform]]s, but are not competitive with less than 600 qubits due to high constants.

== Discrete logarithms ==
Given prime <math>p</math> with generator <math>g</math> where <math>1 < g <p-1</math>, suppose we know that <math>x = g^r \pmod{p}</math>, for some ''r'', and we wish to compute ''r'', which is the [[discrete logarithm]]: <math>r = \log_g x \pmod{p}</math>. Consider the Abelian group <math>\left( \mathbb{Z}_{p} \right)^\times \times \left(\mathbb{Z}_p\right)^\times</math> where each factor corresponds to modular multiplication of nonzero values, assuming p is prime. Now, consider the function

:<math>f(a,b) = g^a x^{-b} \pmod{p}.</math>

This gives us an Abelian [[hidden subgroup problem]], as ''f'' corresponds to a [[group homomorphism]]. The kernel corresponds to modular multiples of (''r'',1). So, if we can find the kernel, we can find ''r''.

== In popular culture ==
On the television show ''[[Stargate Universe]]'', the lead scientist, Dr. [[Nicholas Rush]], hoped to use Shor's algorithm to crack ''Destiny'''s master code. He taught a [[quantum cryptography]] class at the [[University of California, Berkeley]], in which Shor's algorithm was studied.

Shor's algorithm was also a correct answer to a question in a Physics Bowl competition in the episode "[[The Bat Jar Conjecture]]" of the TV series ''[[The Big Bang Theory]]''.

== References ==
{{reflist}}

== Further reading ==
{{more footnotes|date=September 2010}}
*{{citation |last=Nielsen |first=Michael A. |last2=Chuang |first2=Isaac L. |lastauthoramp=yes |title=Quantum Computation and Quantum Information |year=2000 |publisher=Cambridge University Press |location= |isbn= |pages= |url= }}.
* Phillip Kaye, Raymond Laflamme, Michele Mosca, ''An introduction to quantum computing'', Oxford University Press, 2007, ISBN 0-19-857049-X
* [http://scottaaronson.com/blog/?p=208 "Explanation for the man in the street"] by [[Scott Aaronson]], "[http://scottaaronson.com/blog/?p=208#comment-9958 approved]" by Peter Shor. (Shor wrote "Great article, Scott! That’s the best job of explaining quantum computing to the man on the street that I’ve seen."). An alternate metaphor for the QFT was presented in [http://www.scottaaronson.com/blog/?p=208#comment-5187 one of the comments]. Scott Aaronson suggests the following 12 references as further reading (out of "the 10105000 quantum algorithm tutorials that are already on the web."):
*{{Citation |last=Shor |first=Peter W. |year=1997 |title=Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer |journal=SIAM J. Comput. |volume=26 |issue=5 |pages=1484–1509 |id= |doi=10.1137/S0036144598347011 |arxiv=quant-ph/9508027v2|bibcode = 1999SIAMR..41..303S }}. Revised version of the original paper by Peter Shor ("28 pages, LaTeX. This is an expanded version of a paper that appeared in the Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, Nov. 20--22, 1994. Minor revisions made January, 1996").
*[http://alumni.imsa.edu/~matth/quant/299/paper/index.html Quantum Computing and Shor's Algorithm], Matthew Hayward, 2005-02-17, imsa.edu, LaTeX2HTML version of the original [http://alumni.imsa.edu/~matth/quant/299/paper.tex 2750 line LaTeX document], also available as a 61 page [http://alumni.imsa.edu/~matth/quant/299/paper.pdf PDF] or [http://alumni.imsa.edu/~matth/quant/299/paper.ps postscript] document.
*[http://homepages.cwi.nl/~rdewolf/publ/qc/survey.ps Quantum Computation and Shor's Factoring Algorithm], Ronald de Wolf, CWI and University of Amsterdam, January 12, 1999, 9 page postscript document.
*[http://www.cs.berkeley.edu/~vazirani/f04quantum/notes/lec9.ps Shor's Factoring Algorithm], Notes from Lecture 9 of Berkeley CS 294-2, dated 4 Oct 2004, 7 page postscript document.
*[http://www.theory.caltech.edu/people/preskill/ph229/notes/chap6.ps Chapter 6 Quantum Computation], 91 page postscript document, Caltech, Preskill, PH229.
*[http://www-users.cs.york.ac.uk/~schmuel/comp/comp.html Quantum computation: a tutorial] by [http://www.cs.york.ac.uk/~schmuel/ Samuel L. Braunstein].
*[http://www.cs.ucr.edu/~neal/1996/cosc185-S96/shor/high-level.html The Quantum States of Shor's Algorithm], by Neal Young, Last modified: Tue May 21 11:47:38 1996.
*[http://web.archive.org/web/20121115112940/http://people.ccmr.cornell.edu/~mermin/qcomp/chap3.pdf III. Breaking RSA Encryption with a Quantum Computer: Shor's Factoring Algorithm], Lecture notes on Quantum computation, Cornell University, Physics 481-681, CS 483; Spring, 2006 by N. David Mermin. Last revised 2006-03-28, 30 page PDF document.
*[http://www.arxiv.org/abs/quant-ph/0303175 arXiv quant-ph/0303175 Shor's Algorithm for Factoring Large Integers. C. Lavor, L.R.U. Manssur, R. Portugal]. Submitted on 29 Mar 2003. This work is a tutorial on Shor's factoring algorithm by means of a worked out example. Some basic concepts of Quantum Mechanics and quantum circuits are reviewed. It is intended for non-specialists which have basic knowledge on undergraduate Linear Algebra. 25 pages, 14 figures, introductory review.
*[http://www.arxiv.org/abs/quant-ph/0010034 arXiv quant-ph/0010034 Shor's Quantum Factoring Algorithm, Samuel J. Lomonaco, Jr], Submitted October 9, 2000, This paper is a written version of a one hour lecture given on Peter Shor's quantum factoring algorithm. 22 pages.
*[http://www.cs.princeton.edu/theory/complexity/quantumchap.pdf Chapter 20 Quantum Computation], from ''Computational Complexity: A Modern Approach'', Draft of a book: Dated January 2007, Comments welcome!, Sanjeev Arora and Boaz Barak, Princeton University.
*[http://blogs.discovermagazine.com/80beats/2011/01/19/a-step-towards-quantum-computing-entangling-10-billion-particles/ A Step Toward Quantum Computing: Entangling 10 Billion Particles], from "Discover Magazine", Dated January 19, 2011.
*[http://www.fi.muni.cz/usr/gruska/survey1.ps Josef Gruska - ''Quantum Computing Challenges''] also in [http://www.amazon.com/Mathematics-Unlimited-Bj%C3%B6rn-Engquist/dp/3540669132 Mathematics unlimited: 2001 and beyond], Editors Björn Engquist, Wilfried Schmid, Springer, 2001, ISBN 978-3-540-66913-5

{{Quantum computing}}

{{number theoretic algorithms}}

{{DEFAULTSORT:Shor's Algorithm}}
[[Category:Quantum algorithms]]
[[Category:Integer factorization algorithms]]
[[Category:Quantum information science]]
[[Category:Articles containing proofs]]

Kirkendall effect - Revision history

en>Debouch: Undid revision 619378681 by AlonsoAlegre (talk) "short person jumping" does not describe anything in the article

en>Rjwilmsi: Journal cites, added 1 DOI using AWB (9904)