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

12 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 __aaltlg1547 · · Score: 1, 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.

    7. 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.
    8. 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:That's no moon... by shentino · · Score: 1, 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.

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

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