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

23 of 262 comments (clear)

  1. Re:That's no moon... by Anonymous Coward · · Score: 5, Funny

    To be fair, it could have been either until we looked.

    (And you could have posted either here or at the correct story.)

  2. Re:Maths by Anonymous Coward · · Score: 4, Funny

    Of course 2 + 2 = 5. Take two strings. Tie 2 knots in each. Then tie them together and count the knots.

  3. 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: 5, Informative

      Consider problems which take a lot longer to compute than to verify. It may be much faster to compute the answer with a quantum computer, then check it with a regular computer, than to simply compute it with a regular computer.

    2. Re:Can someone explain... by gmueckl · · Score: 4, Informative

      That depends. Sometimes you have a hard time finding a possible result, but verifying it is simple. Factorization is just such a problem. So you repeat the algorithm and test the result until the test succeeds. If this is on average faster than a completely deterministic approach, you have won.

      --
      http://www.moonlight3d.eu/
    3. Re:Can someone explain... by Anonymous Coward · · Score: 5, Funny

      How is it useful to have the correct answer 50% of the time?

      Cat life-support devices.

    4. Re:Can someone explain... by Anonymous Coward · · Score: 5, Funny

      If you can factor really large prime numbers,

      I can factor really large prime numbers in my head.

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

    6. Re:Can someone explain... by Sancho · · Score: 4, Informative

      RSA public key includes a number n, which is the sum of two secret primes p and q

      Just FYI, it's the product of two secret primes. Product is for multiplication, while sum is for addition.

    7. Re:Can someone explain... by ShanghaiBill · · Score: 4, Informative

      How is it useful to have the correct answer 50% of the time?

      In many cases, it is very useful. If you need to crack a code by factoring a 200 digit number, getting the right answer 50% of the time would be fantastic. You just try repeatedly until you get the right answer.

      When designing computing algorithms, wouldn't you want it to return the correct answer 100% of the time?

      Of course. That is why the "quantum" computer would be just part of the solution. Overall, your algorithm would look like this:

      correct_answer() {
          for (;;)
              answer = quantum_result();
              if (verify_answer(answer)) {
                    return answer;
              }
          }
      }

       

      This solution would be good enough for any problem where verifying an answer is much faster than finding an answer. Most NPC problems fall into this category.

    8. Re:Can someone explain... by __aaltlg1547 · · Score: 5, Interesting

      That may be so, but computing the prime factorization of 15 is not in that class.

      I don't think you should even get to call something a middle-school dropout can figure in his head faster than he can say "Fries with that?" computation. So-called quantum computers still barely qualify as expensive but useless toys.

      Post again when a quantum computer can solve a real mathematical puzzle at a speed comparable to what a traditional computer can do. That would be news.

      Scientists have been touting the supposedly vast potential of quantum computing for decades now. D-E-C-A-D-E-S. But thanks to fundamental limitations of the nature of what they are, it's really hard to get them to barely work at all. It appears we could forever be stuck at the point where the qubits can be minimally processed but quantum decoherence can't be held off long enough to get a useful result. Meanwhile traditional methods of computing continue to forge ahead, although the rate of increase is slowing. Just keep in mind: quantum computing is 2500 years behind traditional computing methods in general, 175 years behind automated mechanical methods and more than 70 years behind electronic computers.

      Electronic computing methods overtook all other methods extremely quickly, but they faced only technical challenges not challenges posed by the fundamental nature of what they were trying to do. You can regard them in some ways as fancy abacuses: they literally count chunks of charge the way an abacus uses the position of beads to represent numbers (or in principle anything else). With qubits, you are attempting to get definite results by exploiting the indefinite character of things like the spin states of electrons. That's not just hard. It may be intractably hard. But if somebody can get it to work it might be very valuable to the NSA and anybody else interested in cracking the security of computing systems.

    9. Re:Can someone explain... by cryptizard · · Score: 4, Informative

      Thats how we find primes right now. All the practical algorithms are probabilistic. If a number is prime, running the algorithm always returns "prime". If it is composite, running the algorithm will result in "prime" about half the time and "composite" about half the time. This is fine, however, because we can run the algorithm n times and our confidence is .5^n, which grows very small very fast.

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

    12. 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
  4. Size, not reliability by TheRaven64 · · Score: 4, Interesting

    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
  5. One word: by drainbramage · · Score: 4, Funny

    Close enough for government work.

    --
    No brain, no pain.
    1. Re:One word: by __aaltlg1547 · · Score: 4, Funny

      Close enough for government work.

      Did you count that with a quantum computer, because by traditional methods I get 5 words 100% of the time.

  6. Well heck, Intel might buy it. by Anonymous Coward · · Score: 5, Funny

    Historically, they're a bit more tolerant about that math thing.

  7. NSA likely already built one by IamTheRealMike · · Score: 5, Interesting

    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.

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

  8. Re:First post - from a quantum computer by StillAnonymous · · Score: 4, Funny

    They've done studies, you know. 48% of the time, it works every time.

  9. Great! Congrats! by drolli · · Score: 4, Interesting

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