Talk:Shor's algorithm

From Wikipedia, the free encyclopedia

	This article is within the scope of WikiProject Physics, which collaborates on articles related to physics.	Physics Portal
???	This article has not yet received a rating on the assessment scale. [FAQ]
???	This article has not yet received an importance rating within physics.
Help with this template Please rate this article, and then leave comments here to explain the ratings and/or to identify the strengths and weaknesses of the article.

Contents 1 Time complexity of Shor's algorithm 2 speed of various classical factoring algorithms 3 Encryption schemes not vulnerable to quantum computing 4 Jones' Algorithm 5 Error in the 'classical' part 6 external link removed 7 Many Worlds Interpretation 8 QFT? 9 Implementation

[edit] Time complexity of Shor's algorithm

In Shor's original paper, he writes

"...Our quantum factoring algorithm takes asymptotically O((log n)^2 (log log n) (log log log n)) steps on a quantum computer, along with a polynomial (in log n) amount of post-processing time on a classical computer that is used to convert the output of the quantum computer to factors of n..."

How does this compare with the O((log n)^3) figure given on the Wikipedia page? I don't believe the expression Shor gives and the expression on the Wikipedia page are equivalent, unless the definitions of n in use are different, or if Shor is measuring something else. (More importantly, how was the O((log n)^3) figure arrived at?) -Yipdw 06:02, 14 May 2006 (UTC)

Big O notation gives an upper bound on running time, so O((log n)^3) is a weaker statment than O((log n)^2 (log log n) (log log log n)). Eg. Shor's statemtent implies the statement that is given in the Wikipedia. O((log n)^3) could have been arrived at by simply observing that O(log n) contains log log n * log log log n.

[edit] speed of various classical factoring algorithms

The article said the best classical factoring algorithms are O(e^N). The author presumably meant theta rather than O. The General Number Field Sieve [1] is significantly faster than that, with a running time of theta(exp(((64/9)*log N)^1/3 (log log N)^2/3). I've changed the sentence to claim superpolynomial rather than exponential. --LC

Okey dokey. You might want to make a wiki node on that. -- CYD

OK. It's integer factorization. --LC

Thanks! -- CYD

[edit] Encryption schemes not vulnerable to quantum computing

"Many public key cryptosystems, such as RSA, will become obsolete if Shor's algorithm is ever implemented in a practical quantum computer."

Are there any encryption systems that would not be obsolete if a quantum computer becomes practical? That would be useful information to add here, if anyone knows. I have been trying to look this information up but nothing so far, anyone have any clues?--ShaunMacPherson 22:06, 12 Apr 2004 (UTC)

One time pads would be unaffected. Richard Farmbrough.

This is briefly discussed at quantum computer#The power of quantum computers. At the present time, only factorisation and discrete log based ciphers are known to be seriously affected (if a QC of sufficient size could be built). A quantum computer could be used to attack a symmetric cipher, but it's speed up is "only" to take the square root of the number of steps. This is a huge speed up for typical block ciphers, but is trivially defeated by doubling the key size. There exists a standard, thoroughly studied method to double the key size of any block cipher, namely triple encryption. Further, the most common key size used today - 128 bits - would only be reduced to a work factor of the order of 2⁶⁴, which is still quite a tough job unless the information is extremely valuable. And the AES already has 192 and 256 bit modes built in. So, at our present level of knowledge, QC poses essentially no threat to symmetric encryption. Securiger 07:40, 6 Oct 2004 (UTC)

== Definition of f() in the 'classical part' Shouldn't it be: : ? Evan Ettinger.

[edit] Jones' Algorithm

Shor and Jones (Jones's Period Proxy Algorithm) use the same algorithm, however, Shor focusses on using a quantum computer and Jones looks for hyper-reduced reptends to solve in polynomial time.

166.70.15.234 18:10, 2 Apr 2005 (UTC)

[edit] Error in the 'classical' part

Isn't this wrong:

If gcd(a, N) ≠ 1, then there is a nontrivial factor of N, so we are done.

It should be trivial factor, shouldn't it? I'll change it myself soon if no-one replies. Aaron McDaid (talk - contribs) 10:34, 12 February 2006 (UTC)

No. The step is correct. The chances that gcd(a,N) > 1 are very small when factoring large integers. So in practice this step should always fail to find a factor. Note, however, that the remainder of the algorithm rks if gcd(a,N)=1. Furthermore testing gcd(a,N) is important when factoring small integers such as 15. 24.228.93.22 14:47, 16 February 2006 (UTC)

Trivial factors (or divisors) of N are by definition N and 1. Nontrivial factors are all factors of N other than N and 1. So the article was correct. 84.227.226.196 07:03, 30 May 2006 (UTC)

[edit] external link removed

I removed the external link simply because it is NOT an implementation of Shor's algorithm in php. Such an implementation is impossible because a quantum dynamical system cannot be simulated with a classical system. The implementation ignores the entire quantum portion of the algorithm.

LHon 09:42, 16 April 2006 (UTC)

...a quantum dynamical system cannot be simulated with a classical system... Sure it can, just not very efficiently. I'm putting the link back because it's relevant and not spam. —Keenan Pepper 16:58, 16 April 2006 (UTC)

[edit] Many Worlds Interpretation

Can someone fix the article so that it doesn't suggest that the many worlds interpretation has been established? I'd do it myself if I was an expert in this area.

I removed the offending paragraph, which was not only severly POV but blatantly false. I don't think something of this nature is even necessary in this article, but if someone wants to add something a little less POV, that would probably be ok. Grokmoo 18:57, 16 June 2006 (UTC)

[edit] QFT?

Throughout the article, it is stated many times that Shor's Algorithm uses the Quantum Fourier Transform (QFT). In fact, it uses the inverse of the QFT (the same circuit, only backwards). I haven't changed it myself because I want to make sure I'm not completely off-base here.

Can anyone else either support or refute this (I don't care if I'm wrong, so long as the article is correct). --RckmRobot 14:48, 16 June 2006 (UTC)

• After looking into this, I found out that it is in fact the inverse QFT rather than the "normal" QFT that is used in implementing Shor's Algorithm. I fixed the article accordingly.--RckmRobot 17:54, 21 June 2006 (UTC)

[edit] Implementation

There are many who don't accept the factorization of 15 as a valid "true quantum" implementation. Would an expert like to comment on why no one has gone beyond 15 in hardware implementations in the last 5 years? Lotte Monz 04:07, 7 July 2006 (UTC)

Any reference to these concerns? Also how many qbits does it take factor 21 and what is the maximum number of qbits have been implemented in a quantum computer? crandles 15:16, 21 September 2006 (UTC)

It takes 2n qubits to factor a number n bits long. 21 requires 5 bits to represent and therefore would require a quantum computer with atleast 10 qubits to factor. 198.37.27.79 03:04, 27 October 2006 (UTC)

Thanks. Though it does rather prompt the question of how 15 was factored with 7 qubits.crandles 11:07, 27 October 2006 (UTC)