Shor's Factoring Algorithm - does it even work?

[xilman]

Originally Posted by Citrix

Shors algorithm says that for a pseudo random number a, find a^x=a^(x+r )mod n

where n is the number to be factored.
How do you do this on an ordinary computer for a large number? I don't think the algorithm is p?

If r could be found easily then all numbers can be factored in p!

Citrix

Ah, a great light dawns!

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 order-finding 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

[Citrix]

What does this mean

"A reduction of the factoring problem to the problem of order-finding, which can be done on a classical computer. " -- How do you do this?

Citrix

[akruppa]

Originally Posted by Citrix

Shors algorithm says that for a pseudo random number a, find a^x=a^(x+r )mod n

where n is the number to be factored.
How do you do this on an ordinary computer for a large number? I don't think the algorithm is p?

If r could be found easily then all numbers can be factored in p!

Citrix

On a conventional computer the algorithm is purely exponential-time. The idea is:

1. Choose some a
2. Compute a^n (mod N) for 1<=n<=k*N, with k large enough. This sequence is o-periodic, o=ord_N(a)
3. Do a Fourier transform on the sequence. Since it is o-periodic, 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. Mind-boggling 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

[Citrix]

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.

[Mystwalker]

Originally Posted by R.D. Silverman

15 has indeed been factored on a 4-qubit quantum computer.

Just for clarification:
The article stated 7-qubits. Which one is correct?

[akruppa]

7 qubit is correct. The composite number 15 has 4 bits, and you need extra bits for the exponent, etc.

Alex

[ewmayer]

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.

[Citrix]

Please remove the word crap from the title. It was a misunderstanding on my part.
(Rename it quantum computing perhaps)

Thankyou,
Citrix

[akruppa]

Done.

Alex

[Peter Nelson]

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.

[ewmayer]

Originally Posted by akruppa

Done.

Wuss.

I quote:

Originally Posted by Citrix

Is there any merit to this method? It look like crap to me.