Slashdot is powered by your submissions, so send in your scoop

 


Forgot your password?
Close
typodupeerror
×
News

IBM Builds A Limited Quantum Computer 317

Posted by chrisd from the soon-your-pgp-key-will-be-useless dept.
phr1 writes "IBM has announced and Yahoo has noted that the first working implementation of Shor's factoring algorithm. Using NMR techniques they built a seven-qubit quantum computer and factored the number 15 into the factors 3 and 5. This is by far the most complicated quantum computation ever done. It's quite an amazing feat--many people thought quantum computing was just a theoretical curiosity and Shor's algorithm could never be implemented in practice."
This discussion has been archived. No new comments can be posted.

IBM Builds A Limited Quantum Computer More

IBM Builds A Limited Quantum Computer

Comments Filter:
  • to factor 15 as it does the product of two 128 bit primes, what's stopping this computer from breaking current asymmetric crypto right now?
    • Well for starters the time will not be the same. Also the complexity of factoring a 256 bit number is amazingly higher than factoring a 4-bit number.

      Tom

    • Re:if a quantum computer takes the same time (Score:1, Interesting)

      by Anonymous Coward
      The NSA probably already has a tie with quantum computer developers. Maybe our use of crypto algorithms have already been broken...

    • Re:if a quantum computer takes the same time (Score:5, Interesting)

      by Anml4ixoye ( 264762 ) on Wednesday December 19, 2001 @09:13PM (#2729737) Homepage
      Mainly because of the number of molecules it takes to perform that feat. "IBM chemists designed and made a new molecule that has seven nuclear spins" - exactly enough to solve the simple factor. You need many more spins than that to perform complex calculations.

      But once the molecules are put together and they can control them properly, then nothing really stops it. That is why they say that a fundamental change in cryptography is on the horizon.

    • Moin!

      -ironic- Damn does this mean i have to use numbers greater than 5 as p,q in my implementation of RSA? Damn, even encoding my files with a 8-Bit key will mean milliseconds of waiting in front of my K7. I can't stand waiting -/ironic-

      No, to be onest i do not think the coherence length will be raised to those needed for a 256-QBit QC within a decade. Until then we will use longer keys. I think that - if ever - the race Keylength vs. QC will be going on 20 years at least.

      CU Seth

    • Re:if a quantum computer takes the same time (Score:4, Informative)

      by stevelinton ( 4044 ) <sal@dcs.st-and.ac.uk> on Thursday December 20, 2001 @09:31AM (#2731499) Homepage
      It doesn't. The thing about Shor's algorithm is that, as initially written up, it factors an L bit number on a 3L q-bit quantum computer in polynomial time (O(L^3), I think). Obviously IBM have tweaked it a bit to get down from 12 (3*4) to 7 qbits, but even so, going from 4 bits to say 1024 would require 256 times as many qbits (the hard part) and 256^3= 16 million times as much time (not a big problem).

      In contrast existing non-quantum techniques take O(e((log L)^(2/3)*(L)^(1/3))) time on a computer of fixed word size. To go from 4 bits to 1024 increases the run time by a factor of something like 10^18.

      More to the point, on quantum computers, the race between prime finding, and so key pair generation, and factoring and so code-breaking is much less uneven.

  • Frightening implications (Score:3, Insightful)

    by krackbebe ( 545104 ) on Wednesday December 19, 2001 @09:08PM (#2729718) Homepage
    If a private sector company has been able to climb the steep hill that is quantum computing, how far has the US govt been able to get with their nearly unlimited budget?

    It has been widely acknowledged that such agencies as the NSA have been at least a decade or more ahead of the private sector. The first govt to get a working quantum computer not only has unbreakable encryption, they are able to read any code of foreign nations. The stakes are incredible!

    Soon, they will be watching all of us. Better read 1984 quickly my fellow citizens!
    • 1. The us government does not have an unlimited budget.

      2. Most meaningful research comes from the private sector (bell labs and the like) with a few exceptions (Darpa)

      3. Even if the government had quantum computer level encription it couldn't get it's self organized enough to use it for more then maybe presidential level communication.

      • Re:Frightening implications (Score:2, Interesting)

        by Anonymous Coward
        Yeah and you probably still think they can't crack DES, either...

        The NSA's budget is classified. They recruit top people in research fields (and not only U.S. citizens). The estimate I've heard is that they are more like TWENTY years ahead of civilian cryptographers. Don't be fooled by the government's outward appearance of being inept. They do get things done in certain areas where it counts.
      • 2. Most meaningful research comes from the private sector (bell labs and the like) with a few exceptions (Darpa)

        Most meaningful reasearch, by any standard you care to name (dollars spent, papers written, patents granted, etc), comes from Universities. In the US, almost all industrial basic research (IBM being a notable exception) has been eliminated in the names of quarterly profits. The problem is that the return on basic research doesn't arrive for 5-10 years and most companies don't look beyond next quarters balance sheet.

        And, since you brought it up, Bell Labs no longer exists. When AT&T split itself up, the old Bell Labs became Lucent Corporation. The research parts of Lucent pretty much ceased to exist as of the recent restructuring where research was split up between Lucent, Agere, and Avaya.

        And, as someone else pointed out, DARPA is only for the U.S. military and is a primarily funding agency, not a research lab. U.S. civilian research is funded largely by DOE, NSF, and NIH.

        -JS

    • Nonsense! (Score:2, Funny)

      by Anonymous Coward
      Just send in Robert Redford and his team of lovable misfits to get the black box out of the answering machine!

    • Re:Frightening implications (Score:5, Informative)

      by internic ( 453511 ) on Wednesday December 19, 2001 @10:38PM (#2730053)

      While I have also often heard stories of the NSA having much more advanced equipment and techniques than the private sector, or at least than the non-classified private sector, in the case of quantum computing this is unlikely. First, it's a relatively new subject. Shore's algorithm, for example, was only discovered in the 80's. There really hasn't been enough time for them to get so far ahead. Second, the NSA is full mostly of mathematicians and computer scientsts, not physicists, so they really don't have the right staff for that. Third, most of the academic research is funded by the NSA.

      Finally, though it's hard to say exactly how far this technology is from being useful (or alternately the probability that it will EVER be useful), it is probably safe to say it will be quite a while from now. Moreover, it is probably also safe to say that it only gets harder from here. Larger computations will involve the same problems as these only on larger scales plus a whole new, tougher, slew of problems that these avoid. These are chiefly quantum decoherence and entangling large numbers of quantum states.

      Quantum decoherence is the loss of the special quantum information (quantum phase relations) that allows quantum computers to do their funky magic. This happens over time in any system that has any interaction with the outside world. I think these small calculations largely avoid this problem because they are reasonably fast. Larger ones involve more steps and thus will run up against these problems. Some error correcting quantum codes have been developed, but these involve even more qubits, which exaserbates the other problems, and are still largely in the formative stages.

      The other big hurdle is entangling much larger numbers of particles in one state. These take advantage of the interactions between different nuclei in the same molecule. Once you need many more qubits, you will need to come up with a more general scheme for entangling the quantum states, because it's unlikely that you'll be able to engineer a molicule for the purpose. Also, the bigger you make your system, the more strongly it interacts with the outside world and the worse decoherence becomes....Life's a bitch, ain't it?

      So, I think this is really exciting and quantum computers have great promise, but I don't expect to have a quantum co-processor in my PC any time soon, nor do I really think it's likely that the NSA has a quantum supercomputer sitting in the back room decrypting my credit card information.

      • You weren't paying attention. Shor's(sic) algorithm was discovered by AT&T's engineer by the same name in 1994!
      • , the NSA is full mostly of mathematicians and computer scientsts, not physicists, so they really don't have the right staff for that.
        The NSA run their own chip fab, and now that they are no longer able to buy all the equipment they need from US suppliers, they reverse engineer and rebuild the fab equipment they get from foreign sources, so I imagine they have a few physicists around some somewhere.

        sPh

      • Finally, though it's hard to say exactly how far this technology is from being useful (or alternately the probability that it will EVER be useful), it is probably safe to say it will be quite a while from now. Moreover, it is probably also safe to say that it only gets harder from here.

        Certainly. On the other hand, if you had looked at the thermionic-valve computers of the 1940's, it would have been hard to imagine the Atari 2600, much less a Beowulf cluster of quad-Xeons.

        nor do I really think it's likely that the NSA has a quantum supercomputer sitting in the back room decrypting my credit card information.

        Nor should you. However, given the way the NSA has largely backed off any serious efforts to outlaw public-key cryptography, it is likely that they have either the brute force computing power or classified algorithms to crack it, so it's not necessary to imagine exotic computing technology. Besides, if an agency like the NSA really wants information from you badly enough, you'll end up giving it to them, Winston.


        Shouldn't there be a +1 Deeply Paranoid moderation option?

        • However, given the way the NSA has largely backed off any serious efforts to outlaw public-key cryptography, it is likely that they have either the brute force computing power or classified algorithms to crack it

          I think it is more probable that they realized it is much easier to attack the passphrase or find some other way of breaking into the computer, install a keystroke logger and so on, than try to decipher a message by brute force.

          Or it could just be that somebody actually realized that a country where strong cryptography is readily available to everyone is actually safer for everyone.

    • It has been widely acknowledged that such agencies as the NSA have been at least a decade or more ahead of the private sector.

      Schneier's Applied Cryptography has a discussion of this with regard to DES. Here's my description of it (I'm doing this off the top of my head, and I'm not an expert, so please excuse any mistakes):

      In the early 1970s, IBM was contracted by the US Government to create a standard encryption algorithm that companies could use to secure their communications.

      IBM was given free reign to design what they wanted, with one exception: Any algorithm that they developed would have to be given to the government (NSA) to look at, and the government would have final approval. So, after some work, IBM came up with the algorithm that we now know as DES, although what they came up with is slightly different than what is in use today...

      The important part of DES, the part that does the actual encrypting, is a part of the algorithm where the incoming bits are mixed. The actual mixing can be described as a matrix of numbers. The makeup of this matrix is important, as it determines whether the bits are properly encrypted. If this block of numbers has the wrong configuration, then the numbers may not be mixed in a truly secure manner.

      The question then, of course, is how to determine whether a block of numbers is "secure" or not. IBM had developed a test that would check this particular property, came up with a set of numbers that they had decided would make the algorithm properly secure, and gave it all to the NSA to check.

      The NSA approved the algorithm, but with one exception: They supplied a new set of numbers for the mixing block! IBM checked these new numbers, found that they satisfied their requirements for security, and, so, that is what we are using today.

      So What? About 10 years later a new method of attacking ciphers was developed, called Differential Analysis. This method was brand new, nobody had ever heard about it before, and turned out to be very powerful. Of course, DES was checked to see how secure it was against this new attack, and it turns out that the security of DES depends entirely on what numbers are picked for the mixing block.

      Here's the interesting part: It turns out that the numbers used in DES, the ones that the NSA itself had generated and given to IBM, were in the 2% worst of all possible blocks to be used!

      Coincidence? Perhaps...although it does seem to indicate that the NSA was aware of Differential Analysis many years before the rest of the world was, and purposely sabotaged DES to make it easier to crack. Remember that the NSA is the world's largest employer of mathematicians!

      • You're exactly right and wrong! (Score:5, Interesting)

        by HiredMan ( 5546 ) on Thursday December 20, 2001 @02:29AM (#2730726) Journal
        You're right that the NSA knew about Differential Cryptanalysis years before anyone. I extrapolated this largely using the same facts - but if you read _AC_ carefully they openly acknowledge this.

        But you're wrong in the fact that DES IS resistant to DC. The bit S-box design the NSA gave IBM are designed to make it STRONGER against DC NOT weaker.

        "As in choosing the key length , another of the NSA'a design criteria was based on making the algorithm [DES] resistant to differential cryptanalysis..." _AC_ first edition Schneier page 238

        If you want to bust the NSA's chops complain that they made the key length go from 128 to (effectively) 56 bits. Now that hurt...

        =tkk
    • If a private sector company has been able to climb the steep hill that is quantum computing, how far has the US govt been able to get with their nearly unlimited budget?

      IBM is no ordinary corporation - it's practically a country in its own right. Remember that two of the largest revolutions in computing (desktop PCs and relational databases) were things that IBM created, then couldn't exploit commercially, and they not only survived but thrived after two disasters like that. If anyone can do it, Intergalactic Battle Machines can...

    • Re:Frightening implications (Score:4, Insightful)

      by KjetilK ( 186133 ) <kjetil AT kjernsmo DOT net> on Thursday December 20, 2001 @07:35AM (#2731245) Homepage Journal
      This is an interesting point. We discussed this to some length at the International Conference for Physics Students this summer.

      The core question is: Can a real, working quantum computer be built in secrecy?

      IMHO, it is very unlikely. It has to do with how science works. A few things can pop out straight from a brilliant idea, and can be implemented based on that idea alone. This is, however, very, very uncommon. Even the most brilliant minds needs feedback from their peers to get anywhere. You need critisism, even strong opposition, to fine-tune your ideas and your arguments. This is what the greater scientific community provides.

      In closed projects, even if you hire the best minds, you'll get inbreed, you will not get the same level of critisism, and soon you will most probably paint yourself into a corner.

      So, while there are examples of projects that have been developed in secrecy that actually work well, most real science has to be done in the open.

      Arguably, the most advanced project that we know of that was conducted in secrecy is the Manhattan project. However, building a nuclear bomb wasn't really that difficult. All the basic science was well understood in 1941, it was just engineering left. The brilliant minds found it rather boring. It was completed, and it was kept secret because of the war, there existed very strong reasons for the people who developed it to keep it secret. Hardly any such reasons exist today. A quantum computer will be so important to science and technology, I don't think you can have a larger group of brilliant minds keep it secret for very long. They would want to have the advancement of science going, and beside, they want the nobel prize.

      I'm not really frightened. I'd really like to see quantum computers. Yeah, it will make PKI as we know it obsolote, and it really needs adressing fast. I'm not aware of any algoritms that can make reasonably strong encryption on a classical computer that can withstand an attack from a quantum computer, but we'll need that to be reasonably safe while we're waiting for quantum computers to be widespread enough for everybody to use. Anybody know of efforts in this regard?

  • Assuming that during the 50's era, we were just getting electronics on a large scale to do the same thing, I give this tech about 20-30 years to really take off and become the norm.

    • Re:Almost There (Score:2, Insightful)

      by kesuki ( 321456 )
      20-30 years is about right. AT&T proved the posibility of optical computing I can't remember the exact year but It was somewhere between 1980 and 1997. How long after that did it take for galium-arsenide optical processors to get put into DVD-rom drives. Anyways, I full well expect the Playstation 7 or the Xbox 5 to be using quantum-computers so that those 3-d games can be played with some kinda full immersion system with real physics. At the rate we're going now we won't need encryption, since noone outside the NSA or the FBI or the military will be allowed to use it. In fact it will probably be illegal to choose an operating system or modify any hardware device purchased.

  • similar has been done before (Score:3, Interesting)

    by Phork ( 74706 ) on Wednesday December 19, 2001 @09:13PM (#2729738) Homepage
    2 years back i heard someone(i belive it was bruse schneir), say that the NSA or los alamos had built a quanum computer, and it could factor the number 7, down to 1 and 7, not to hard. but still an impressive feat.

    • Los Alamos and "federal researchers" (Score:3, Informative)

      by Anonymous Coward
      Los Alamos built a three-qubit quantum computer a while back. I don't have references, except a few mentions in other news articles. Sorry.

      But in March of 2000, a group claimed to have built a 7-qubit quantum computer. It's based on some different techniques than previously used, but the researcher said that the techniques can't go past 15 qubits. Check it out at:

      http://www.wired.com/news/technology/0,1282,3512 1, 00.html

  • OS (Score:3, Funny)

    by geekoid ( 135745 ) <dadinportlandNO@SPAMyahoo.com> on Wednesday December 19, 2001 @09:16PM (#2729748) Homepage Journal
    Now all I need to do is write a proprietary OS for it, and convince IBM to let me keep the rights!

    I'm thinking of calling my company "Quantumsoft"

    And my software would be able to slow the quantum computer to a crawl!

    • Re:OS (Score:2, Funny)

      by mj01nir ( 153067 )
      Now all I need to do is write a proprietary OS for it, and convince IBM to let me keep the rights!

      Write your own? Who the hell would do that? Just buy someone else's, slap your label on it, and then start bundling everything under the sun along with it.

      So you want 1,000 copies of the Quantumsoft Ion OS? OK, we'll give you a great deal if you also buy 1,000 copies of Quantumsoft Cubix office suite and 1,000 copies of Quantumsoft Visual Q++.
  • So, what happens if you ask it to factor a prime? Does it explode? ;-)
  • IBM chemists designed and made a new molecule that has seven nuclear spins -- the nuclei of five fluorine and two carbon atoms -- which can interact with each other as qubits,

    If they had to hand-craft a molecule to factor the number 15, it would seem that quantum computing would have to be very specialized. Do they have any schemes for creating a general purpose quantum CPU?

    • I don't think the point was that this molecule could only factor 15 (well, maybe, but read on). The point is that they needed to make a molecule with 7 atoms that could interact in a certain way. To do bigger problems, they will need to design a molecular structure that fits many more atoms together. However, that structure will be able to solve *any* problems possible within its capacity.

  • still a long way to go... (Score:4, Insightful)

    by dummkopf ( 538393 ) on Wednesday December 19, 2001 @09:21PM (#2729772) Homepage
    even though we can factor 15 == 3*5, we are still far away from useful quantum computer applications. the problem is that the coherence time of the atoms is fairly short and only O(10^3) computations can be performed before the system is decoherent. there are many interesting (but rather technical) papers about this subject and how to build quantum computers with quantum dots or any other solid state devices. you can get a glimpse of what is going on at the front of physics at http://xxx.lanl.gov/ [lanl.gov]. just search for quantum+computing...

  • anyone got a patch... (Score:3, Funny)

    by merlyn ( 9918 ) on Wednesday December 19, 2001 @09:23PM (#2729775) Homepage Journal
    ... for GnuPG to have 100000 bit keys? Quickly?

  • but... (Score:1, Funny)

    by klocwerk ( 48514 )
    What kind of tea did they use????

  • IBM's largest computer ever (Score:4, Funny)

    by charon_on_acheron ( 519983 ) on Wednesday December 19, 2001 @09:24PM (#2729781) Homepage
    From the Yahoo article:
    "Previously the largest computer IBM had built was based on five atoms."

    So what about the 2 ton behemoths everyone's been buying for years? ;-)

  • An Introduction... (Score:5, Informative)

    by GFish4 ( 449161 ) on Wednesday December 19, 2001 @09:25PM (#2729786)
    My brother found this for me not too long ago. The math involved can get rather intense, but I think it 's worth pointing out:

    An Introduction to to Quantum Computing for Non-Physicists [lanl.gov] - Available in PDF, PostScript, and others.

    If you do a google search, you probably can find it elsewhere, also.

    --GFish4

  • Crud! (Score:5, Funny)

    by Pathos78 ( 398591 ) on Wednesday December 19, 2001 @09:25PM (#2729789)
    And I thought my 4-bit key's were safe!
    Damn the relentless progress of computing!

  • My boss says ... (Score:3, Funny)

    by benedict ( 9959 ) on Wednesday December 19, 2001 @09:34PM (#2729827)
    ... "They should have asked me to do it. They could
    have saved a lot of money."

  • Question (Score:2, Interesting)

    by stapedium ( 228055 )
    I'm not a computer scientist, so for us lay people interested in cryptography, which methods could this compromise?

    I am guessing it would only be those which use factoring large numbers as their "hard" problem. Right? Obviously RSA style public key based encryption is in danger, but that just means I need to find a secure channel to exchange keys.

    What implications does this have for things like IDEA or even Xoring with a big chunk of random data?
    • IDEA

      It probably suffers from the same problems.

      or even Xoring with a big chunk of random data?

      This is known as a one-time pad (where the key is the same length as the message), and it's unbreakable (not just hard to break). Of course, it's also difficult to exchange these keys.

  • Unfortunately NMR quantum computing has limits (Score:4, Insightful)

    by Spooky Possum ( 80044 ) on Wednesday December 19, 2001 @09:44PM (#2729861)
    The technique used here (NMR) is probably the best understood way of doing quantum computing (a lot of the basics are dragged straight out of medical imaging technology). Unfortunately it has a very fundamental limitation: the initialisation phase scales exponentially. Everything else is practical, but for every qubit you add you need to add exponentially more molecules to your system. Since you start off with a "billion billion" molecules you get a good head start, but systems much beyond seven qubits become very difficult and anything practical is impossible.

    Of course almost all current quantum computing schemes have fatal flaws and NMR is well ahead of everyone else (with the possible exception of ion trapping). However in most other schemes the flaws aren't fundamental (just really, really, difficult to fix).

    Disclosure: I have worked on a competing quantum computing scheme (neutral atoms). It's crap too.

    • Re:Unfortunately NMR quantum computing has limits (Score:4, Informative)

      by nihilogos ( 87025 ) on Wednesday December 19, 2001 @11:59PM (#2730305)
      Actually one of the flaws in NMR quantum computation is that the signal strength used for measurement decreases exponetially with the addition of more qubits. That's pretty fundamental.

  • Meow (Score:5, Funny)

    by KarmaBlackballed ( 222917 ) on Wednesday December 19, 2001 @09:46PM (#2729868) Homepage Journal
    If you put a cat inside this computer, will it die?

  • Another article at News.com (Score:4, Informative)

    by A Commentor ( 459578 ) on Wednesday December 19, 2001 @09:53PM (#2729890) Homepage
    It's also discussed at news.com [cnet.com].

  • You Heard It Here First... (Score:5, Insightful)

    by cybrpnk ( 94636 ) on Wednesday December 19, 2001 @09:59PM (#2729907)
    Looks like the number of qbits available in a quantum computer is doubling every 18 months. The article notes the 2 qbit computer was built in 1998, the 4 qbit unit in August 2000 and now a 7 qbit computer in December 2001....they've still got another couple of months to get the 8th qbit....

  • Almost there! (Score:5, Funny)

    by Black Parrot ( 19622 ) on Wednesday December 19, 2001 @10:00PM (#2729914)

    7 Qbits already? That's great! No one should ever need more than 640 Qbits.

  • The End of Asymmetric Key Distribution (Score:3)

    by Muerte23 ( 178626 ) on Wednesday December 19, 2001 @10:12PM (#2729947) Journal
    As probably most people here realize, the advent of sufficiently strong quantum computers renders obsolete every encryption scheme. Except, of course, then Verdam cypher or One Time Pad.

    At JPL, among, there is a group working on quantum key distribution. The aim is to have entanged photons distributed at the same rate (or almost the same rate) as the data, and to use this as a crypto key that is totally unbreakable. Untappable, unbreakable, impervious.

    Doesn't it strike anyone as strange and cool that quantum computers and quantum key distribution are coming to fruition at almost exactly the same time?

    muerte

    • not true (Score:3, Informative)

      by phr1 ( 211689 )
      Quantum computing could conceivably obsolete public key (asymmetric) cryptography. However it doesn't break conventional cryptography. A sufficiently strong quantum computer can turn an O(f(n)) computation into O(f(sqrt(n)) but that's all. For example, it could break a 56-bit key in 2**28 steps instead of 2**56 steps. That means 128-bit keys could conceivably be broken by quantum computers (in 2**64 steps). However, by doubling the key length (say to 256 bits) you get the security against quantum computers that you now get against conventional computers.

      • Re:not true (Score:2, Informative)

        by Miriku chan ( 168612 )
        this is incorrect. a quantum computer can take a task thats usually O(c^n) into a O(n). this is a HUGE HUGE difference.

      • Actually it is true (Score:2, Informative)

        by Anonymous Coward
        Actually, Shor's algorithm takes a O(e^N) algorithm on a classical computer (factoring into primes) and reduces it to a O(N^2)algorithm, so not only does it reduce an exponetial order algorithm to a polynomial algorithm, which is already achieving the holy grail of computing computationally hard problems, but does so in spades. Essentially, if QC's can scale to the number of bits required and operate at any decent clock speed (more on this in a bit) then RSA will go the way of the dodo. So will every other encryption scheme that I know of that is based on a computationally hard to compute key that a QC algorithm can be written for. (BTW, Shor also created an effcient O(N^4) algorithm for the discreet log, which is also used in some encryption schemes, or so I am told).

        Granted I am not a security/encrytion expert, so your statement about this only being effective for assymetric encrytion schemes may be correct if conventially encryption is not based on a hard key, but I thought that all encryption was based on hard keys (BTW, isn't cryptography the creation of a code to hide/diguise the data, as opposed to encrypting it with a function?).

        With regard to "clock" speed (There is no fundamental reason a QC needs to be clocked, but for the sake of simplicity let's say it is), NMR states are, I think, stable on the order of milliseconds, so maybe the computer could "clock" several hundred computations per second. It would still take awhile to do several million comps, or about how many comps will be required to factor something on the order of 10^25 with Shor's algorithm, but timewise that's on the order of months, not the known age of the universe like it would be for a regular computer (figures are from memory, and are meant to illustrate the orders of magnitude involved, not necessarily be completely accurate).

        Granted this is all a guesstimate, but I think a pretty conservative one.

        Someone else quoted rate of ~ O(10^3) computations before decoherence. A QC is probablistic, which means that you run it over and over under an interation produces the correct result. The chance of getting an incorrect answer decreases with each iteration. Shor's algorithm takes either 3 or 4 computations (defined in a QC as a evolution of the wave state) per iteration. I may be a little off here, it's been awhile, but it's definitely around that so if that quote is acurrate, decoherence is no problem, at least for the quoted setup. It also, assuming a decoherence time on the order of ms, appears to be faster than my above guess.

        Essentially, even if QC's can't crack various keys in realtime, they could make key generation/distribution a real pain in the ass and essentially end the era of uncrackable encryption (unless of course it is quantum encryption which is in theory uncrackable, but I know alot less about that)

        Does anyone have any data on how many comps/sec various qubit models can handle? I'd like to see if my guess was close:)
    • Your assertion that quantum computers would be the end of conventional cryptography is incorrect. While it's true that Shor's algorithm would enable you to break RSA and other public key cryptosystems such as DSS and ElGamal, the impact of quantum computers on conventional symmetric cyphers (such as, e.g., AES) is understood and limited.

      Namely, Grover's algorithm would enable you to brute force a symmetric key of size N in O(exp(N/2)) time rather than the current O(exp(N)) time.

      In other words, if quantum computers (even with very large number of qubits) are built, today's public key cryptosystems would no longer be secure, but today's symmetric cyphers would simply need to have their key length doubled to keep the same rough level of security.

    • a crypto key that is totally unbreakable. Untappable, unbreakable, impervious.

      And how exactly is it that quantum key distribution is supposed to protect us from the classic and proven man-in-the-middle attack?
      • The whole point of quantum encryption (which is completely a different process than quantum computing) is that observing the quantum causes the quantum to change. Therefore, the man in the middle will disrupt the transmission and be detected instantly.

        Quantum encryption, when used correctly, is really truly mathematically proven to be unbreakable by any means.
        • The whole point of quantum encryption (which is completely a different process than quantum computing) is that observing the quantum causes the quantum to change. Therefore, the man in the middle will disrupt the transmission and be detected instantly.

          I suggest checking the literature a little more closely. A man in the middle will not disrupt the transmission, because a man in the middle is not an eavesdropper, he's pretending to be both ends of the link at once. Person A tries to communicate with person B, and establishes a secure link, but really, the secure uncrackable link is with person C standing in the middle, and person C then establishes a secure uncrackable link with person B. The problem then becomes, how does person A know that it's REALLY person B that a secure communication has been established with, and vice versa.

          Preventing a man-in-the-middle attack requires authentication, not secure communication. And when it comes down to it, encryption without authentication is almost useless, because man-in-the-middle attacks are not really that difficult to pull off. Classically, authentication is typically done with the existence of some sort of one-way hash function. I don't know if any hash functions are going to survive the dawn of the quantum computing age.

  • Old news (Score:5, Funny)

    by sharkey ( 16670 ) on Wednesday December 19, 2001 @11:07PM (#2730169)
    7 qubits!?!? Sheesh, Noah's Ark was 300 qubits long, by 50 wide, by 30 high. And seven is supposed to be impressive thousands of years later?
  • We need to begin considering a form of cryptography that's relatively immune to quantum computing technology!

    I dearly love SSH, but if it's based on inherently transparent (to quantum computers) mathematics, it's worthless - perhaps worse, since I trust it.

    We need to begin considering this problem NOW, before the privacy of just about everybody is opened up to the whim of somebody with enough money to buy a quantum computer!

    There will definitely be, as Quantum computing hits mainstream in the next 5-15 years, a co-existence period - like twilight, the period of greatest danger, when the world of computing is based neither entirely on binary or quantum systems - and we're heading for that with momumental speed.

  • Stockpiling emails (Score:2, Insightful)

    by shimmin ( 469139 )
    Let's assume that at some point in the next couple decades, an evesdropper with a sufficiently large budget can build a device that will efficiently crack factoring-based keys.

    Unfortunately, that means people using factoring-based keys are in trouble today, because an adversary with a sufficiently large budget (and sufficent access to certain routers) could stockpile a rather large portion of Internet traffic for cracking at such time that it becomes feasible to do so.

    Evidence and paranoia leads one to suspect certain parties do evesdrop on a certain fraction of email, particularly email sent across international cables. If such email is already being filtered for certain keywords, how much harder is it to filter it for apparently encrypted email and shelve it for later use?

  • That's a very impressive result. IBM Almaden does some great physics.

    A friend of mine there says their employee evaluation system has three ratings: "OK", "Not OK", and "Nobel Prize". He's only partly kidding; they have several Nobel laureates on staff.


  • IBM announcement - in history section:
    "But in 1994, Peter Shor of AT&T Research described a specific quantum algorithm for factoring large numbers exponentially faster than conventional computers -- fast enough to defeat the security of many public-key cryptosystems. The potential of Shor's algorithm stimulated many scientists to work toward realizing the quantum computers' potential. Significant progress has been made in recent years by numerous research groups around the world."

    Maybe Magic Lantern isn't needed, and maybe the feds should be more concerned about quantum scientist as the next great public threat? Lets' see now... Hacker used to be a positive connotation.....how to turn Quantum into a negitive connotation...or is ther another name by which these scientists go by?
  • Just out of interest, does anybody know:

    given that a quantum computer could factorise a number N into factors a1, a2, a3,...etc in a defined time, we can therefore tell whether N is prime by seeing if it returns a1=1, a2=N.

    Would it be possible to build a 'super' quantum computer which checks simultaneously all numbers from 0 -> 2^n (where n is the number of qbits) and returns only those which are prime.

    In other words, you would be carrying out 2^n computations simultaneously, each of which is comprised of 2^n computations ?

  • "phr1 writes "IBM has announced and Yahoo has noted that the first working implementation of Shor's factoring algorithm."

    [grammarnazi]

    Apparently, phr1 does not need to use.

    Complete sentences. =P

    Either that or get rid of the "that".

    [clicks jackboots, /grammarnazi]

    -Kasreyn
  • A nice audio cast by Unix guru Rob Pike can be found here:

    http://www.technetcast.com/tnc_play_stream.html?st ream_id=310 [technetcast.com]

    Check the slides too at:

    http://cm.bell-labs.com/who/rob/qcintro.pdf [bell-labs.com]

    Regards,
    Marc

Slashdot Top Deals

Love may laugh at locksmiths, but he has a profound respect for money bags. -- Sidney Paternoster, "The Folly of the Wise"

Close