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."

Comments

Can someone explain...

[Crudely_Indecent]

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...

[thue]

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 )

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:Can someone explain...

[neokushan]

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...

[goffster]

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...

[Wraithlyn]

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:

Of course, factoring 15 isn't something that is going to threaten the PKI and cryptography in general, but factoring larger numbers is just a matter of increasing the number of qubits and this approach does seem to be a scalable solid state approach.

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.

Re:NSA likely already built one

[Sancho]

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.