Slashdot Mirror

← Back to Stories (view on slashdot.org)

Solid State Quantum Computer Finds 15=3x5 — 48% of the Time

Posted by timothy on from the please-show-your-work dept.

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

10 of 262 comments (clear)

  1. Can someone explain... by Crudely_Indecent · · Score: 4, 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?

    --


    "Lame" - Galaxar
    1. Re:Can someone explain... by Anonymous Coward · · 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.

    2. Re:Can someone explain... by thue · · Score: 4, 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 )

      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.

    3. Re:Can someone explain... by neokushan · · Score: 4, 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.

      --
      +1 IDisagreeSoHeMustBeATrollOrAnAstroturferOrAShill
    4. Re:Can someone explain... by goffster · · Score: 4, 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.

    5. Re:Can someone explain... by circletimessquare · · Score: 2, 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?

      --
      intellectual property law is philosophically incoherent. it is your moral duty to ignore it or sabotage it
    6. Re:Can someone explain... by ld+a,b · · Score: 3, Insightful

      Let me remind you of the zeroth law of thermodynamics - You can't have nice things.
      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.

      --
      10 little-endian boys went out to dine, a big-endian carp ate one, and then there were -246.
    7. Re:Can someone explain... by Wraithlyn · · 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:

      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.

      --
      "Mind, as manifested by the capacity to make choices, is to some extent present in every electron." -Freeman Dyson
  2. Re:One word: by fuzzyfuzzyfungus · · Score: 3, 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...

  3. Re:NSA likely already built one by Sancho · · Score: 4, 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.