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.