Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 


Forgot your password?
Close
typodupeerror
×
News Hardware

Quantum Computing Breakthrough in Japan 438

Posted by CowboyNeal from the another-step-closer dept.
An anonymous reader writes "A research team funded by NEC and RIKEN, Japan's Institute of Physical and Chemical Research, are the first to demonstrate a Controlled NOT (CNOT) quantum gate. The CNOT gate when coupled with a rotational gate would create a universal gate. The universal gate would be the basis for quantum computing. ETA for the first quantum computers: 10 to 100 years." When quantum computers first come to fruition, the best part will be reminiscing about how terrible computers were "back in the day."
This discussion has been archived. No new comments can be posted.

Quantum Computing Breakthrough in Japan More

Quantum Computing Breakthrough in Japan

Comments Filter:

  • A couple of Thoughts (Score:4, Funny)

    by ericspinder ( 146776 ) on Friday October 31, 2003 @12:04AM (#7355028) Journal
    With that much computer power.
    • So much for 128 bit encryption or 512, etc
    • SETI would run out of signals to process
    If you crash your quantum computer would you rip a hole in the space-time continum. Maybe that is how black holes get started; one for every planet that just gets to this point and then loads Windows on a quantum computer.

    • Re:A couple of Thoughts (Score:5, Funny)

      by Anonymous Coward on Friday October 31, 2003 @12:10AM (#7355079)
      This black hole brought to you by Microsoft!

      "And you thought we sucked before!"

      --
      actually, no. the universe doesnt crash.. least not yet..

    • No more encryption? (Score:5, Interesting)

      by Rimbo ( 139781 ) <rimbosity@sbcglo[ ].net ['bal' in gap]> on Friday October 31, 2003 @12:13AM (#7355110) Homepage Journal
      I think that modern encryption schemes could be broken really quickly.

      Imagine what kind of encryption you could do with quantum computing. When the first computers were built, most of the standard methods of encryption became obsolete -- ones that usually involved simple letter-substitution. That wasn't the end of encryption; those same computers enabled new ways to encrypt messages.

      So it stands to reason that the existence of quantum computers would lead to new quantum encryption methods, which would take millions of years for the best quantum computers to crack using brute-force.
      • I do believe the article said they will be available in 10-100 years. If was a betting man I'd say it will take at least 40 years. By that time 512 encryption will be useless. At some point we'll be referring to encryption in scientific notation ala 10e32.

      • Re:No more encryption? (Score:5, Informative)

        by ultitool ( 319277 ) on Friday October 31, 2003 @12:43AM (#7355296)
        Modern schemes wouldn't be necessary because quantum cryptography would become the standard and is proven to be unbreakable by the laws of quantum mechanics. Any interaction (malicious or otherwise) of a third party is noticable to the proper parties and the message/key transmission is just repeated until a clean send is achieved.
        Here [csa.com], here [dartmouth.edu] and google (of course) [google.com] provide some good reading if you're interested

        • Re:No more encryption? (Score:5, Insightful)

          by roystgnr ( 4015 ) <roy&stogners,org> on Friday October 31, 2003 @01:18AM (#7355450) Homepage
          Modern schemes wouldn't be necessary because quantum cryptography would become the standard and is proven to be unbreakable by the laws of quantum mechanics.

          Doesn't quantum cryptography require a point to point optic channel capable of successfully transmitting individual photons without interfering with their polarization (as well as detectors and receivers for such)? Even if people get fiber optic lines to their homes in the next few decades, I'm pretty sure we'll never see anything like that available to home users. If you want unbreakable cryptography today, you can use a one time pad with less inconvenience.

      • Re:No more encryption? (Score:3, Informative)

        by 222 ( 551054 )
        You shouldnt confuse quantum computing with quantum cryptography. Quantum cryptography, even with a quantum computer, would still be unbreakable because of how it utilizes the randomness of photons, one time pads, and one hell of an anti-easedropping mechanism.
        Quantum computing would also have a far more severe impact on modern cryptography than breaking it "really quickly". With the ability to instantly factor every large prime, for example, it would nullify the best we've got.

      • Re:No more encryption? (Score:3, Interesting)

        by kidlinux ( 2550 )
        Consider the amount of encrypted data currently in existance. Once quantum computers come about, access to all of this data would be trivial.

        I imagine there are governments which are just frothing at the mouth over quantum computers. They'd have access to hordes of encrypted data that they've no doubt been saving for just such an occasion.

        And until everyone has a quantum computer, not all data will be securely encryptable.

    • "Maybe that is how black holes get started; one for every planet that just gets to this point and then loads Windows on a quantum computer."

      Funny? Well, I suppose there are still a few people left who chuckle at Lewinski.

    • If you can do quantum computing ... (Score:5, Informative)

      by vlad_petric ( 94134 ) on Friday October 31, 2003 @01:56AM (#7355651) Homepage
      Then you can probably do quantum cryptography as well. Quantum cryptography has the nice property that an evesdropper cannot intercept the message without destroying it.

      Anyway, RSA can be broken by factorization. Diffie-Hellman however requires the inversion of the discrete exponential function. While quantum computing can factorize in P-time, it cannot inverse an arbitrary function in a reasonable amount of time. It can do it more efficiently than a normal computer (2^(k/2) time as opposed to 2^k with Lov Grover's search algorithm, where k is the number of bits), but it's still exponential.

      In any case, I wouldn't worry yet ... Shor's algorithm, for 512 bits, requires in the order of tens of thousands qubits (with realistic quantum error correction). So far the highest number of qubits that were put together is around 10.

      • Then you can probably do quantum cryptography as well. Quantum cryptography has the nice property that an evesdropper cannot intercept the message without destroying it.

        As others have pointed out, these are two different problems. We can do Quantum cryptography TODAY. We can do it about as cheaply now as we will 100 years from now. The most expensive part of the process is running a fiber optic cable directly between the sender and receiver. Somehow I don't see that happening on the battlefield...

        Un

      • Re:If you can do quantum computing ... (Score:3, Informative)

        by Anonymous Coward
        Diffie-Hellman however requires the inversion of the discrete exponential function.

        Which you can also solve very well on a QC. Schor also proposed a (less famous) algorithm for this, or more exactly, for computing the discrete logarithm (which is a sufficent condition to break diffie hellman, but which is not even proven to be necessary...). Actually it was in the same paper.

        So you do not need to use grover to speed up brute force. Even on a classical setting there are better ways to compute discrete log
  • the best part will be reminiscing about how terrible computers were "back in the day."

    I'm not so sure. Computers these days can do things like play mp3s and movies, etc(browse porn), these sort of activities I'm sure we'll be doing 10 years from now, computers will still be useful a decade in the future. Of course, this is provided that all the cheap junk that is made now will still WORK 10 years from now...
    • Of course, this is provided that all the cheap junk that is made now will still WORK 10 years from now...

      My little 486 is pushing on 10 years now, and it's done a fine job, showing no signs of collapsing soon. Assuming it was made of the same quality as an XT PC which still runs, I should be able to get another 10 years out of that. Meanwhile I change everything around in my main boxen every 8 months or so, or whenever the next architecture change is.
    • Provided I replace the DVD-ROM when the original fails, I expect my XBox to still be working in ten years. Even more amusing is that I will likely still be using it, though by then it might not be in its original case.
    • I question the 10-100 year estimate... I'd almost lean toward the lower end. According to this source [theindianprogrammer.com] (which seems consistent with others I have seen) Quantum Computing was first conceived in 1982, published in 1985, and research didn't really get underway commercially until the early to mid 1990's. That means that we have come this far (early stage working components) in about 10 years. And pace on this type of thing typically gets faster.

      I think it would be reasonable to say we could have a working p
  • But that's really neither here nor there.

  • What is going to run on these computers? (Score:4, Interesting)

    by Apoptosis66 ( 572145 ) on Friday October 31, 2003 @12:06AM (#7355043)
    We are already hitting the limits of how much code can work together without being riddled by bugs. I think we need a advance in programming first.

  • Quantum Computers (Score:3, Insightful)

    by Henry V .009 ( 518000 ) on Friday October 31, 2003 @12:12AM (#7355105) Journal
    Quantum! The name does sound kind of cool. But try programming for one for a little while. That is something that you can do today with a simulator.

    The only use for quantum computers in the future will be cryptography and very specially formulated problems. It won't run Quake VII or Windows 2015.

    (Then again, if you chart processor and memory usage, you will find that nothing will run Windows 2015)

  • Is it just me, or in the last few years (as a result of AMD vs Intel perhaps?) that hardware has generally outpaced software.

    Sure, a lot of us (myself included) want the "bleeding edge" system, but in reality, even my (now three year old) AMD 750 is still a decent enough system. Whereas I recall "back in the day" being worried about system requirements everytime I bought a piece of software -- only six or nine months after I bought my first PC (a 486DX-4 100).

    Does anyone see software catching up (in the

  • The Reason Progress Is So Slow (Score:5, Funny)

    by Myriad ( 89793 ) <myriad@the[ ]d.com ['bso' in gap]> on Friday October 31, 2003 @12:16AM (#7355129) Homepage
    The real reason why the development of quantum computers is going so slow is pretty simple: everytime they check on their progress they lose the damned thing!

    (with appologies to Mr. Heisenberg)

    Blockwars [blockwars.com]: realtime, multiplayer, and free!

    • The real reason why the development of quantum computers is going so slow is pretty simple: everytime they check on their progress they lose the damned thing!

      I thought it was because they can't know both when and what it will be.

  • Factoring in the effects of computational advances (Score:5, Funny)

    by HalfFlat ( 121672 ) on Friday October 31, 2003 @12:20AM (#7355158)

    From the article,

    That means calculations, such as working out the factors of prime numbers, which present problems for even the fastest supercomputers could be trivialized by a quantum computer.

    Once they get prime numbers licked, they'll move on to the composite ones. To live in such heady times!

    • "That means calculations, such as working out the factors of prime numbers, which present problems for even the fastest supercomputers could be trivialized by a quantum computer."

      The new quantum computer will sport real live emotions! For example, once presented with the task of working out the factors of prime numbrs, the quantum computer responded with "bah, who cares? It's just a bunch of 1s and 0s."
  • the best part will be reminiscing about how terrible computers were "back in the day

    ...as we toil in the silicon mines of our quantum computing overlords.
  • and now I can post from anywhere and anytime, cool!

    In your future, there will be some natural disastors and war. the good news is, Bush will only be emperor for 20 years! wait, did that happen yet?

  • What if .... (Score:4, Interesting)

    by 2Bits ( 167227 ) on Friday October 31, 2003 @12:33AM (#7355234)
    What if we really achieve breakthrough and can really make usable quantum computers, while we still couldn't break through the math bottleneck, and all crypto suddenly become irrelevant?

    Now we have a computer that can break all crypto, and we have no new crytpo algo that would make even a quantum computer crack for millions of years, would the governments in the world allow manufacturing of such a beast?
  • "The universal gate would be the basis for quantum computing. "

    What would a universal gate do to the theory of a closed universe?

  • I have a quantum computer too.. (Score:5, Funny)

    by Epistax ( 544591 ) <epistax@g[ ]l.com ['mai' in gap]> on Friday October 31, 2003 @12:33AM (#7355238) Journal
    I don't know where it is, but it's moving at exactly 3.65 m/s.

  • The Nintendo Game Qubit. (Score:3, Funny)

    by NanoGator ( 522640 ) on Friday October 31, 2003 @12:35AM (#7355249) Homepage Journal
    "ETA for the first quantum computers: 10 to 100 years."

    I predict Duke Nukem Forever will be a launch title for the Nintendo Game Qubit.
  • The very first thing I would do if I had a quantum computer is to crack the XBOX key. (I assume I am not alone here)

    So, wouldn't quantum computers altogether be banned under DMCA?

  • They're fixing them? (Score:5, Funny)

    by The Munger ( 695154 ) on Friday October 31, 2003 @12:37AM (#7355264) Homepage
    When quantum computers first come to fruition, the best part will be reminiscing about how terrible computers were "back in the day."

    No, they'll still be terrible. They'll just be terrible really quickly.

  • speaking of OTPs (Score:2, Interesting)

    by Shakrai ( 717556 )

    Has anyone ever implemented one for a VPN? I had considered writing a quick one, mainly for the time honored reason of "Because we can", but in all seriousness, with DVD-Rs why isn't this feasible (assuming you can make a safe exchange of the media). 4 gigs is a _lot_ of data (hell, even an old fashion CD-R at 700 megs is). You could even get further mileage out of it by compressing the data before you encrypted it. Creating the code itself is child's play -- that's the beauty of OTPs.

    What's the best w

    • Re:speaking of OTPs (Score:3, Informative)

      by rusty0101 ( 565565 )
      One of the problems they have found with radio noise is that if you take your samples too close together you get too many strings of either 1111, 0000, or 10101010. While all three of these strings, as well as many of the permutations are perfectly normal as part of a truely random process, it doesn't do much for your encryption process if you xor your raw text with a string of zeros.

      The problem with most algorythmic random number generators is that if you can collect enough samples you can figure out what
      • The problem with most algorythmic random number generators is that if you can collect enough samples you can figure out what function created those samples, and reproduce the original OTP and decrypt the original message.

        Yes, but with a decent strong pseudo-random number generator, this is equivalent to breaking the crypto algorithm they're based on. Consider even the most basic counter-mode cipher, where output block n is e_k(n), where k is the secret key. Predicting the next output from a bunch of da

  • Some facts about Quantum Computing (Score:5, Informative)

    by vlad_petric ( 94134 ) on Friday October 31, 2003 @12:41AM (#7355288) Homepage
    CNOT has been done before. IBM in fact has demonstrated Shor's algorithm on 15 (the smallest number that can be factorized with that algorithm). This required 7 qubits.

    In a regular computer, data flows through "static" gates. In a quantum computer, the data (qubits) is stationary and the "gates" are in fact carefully crafted laser pulses (the article is not very specific about this particular CNOT gate though)

    1-2 qubits is easy. More qubits are quite difficult to put together. That's why most of the current quantum computers barely do 10 qubits.

    Errors are of analogical nature. Correcting them (with Q-ECC codes) is quite expensive - a more reliable qubit requires a couple normal qubits and gates (I say more reliable because the whole thing is probabilistic)

    Quantum data is very "transient" - it cannot be copied. It can be teleported however (teleportation destroys the source). Storage is however difficult (keeping a superposition of qubits coherent for humanly-observable times is almost intractable)

    A quantum computer can do an operation on 2^k superpositions at the same time (in other words, exponential work in constant time). Selecting the "right" answer from the superposition of 2^k results takes however 2^(k/2) (Lov Grover's algorithm) - so it's still exponential. This is one of the reasons quantum computers were not shown to be more powerful than regular ones (i.e QP != P) . Yes, Shor's factorization algorithm works in polynomial time on quantum computers, and is furthermore quite efficient, but factorization has been shown to be in P anyway (although the current "regular" algorithm is not efficient at all)

    • IAAQCR (I Am A Quantum Computation Researcher) (Score:5, Informative)

      by bifurcation ( 152542 ) on Friday October 31, 2003 @01:23AM (#7355470)
      Some very apt points, but I'd like to make a couple of corrections:
      IBM in fact has demonstrated Shor's algorithm
      I'm not certain that IBM hasn't done something similar, but I believe that the work you're referring to is an experiment at Los Alamos [arxiv.org] which used Nuclear Magnetic Resonance and lasers to manipulate nuclear spins as qubits.
      ... the "gates" are in fact carefully crafted laser pulses ...
      Again, this is true in the Los Alamose experiment, but in general, gates can take on a bunch of different forms. In an NMR system, pulsed lasers are gates; in optical systems [univie.ac.at], things beam splitters and phase shifters (and the qubits do travel between gates); in solid-state systems, different electric fields are used to manipulate states.

    • Re:Some facts about Quantum Computing (Score:5, Informative)

      by dirtydamo ( 160364 ) on Friday October 31, 2003 @01:28AM (#7355496)
      Shor's factorization algorithm works in polynomial time on quantum computers, and is furthermore quite efficient, but factorization has been shown to be in P anyway (although the current "regular" algorithm is not efficient at all)

      No, factorization has NOT been shown to be in P (or at least, I have never heard of this -- care to give references)?

      Primality proving was recently shown to be in P, but that is a much easier problem.

    • Last I checked, the best algorithms for factoring were still in NP; otherwise public key encryption would never be trusted for anything.

      For that matter, the same algorithm, with very little change, also solves the discrete log problem and the hidden subgroup problem in polynomial time.

      As for quantum data being "transient," it is true that most of the quantum information systems have decoherence problems. But, if memory serves, there are some with coherence times that can be measured in seconds. With ref
  • I don't think these guys are the first to demonstrate a CNOT gate, contrary to what the headline implies. This is just the first implementation of a CNOT gate in a _solid-state_ quantum computation device - not having followed this particular area, I can't say whether this was an incremental, and expected development, or a real "breakthrough". But it's nice to finally see people pursuing something other than using bigger, bulkier molecules in jerry-rigged NMR machines, which might actually scale to enough

    • Re:Err, no... (Score:3, Insightful)

      by Neurotensor ( 569035 )
      Not only that but they probably aren't the first to demonstrate in a solid either.

      I worked in a lab that already did that late last year, in the Laser Physics Centre, ANU, as evidenced by a recent PhD thesis by Jevon Longdell, and many conference presentations. Although technically it was a controlled-phase gate, but they are functionally equivalent anyway.

      Unfortunately writing papers takes a back seat to doing the work, so in the wider field few people know about it. It sucks to watch it happen.
  • Just think if one day you walk into a computer store and see the 100Ghz Intel system running Windows 2015 and next to it you have your quantum computer running bochs in linux, simulating 100 100Ghz intel computers.

  • All the awesome power -- (Score:3, Funny)

    by Chromodromic ( 668389 ) on Friday October 31, 2003 @02:23AM (#7355785)

    -- And Emacs will still be slower than Vim.

  • ETA (Score:3, Funny)

    by Jace of Fuse! ( 72042 ) on Friday October 31, 2003 @03:01AM (#7355941) Homepage
    ETA for the first quantum computers: 10 to 100 years.

    10 to 100, is it? I guess since we're talking about Quantum, we'll take this a step further and say "They may or may not actually release a computer."

    Or is it that they will AND they won't?

  • The Details (Score:3, Insightful)

    by TheSync ( 5291 ) on Friday October 31, 2003 @03:42AM (#7356037) Journal
    The interesting thing about this method is that it is solid-state rather than some concoction of lasers and ultra-cold gasses.

    Demonstration of conditional gate operation using superconducting charge qubits

    T. YAMAMOTO1,2, YU. A. PASHKIN2,*, O. ASTAFIEV2, Y. NAKAMURA1,2 & J. S. TSAI1,2

    1 NEC Fundamental Research Laboratories, Tsukuba, Ibaraki 305-8501, Japan
    2 The Institute of Physical and Chemical Research (RIKEN), Wako, Saitama 351-0198, Japan
    * Permanent address: Lebedev Physical Institute, Moscow 117924, Russia

    Correspondence and requests for materials should be addressed to T.Y. (yamamoto@frl.cl.nec.co.jp).

    Following the demonstration of coherent control of the quantum state of a superconducting charge qubit, a variety of qubits based on Josephson junctions have been implemented. Although such solid-state devices are not currently as advanced as microscopic qubits based on nuclear magnetic resonance and ion trap technologies, the potential scalability of the former systems--together with progress in their coherence times and read-out schemes--makes them strong candidates for the building block of a quantum computer. Recently, coherent oscillations and microwave spectroscopy of capacitively coupled superconducting qubits have been reported; the next challenging step towards quantum computation is the realization of logic gates. Here we demonstrate conditional gate operation using a pair of coupled superconducting charge qubits. Using a pulse technique, we prepare different input states and show that their amplitude can be transformed by controlled-NOT (C-NOT) gate operation, although the phase evolution during the gate operation remains to be clarified...

  • Not the first (Score:3, Interesting)

    by Anonymous Coward on Friday October 31, 2003 @04:53AM (#7356218)
    This is not the first controlled not gate. Controlled not operations have been implemented in quantum optical systems for a few years now. The problem with quantum optics is that you cannot make the systems with lithography.

    As they say in the article, it is the first controlled not quantum gate in a solid state device.
    It is very important to make that distinction, since quantum optical systems have much less decoherence then solid state devices, which makes them a better candidate from a fundamental point of view. Combining that with the electronic-optical hybrid chip that was discussed in a posting here a few days ago, I think that you cannot rule out the possibility that quantum computers will be implemented in such hybrid systems as well.

  • Security Implications (Score:3, Informative)

    by eddeye ( 85134 ) on Friday October 31, 2003 @05:34AM (#7356322)
    I'm currently taking a grad class on quantum computing at UC Davis. The technology is unbelievably fragile right now. There are huge hurdles to overcome before a non-trivial quantum computer is built. The security ramifications are blown way out of proportion. Consider:
    • Current architectures don't scale past about 7 qubits, which is barely enough to factor the number 15. Part of the problem is letting all the qubits in the system interact with each other. It's not even certain that a scaleable architecture can be developed.
    • The quantum state of the machines decays very quickly, requiring a lot of error corrections for sustainable calculations. It's not a given yet whether such architectures are possible.
    • Shor's algorithm is algorithmically faster than classical sieve methods for factoring numbers. However the constants involved are huge. No one knows where the curves cross yet (mainly because no one's built a large enough quantum computer to extrapolate from yet). It may require impossibly large numbers to benefit from Shor's speed advantage. I.e if Shor's is only faster than sieves on composites of 50,000+ bits, asymmetric crypto is safe.
    • Symmetric crypto will barely notice when/if quantum computers appear. Grover's may be able to effectively halve the key size for brute-force searches, but it's gonna be much, much slower than a classical computer on that reduced size. A 256-bit key would be at least as immune to brute-force from quantum computers as a 128-bit key is to conventional machines.
    • Quantum cryptography is a misnomer for the BB84 and BB92 protocols. These should be called quantum key distribution because that's all they do. You can't encrypt information with them, just exchange keys. You still need conventional crypto to use the keys with.
    • There are indications that the quantum world might provide equivalents to digital signatures and possibly other asymmetric crypto primitives. However like quantum key distribution it requires a dedicated quantum channel (e.g. a single fiber optic cable) between the two parties. It's gonna be expensive to setup.
    Basically, quantum computers and quantum cryptography will have little effect on the security world. Quantum crypto is only useful in ultra-paranoid, damn-the-expense applications (military, govt). Worse case scenario, the rest of the world has to give up asymmetric crypto and fall back on symmetric methods. Some infrastructure gets replaced and life goes on.

    I don't expect to see non-trivial quantum computers in the research lab for a minimum of 3 decades, though the professor sees them in 1.

  • Yeah, but besides encryption? (Score:3, Insightful)

    by osgeek ( 239988 ) on Friday October 31, 2003 @08:49AM (#7356851) Homepage Journal
    What good is a quantum computer for besides breaking encryption? It seems like that's the only problem-solving ability of quantum computers that is ever mentioned.

  • Quantum gates (Score:3, Funny)

    by RayBender ( 525745 ) on Friday October 31, 2003 @09:36AM (#7357071) Homepage

    I thought it had been shown that to make a quantum computer you needed the gates to be made of cats...

  • At the risk of sounding US-centric... (Score:3, Insightful)

    by KC7GR ( 473279 ) on Friday October 31, 2003 @12:39PM (#7359167) Homepage Journal
    I find it significant (and maybe a little alarming as well) that it was Japan, and not the U.S., who made this apparent breakthrough. To my eyes, although I would say "Congrats!" to the Japanese, it makes a pretty sad statement about how our own industrial base (read: large companies) values (or doesn't) heavy R&D and engineering.

    How much engineering and R&D has been "outsourced" or "downsized" in the past two decades, in favor of delivering short-term "Shareholder Value?"

    What happened to long-term survival and growth of a company vs. short-term profits? Just as two examples, Bell Labs is a pale shadow of what they once were, as is Boeing. How much further is it going to go before the U.S. is merely a mass "user" of the products that our "global partners" think up and turn out?

Slashdot Top Deals

The Tao is like a glob pattern: used but never used up. It is like the extern void: filled with infinite possibilities.

Close