Content deleted Content added
→external link removed: reply |
questions on time complexity |
||
Line 1:
==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? (More importantly, how was the O((log n)^3) figure arrived at?) -[[User:Yipdw|Yipdw]] 06:02, 14 May 2006 (UTC)
==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 [http://citeseer.nj.nec.com/398050.html] is significantly faster than that, with a running time of theta(exp(((64/9)*log N)<sup>1/3</sup> (log log N)<sup>2/3</sup>). I've changed the sentence to claim superpolynomial rather than exponential. --[[user:LC|LC]]
| |||