From: greg@math.ucdavis.edu (Greg Kuperberg) Subject: Re: This week in the mathematics arXiv (31 Jan - 4 Feb) Date: 7 Feb 2000 12:00:02 -0600 Newsgroups: sci.math.research Summary: [missing] In article <87fv3j$9ts$1@manifold.math.ucdavis.edu>, Greg Kuperberg wrote: >In particular the best non-quantum algorithms for factoring a number >with N digits requires exponential time (exponential in N^1/4 I think). As several people pointed out, this is inaccurate. I should have said that the fastest known non-quantum factoring algorithm works in time O( C^(D^1/3*log(D)^2/3) ) to factor a number with D digits. This is more conventionally written O( exp(c*log(N)^1/3*log(log(N))^2/3 ) to factor the number N. Shor's algorithm is definitely polynomial time; Shor gives the complexity as O( D^2*log(D)*log(log(D)) ). Actually in my view this complexity bound is debatable. It is not completely clear which model of quantum computation would best match a real quantum computer; in particular no one knows the true performance penalty for implementing quantum error correction. This uncertainty is similar to the poly-logarithmic fudge factor in comparing idealized random-access computers with real computers. Of course since quantum computers don't yet exist, the uncertainty in their complexity models is greater. Nonetheless the conclusion that factoring has quantum complexity (D^(2+epsilon)), or at worst O(D^(3+epsilon)), is inescapable. -- /\ Greg Kuperberg (UC Davis) / \ \ / Visit the Math Archive Front at http://front.math.ucdavis.edu/ \/ * From A-hat to Z(G), ABC to ZFC *