20051025, 19:43  #12  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
2·7^{3}·17 Posts 
Quote:
You are quite correct in your observation. No algorithm is known to solve that problem in polynomial time on a classical computer. However, such an algorithm is known for a quantum computer  it is Schor's algorithm. The article to which you refer specifically states that the orderfinding subroutine is to be run on a quantum computer. In this situation the entire algorithm runs in polynomial time. Looks like you thought that the entire algorithm had to be run on a classical machine. Paul 

20051025, 19:47  #13 
Jun 2003
3×5×107 Posts 
What does this mean
"A reduction of the factoring problem to the problem of orderfinding, which can be done on a classical computer. "  How do you do this? Citrix 
20051025, 19:50  #14  
"Nancy"
Aug 2002
Alexandria
4643_{8} Posts 
Quote:
1. Choose some a 2. Compute a^n (mod N) for 1<=n<=k*N, with k large enough. This sequence is operiodic, o=ord_N(a) 3. Do a Fourier transform on the sequence. Since it is operiodic, the Fourier coefficients for the frequency o/(k*N) will dominate 4. Randomly choose a coefficient with probability according to its amplitude On a conventional computer, steps 2 and 3 take \Omega(N) steps. On a quantum computer, you can put the all the exponent qubits into a (1 1) (1 1) / sqrt(2) state, i.e. a 0 and 1 bit with 50% probability each, and exponentiate by that exponent. The result of this exponentiation is a superposition of all a^n. This superposition can be transformed with a Quantum Fourier Transform (QFT), giving you a state where the o/(k*N) frequency and its multiples dominate in amplitude. Measuring the state gives you one of these values. You can then recover o by a continued fraction expansion. The nice thing is that the exponentiation and the QFT can be done in time O(log(N)^2), iirc. There are some catches that make the algorithm extremely tricky to actually implement, but the idea itself is sound. I gave a presentation on this algorithm at the uni once. Quantum comuting is by far the weirdest I've seen yet. Mindboggling does not begin to describe it. If you're interested in this, get Nielsen and Chuang: Quantum Computation and Quantum Information. Note: the above is from memory, there probably are errors. I think I got the overall idea right, though. Alex Last fiddled with by akruppa on 20051026 at 22:37 Reason: corrected Hadamard matrix, complexity 

20051025, 19:55  #15 
Jun 2003
3·5·107 Posts 
Thankyou very much. This stuff is really interesting. It was my fault. I was too quick to judge the method. I just read the classical part and thought that, it had to be done before the quantum part.

20051025, 21:25  #16  
Jul 2004
Potsdam, Germany
3×277 Posts 
Quote:
The article stated 7qubits. Which one is correct? 

20051025, 21:34  #17 
"Nancy"
Aug 2002
Alexandria
9A3_{16} Posts 
7 qubit is correct. The composite number 15 has 4 bits, and you need extra bits for the exponent, etc.
Alex 
20051025, 21:57  #18 
∂^{2}ω=0
Sep 2002
Repรบblica de California
5×2,351 Posts 
I'm renaming this thread "Shor's Factoring Algorithm = Crap?" (I believe that captures the tone of the initial posting, but is more descriptive) and moving it to the regular Math section.
Note that there is no 'c' in the spelling of Peter Shor's last name. Last fiddled with by ewmayer on 20051025 at 21:58 
20051026, 03:42  #19 
Jun 2003
3105_{8} Posts 
Please remove the word crap from the title. It was a misunderstanding on my part.
(Rename it quantum computing perhaps) Thankyou, Citrix Last fiddled with by Citrix on 20051026 at 03:43 
20051026, 05:12  #20 
"Nancy"
Aug 2002
Alexandria
4643_{8} Posts 
Done.
Alex 
20051026, 05:36  #21 
Oct 2004
23^{2} Posts 
Quantum computing and the Shor algorithm in particular is mentioned in "Crandall and Pomerance: Prime Numbers: A computational approach" in second edition its 8.5.2 "The Shor quantum algorithm for factoring" on p422.
For second edition it may be slightly in need of revision (ie the IBM machine factoring 15 was in 2001) whereas they say "We stress that an appropriate machine has not been built". Perhaps someone could suggest to C&P that they could mention the IBM experiment. However they do say "but if it were the following algorithm IS EXPECTED TO WORK". In their presentation they do not give all the details of the algorithm. In their words "we have been intentionally brief in the final steps of the algorithm". They do point out that it could be done on conventional computers but in much longer time which would become unworkable, and it is quantum computers that offer opportunity to use it. I personally found the answers.com/wikipaedia treatment more complete and a little more readable. 
20051026, 18:35  #22  
∂^{2}ω=0
Sep 2002
Repรบblica de California
10110111101011_{2} Posts 
Quote:
I quote: Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Alternativelygifted factoring algorithm  Prime95  Miscellaneous Math  72  20151026 00:14 
Shor's Algorithm  flouran  Math  3  20091027 09:31 
Prime Factoring Algorithm  Visu  Math  66  20080512 13:55 
Faster Factoring Algorithm?  Citrix  Factoring  6  20071223 11:36 
A new prime factoring algorithm?  Visu  Factoring  22  20061109 10:43 