Slashdot Mirror
Solid State Quantum Computer Finds 15=3x5 — 48% of the Time
mikejuk writes "The Shor quantum factoring algorithm has been run for the first time on a solid state device and it successfully factored a composite number. A team from UCSB has managed to build and operate a quantum circuit composed of four superconducting phase qubits. The design creates entangled bits faster than before and the team verified that entanglement was happening using quantum tomography. The final part of the experiment implemented the Shor factoring algorithm using 15 as the value to be factored. In 150,000 runs of the calculation, the chip gave the correct result 48% of the time. As Shor's algorithm is only supposed to give the correct answer 50% of the time, this is a good result but not of practical use."
Consider problems which take a lot longer to compute than to verify. It may be much faster to compute the answer with a quantum computer, then check it with a regular computer, than to simply compute it with a regular computer.
That depends. Sometimes you have a hard time finding a possible result, but verifying it is simple. Factorization is just such a problem. So you repeat the algorithm and test the result until the test succeeds. If this is on average faster than a completely deterministic approach, you have won.
http://www.moonlight3d.eu/
RSA public key includes a number n, which is the sum of two secret primes p and q
Just FYI, it's the product of two secret primes. Product is for multiplication, while sum is for addition.
How is it useful to have the correct answer 50% of the time?
In many cases, it is very useful. If you need to crack a code by factoring a 200 digit number, getting the right answer 50% of the time would be fantastic. You just try repeatedly until you get the right answer.
When designing computing algorithms, wouldn't you want it to return the correct answer 100% of the time?
Of course. That is why the "quantum" computer would be just part of the solution. Overall, your algorithm would look like this:
correct_answer() {
for (;;)
answer = quantum_result();
if (verify_answer(answer)) {
return answer;
}
}
}
This solution would be good enough for any problem where verifying an answer is much faster than finding an answer. Most NPC problems fall into this category.
Thats how we find primes right now. All the practical algorithms are probabilistic. If a number is prime, running the algorithm always returns "prime". If it is composite, running the algorithm will result in "prime" about half the time and "composite" about half the time. This is fine, however, because we can run the algorithm n times and our confidence is .5^n, which grows very small very fast.
I believe it's just confusing wording. They're saying 48% is good because at best it could only have been 50%. It's impractical because it is only 4 qbits and so conventional computing can easily do the job faster and cheaper for numbers that small (for that matter, it' small enough that a lookup table is an attractive solution).
With qubits, you are attempting to get definite results by exploiting the indefinite character of things like the spin states of electrons. That's not just hard. It may be intractably hard.
Actually, the math and abstract procedure of how to do this is pretty well understood. The question of how to get definite answers from such quantum states is solved, in the sense the algorithm's results are very quickly and easily shown to have worked or not (and not just by multiplying the two factors, the result of the quantum portion of calculation has to be converted into actual factors via classical computation, and is obvious when this fails). The jump from probabilistic states to definite answers is already quite clear.
The hard part is improving the signal to noise ratio essentially. It is not the managing of the quantum states, but managing of the apparatus to keep it doing what you want it to do. And that is one of the big results of this paper. It is not about the 48% being good enough to be practical, it is that the 48% result is almost the ideal 50% case. This means that outside noise and device failure due to improperly carrying out the steps was quite small, which suggest that the number of qubits could be scaled up, and still have the algorithm followed. It is pretty well understood what the limitations of the algorithm is, and known that it could still be very, very useful, but that won't go anywhere if the algorithm can't be implemented.
Schrödinger wrote about the cat idea in order to demonstrate how ridiculous that particular model of quantum physics is; he'd be rolling in his grave if he knew that people were taking it as truth...
That case happens rarely. The case you're actually looking for is values of a where the function has even period.
The reasoning behind it is this:
Suppose that N has at least two distinct prime factors. (If it isn't, then N is either prime or a perfect power of a prime. There are efficient algorithms for detecting the latter case.) Further suppose that the function f(x) = a^x mod N has minimum period 2r for some r. (That is, f(x+2r) = f(x), but f(x+q) f(x) for any q < 2r.)
In this case, a^(2r) is congruent to 1 modulo N, but a^r is NOT congruent to 1 modulo N. That is, a^r is a square root of unity modulo N, but it isn't congruent to 1. If it also isn't congruent to -1 (which is the case that you mentioned), then it's a nontrivial square root of unity.
Now consider the number d = gcd(a^r-1, N). If d=N, then N is a factor of a^r-1, that is, a^r is congruent to 1 modulo N. This is a contradiction (since we eliminated this case above), so it can't happen. Similarly, if d=1, then a^r is congruent to -1 modulo N, which is the other case that we eliminated above. (Exercise: prove this!)
So d is a divisor of N (because it's the gcd of N with some other number), but it isn't 1 or N. Therefore, it's a nontrivial factor of N.
Of course, it's not obvious that there should be an a for which f has even period, but that's where the hardcore analysis comes in.
sub f{($f)=@_;print"$f(q{$f});";}f(q{sub f{($f)=@_;print"$f(q{$f});";}f});