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."
Sometimes 2+2=5, give the thing a break!
To be fair, it could have been either until we looked.
(And you could have posted either here or at the correct story.)
From TFA:
As Shor's algorithm is only supposed to give the correct answer 50% of the time, this is a good result.
How is it useful to have the correct answer 50% of the time? When designing computing algorithms, wouldn't you want it to return the correct answer 100% of the time?
"Lame" - Galaxar
Validating the result is cheap on a classical computer. Even for very large values, multiplying two 4096-bit values together and checking the result is incredibly cheap. A quantum computer that could give the right set of divisors for a 4096-bit prime 1% of the time would still let you very quickly find which of the answers that it gave was correct. The limitation is the size, not the reliability.
I am TheRaven on Soylent News
Close enough for government work.
No brain, no pain.
Historically, they're a bit more tolerant about that math thing.
It seems that quantum computing has consistently been viewed as harder than it really is, judging by the ever-decreasing timescales between breakthroughs. Judging from the history of cryptography, and the military value of being able to break RSA, it's not unreasonable to expect that the NSA may have been trying to build such a chip for some time and could potentially have succeeded.
Some months ago James Bamford, who is the premier chronicler of the NSA and has a history of being given accurate leaks, claimed the NSA had made a "huge breakthrough" in its ability to break codes - and that the datacenter they're currently building is a part of the solution. The NSA denied everything of course. But if academics are now able to build a working implementation of Shors algorithm for small numbers, that strongly implies that a focussed team with practically infinite budgets could have already succeeded in building one that can handle crypto-sized numbers.
They've done studies, you know. 48% of the time, it works every time.
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...
Disclaimer: I am a former researcher in the field, left to some other job.
What you can see at UCSB is what happens when a team of scientists which ae skilled in engineering, working as a team, and collaborating with everybody happens to have the right guy as the leader (with the right policy about co-authors on publications).
Everybody whom i met from this team was open, honest, and friendly; they have worked hard and long on it and they accumulated some of the best people.
They deserve the success they have now! I think there may be a small break now in their publications, since i have the ffeling they now may work on overcoming the next big roadblocks (but now they they have all the backing they could need for it).
I also have to state it will be a long long way to the first QC. While i believe that every step like this will be more than just replicated at the NSA, i believ that they wont be more than 10 years ahead, and i estimate 20y-30y until qc works better than classical qc (although I also hope and believe that breaktroughs are possible).
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});