Solid State Quantum Computer Finds 15=3x5 — 48% of the Time 262
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."
Can someone explain... (Score:5, Insightful)
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?
Re:Can someone explain... (Score:2, Insightful)
It's useful because checking that the answer is correct or not is trivial, and having to run the algorithm twice (long term average) is still exponentially faster than relying on classical methods.
Re:That's no moon... (Score:2, Insightful)
It was both a moon and a space station at the same time.
To the jerk who modded the parent down:
Read up on schroedinger's cat you doofus.
Then you can have your geek card back.
Re:Can someone explain... (Score:5, Insightful)
For a concrete example, the RSA public key includes a number n, which is the sum of two secret primes p and q. The encryption is broken if an attacker can derive p and q from n by factorization. ( http://en.wikipedia.org/wiki/RSA_(algorithm)#Operation [wikipedia.org] )
if you could factorize an RSA public key 48% of the time then it would be a pretty big deal, since it would render RSA completely obsolete.
Re:One word: (Score:4, Insightful)
In this case, I suspect that the NSA would readily agree... This quantum computer is far too small for any practical purposes that couldn't be brute-forced with a TI-83 much more easily; but tepid accuracy isn't a big deal if checking your work is computationally inexpensive...
Re:NSA likely already built one (Score:5, Insightful)
And before anyone freaks out and thinks that the NSA is reading their e-mail, keep in mind that they have to be very selective about how and when they use results from their quantum computer. This is similar to breaking ENIGMA--you want the enemy to think that their codes are secure, so you don't suddenly counter all of their plans perfectly. You certainly don't turn this on e.g. classical organized crime, as that could give away your capabilities on a considerably less valuable target.
Re:Can someone explain... (Score:5, Insightful)
Yeah, scientists were theorising about the Higgs-boson for deacdes as well. Sometimes it takes that long to get somewhere.
It's very early days for quantum computing. The fact that they've taken something from pure theory and made it actually do something is a fantastic indicator that they're onto something. So what if it takes another 5 decades to get there, the implications would still be incredible by that point.
Re:Can someone explain... (Score:5, Insightful)
An algorithm that could factor a 4096 bit number even 10%
of the time would be enough to consider 4096 key as completely unsafe
for cryptography.
It is easy enough to verify the result.
Re:Can someone explain... (Score:3, Insightful)
yeah. the wright brothers built some stupid linen and balsa wood thing that fluttered above the ground for a few seconds. useless. they've been talking about flight for centuries
morse can send little tappity taps on a wire? big deal. i can't figure out what it means, and does anyone actually believe we're going to string wires all over the country? impossible!
and i heard of this television device. what a crazy unweildy delicate gizmo. shows a fluttering image you have to squint to maybe make out what they are trying to show. ma and pa middle america is going to set up this gizmo in their living rooms instead of a trusty radio? you're out of your minds. they have radio shows and the picture show at the local theatre, this television thing is going nowhere
in other words: thank god we have people with actual imagination in this world. what do dull minds like yours contribute exactly?
Re:Can someone explain... (Score:2, Insightful)
But we are a very long way from that. Right now it takes enormously more effort to do the job with a quantum computer and it can only be done at all with very small numbers like 15. And the results show that hardware is not scalable. It's supposed to get the answer right 50% of the time and it only gets 48% in 150,000 runs. The 2% difference is significant and whatever the cause of that is, it's almost certain to not scale well:
If a 4 bit number gives you a 48% correct rate, that means that it gets the wrong answer 2% more often than it theoretically should. So the hardware is failing to work correctly conservatively 4% of the time. (Since only half the time can you tell that the hardware didn't perform as expected.). The machine has to be massively scaled up to get into the class that might be able to solve lengthy computing problems, and the hardware-dependent error rate is going to scale up at least exponentially with the number of bits. (Looks like it might be 99%^N.) If it's only that bad, the hardware CAN be scaled up to useful problems, like breaking 128-bit encryption with fewer trials than traditional methods.
Re:Can someone explain... (Score:4, Insightful)
By that law I predict Shor's algorithm works in practice as follows:
6=2x3 96%
15=3x5 48%
35=5x7 24%
77=7x11 12%
143=11x13 6%
Good luck breaking RSA.
Re:Can someone explain... (Score:5, Insightful)
There should be a "-1 Bitching That This Doesn't Meet My Personal Criteria For News" mod. Every. Damn. Article. Somebody has to come write an essay on how completely not interesting or impressive this is to them.
Yes, factoring 15 isn't particularly impressive. Thank you, Captain Fucking Obvious.
Now if you'd bothered to RTFA, you'd have noted it already directly discusses this:
So they can instantly factor numbers (well, with ~50% success), with an approach that *seems scalable*. That's news to me.
Maybe in a few months, there will be another story about how they failed to scale this approach up. That will be an additional piece of news. Failure can be news.
Some of us are interested in the journey, not just the destination.