![News News](http://a.fsdn.com/sd/topics/news_64.png)
![Hardware Hardware](http://a.fsdn.com/sd/topics/hardware_64.png)
Quantum Computing Breakthrough in Japan 438
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."
A couple of Thoughts (Score:4, Funny)
Re:A couple of Thoughts (Score:5, Funny)
"And you thought we sucked before!"
--
actually, no. the universe doesnt crash.. least not yet..
No more encryption? (Score:5, Interesting)
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.
Re:No more encryption? (Score:2)
Re:No more encryption? (Score:5, Informative)
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)
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)
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:5, Funny)
Nonsense! I can instantly factor every large prime--in my head!!
You can too.
--Tom
Re:No more encryption? (Score:3, Interesting)
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.
Re:A couple of Thoughts (Score:2)
Funny? Well, I suppose there are still a few people left who chuckle at Lewinski.
If you can do quantum computing ... (Score:5, Informative)
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.
Re:If you can do quantum computing ... (Score:3, Informative)
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)
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
Re:A couple of Thoughts (Score:5, Informative)
The availability of quantum computers for encryption cracking will just result in a change to another type of cryptography that does not rely on the unproven assumption that factorizing large integers is NP hard. These future encryption methods may be less mathematical and more physical.
Re:A couple of Thoughts (Score:2)
for instance it's already possible to use quantum interference to determine if the signal has been observed in transit.
Re:A couple of Thoughts (Score:2)
Re:A couple of Thoughts (Score:4, Interesting)
as long as a solution exists. not matter how improbable, it can be arrived at, as the gates in superposition go through all the possibilities simultaneously.
so, to my admittedly limited understanding, where brute forcing means it's statistically likely you'll crack conventional encryption after a certain limited number of iterations, and a certainty once you exhaust all the possibilities, unless the chance of brute forcing an OTP is exactly infinite then it's still going to be a snap to a machine that evaluates all states simultaneously.
But i don't pretend to have a deep understanding of the field.
So I promise not to get upset if someone now brutally demolishes my thinking
Re:A couple of Thoughts (Score:3, Informative)
Well that's the catch. Yeah, a solution exists, but it's impossible to know if you have found it. If you have a message of length N encoded with a one time pad, then any possible message of length N is an equally valid solution. So if I send a message where n is 23, it could be decoded as "We attack at one thirty" or I could be saying "The pizza was
Re:A couple of Thoughts (Score:5, Informative)
The key (no pun intended) here is that there is no way to know when you have the correct key. With the XOR example, there exist keys that will produce every possible combination of output bits, and no way to tell which one is right. So trying to decrypt it is no different than generating random bit patterns the length of the data and seeing which output "looks right" - even looking for outputs that are valid English, you will encounter every possible sentence of the given data length.
"That's why OTP is unpractical"... Blehh (Score:3, Insightful)
As a matter of fact, I can, without problem, get a Multi Megabyte Key, available worldwide, without anyone the wiser...
It's called "Project Gutemberg", for one, or any place you can DL fixed texts,software or anything you like (say, what about usinf MS SP4 update as a key? it's available, and makes a key about 200Mo...)
OTP is real, works nice and is easily implementable. In
Re:"That's why OTP is unpractical"... Blehh (Score:3, Insightful)
The NSA would say, gee, there is no way to tell which of these 100 million keys that generate valid english messages are real, but one has a surprising similarity to War and Peace. Wonder which one is the real one?
The whole point in using a RANDOM key is that nobody knows when they've found the right one. If your key is as ordered as your message then it will be VERY obvious. What are the chances that two different novels when applied to the same ciphertext would yield two different valid en
Re:A couple of Thoughts (Score:3, Interesting)
On the other hand, suppose my key is 1,2,3,4,5 - making the message "Hello" turn into "Igopt". Now let me brute-force that - let's try 25,6,22,1,6. Whoa - lucky
Re:A couple of Thoughts (Score:3, Informative)
Re:A couple of Thoughts (Score:3, Informative)
Yeah but encryption will catch up just as fast. You can break codes from WW2 now with what? A 486DX and 15 seconds of CPU time? It's all relative. Besides, we should all be using OTPs anyway
A little knowledge is a dangerous thing... keyword here being "little". Allow me to correct a few points:
1. No, encryption won't catch up just as fast. Currently, encryption enjoys a Big-Oh advantage over brute force cracking. Encryption is O(1) and cracking is O(n). [n is keyspace, not key bits]. If quantum compu
No (Score:5, Informative)
The most significant thing they did was to workout the wiring of the Enigma machine itself. There are 26! ways to wire the machine, and one of the Polish mathematicians - Marian Rejewski - in a stroke of genius - managed to work this out.
The British Intelligence built on the work of the Poles at Bletchly Park duing WW2. Turing in particular produced what was called "The Prof's Book" which was a systematic method for breaking Enigma regardless of the system being used with it. Note that the cracking couldn't be done cold - in particular the woring of the rotors in the enigma machines were required (as well as the wiring of the machine itself - although oddly this was never changed).
What both the Poles and the Allies realised was that Enigma had a huge weakness - it could never encipher a character as itself. The German's knew about this, but thought it was just a quirk.
Later on Shark appeared. This was a cypher system similar to Enigma except it worked on teletype messages. To break this Colossus was born, but the same general idea worked. Ironically, although this was the first Turing machine*, Turing actually had very little directly to do with it.
Thus ends the "Miniature Guide to Codebreaking in Europe in WW2"
* Actually, the German Z3 was the first Turing machine, in 1941. This is not the usual case of "to the victor the spoils" as nobody was sure that the Z3 was a Turing machine until about 1990, althought Conrad Zuse, its designer, thought it might be. I've always vaguely wondered if, by using the same tricks, you could get the difference engine to become a Turing machine.
You're off (Score:2)
Tim
I dunno (Score:2)
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...
Re:I dunno (Score:2)
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.
Re:I dunno (Score:2)
Re:I dunno (Score:2)
I think it would be reasonable to say we could have a working p
I'm working on my own quantum computer (Score:5, Funny)
Re:I'm working on my own quantum computer (Score:3, Funny)
Re:I'm working on my own quantum computer (Score:3, Funny)
Re:I'm working on my own quantum computer (Score:2)
I mean, that's really the point, isn't it?
What is going to run on these computers? (Score:4, Interesting)
Re:What is going to run on these computers? (Score:4, Funny)
Re:What is going to run on these computers? (Score:3, Funny)
Re:What is going to run on these computers? (Score:2)
If they can build it, then they're at the right level of 'advancement' to control it. By your logic, early processors would have been totally unacceptable as a mass-market product.
Re:What is going to run on these computers? (Score:2, Interesting)
Consistent, user frienldy computing is not ubiquitous now, faster processing does not equate to better control, all it means is that we can all BSOD in a fraction of a second instead of in 30 seconds. We can build many things that we cannot control; Highways (who needs a speed limit when I am drunk?), a-bombs (hey, how is North Korea these days?) even daycare centers (Oh, dont worry, the kids are *fine*). What to poster was saying was the processor we use today is insanely faster than the Pent
Re:What is going to run on these computers? (Score:2)
Re:What is going to run on these computers? (Score:2)
Re:What is going to run on these computers? (Score:2)
Shift happens.
Re:What is going to run on these computers? (Score:3, Funny)
No more etc!? Where will we put all our configuration files?
Quantum Computers (Score:3, Insightful)
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)
Re:Quantum Computers (Score:5, Funny)
Re:Quantum Computers (Score:5, Funny)
At least call it by its proper codename. It's called Longhorn, not Windows 2015
Re:Quantum Computers (Score:2)
Re:Quantum Computers (Score:2)
Re: (Score:2, Interesting)
Re:hmm... hardware outpaces software again? (Score:4, Funny)
Re:hmm... hardware outpaces software again? (Score:3, Funny)
The Reason Progress Is So Slow (Score:5, Funny)
(with appologies to Mr. Heisenberg)
Blockwars [blockwars.com]: realtime, multiplayer, and free!
are you certian of that? (Score:2)
I thought it was because they can't know both when and what it will be.
Re:Bugs, who need them? (Score:3, Insightful)
Factoring in the effects of computational advances (Score:5, Funny)
From the article,
Once they get prime numbers licked, they'll move on to the composite ones. To live in such heady times!
Re:Factoring in the effects of computational advan (Score:2)
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."
Reminiscing (Score:2)
I just turned mine on (Score:2)
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)
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?
Is the gate open? (Score:2)
What would a universal gate do to the theory of a closed universe?
I have a quantum computer too.. (Score:5, Funny)
The Nintendo Game Qubit. (Score:3, Funny)
I predict Duke Nukem Forever will be a launch title for the Nintendo Game Qubit.
Re:The Nintendo Game Qubit. (Score:2)
Wow. Not many people can burn Nintendo and Id Software at the same time about their legendary delays. Kudos.
Re: (Score:2)
Would it be outlawed in US? (Score:2)
So, wouldn't quantum computers altogether be banned under DMCA?
They're fixing them? (Score:5, Funny)
No, they'll still be terrible. They'll just be terrible really quickly.
Re: (Score:2, Interesting)
Re:speaking of OTPs (Score:3, Informative)
The problem with most algorythmic random number generators is that if you can collect enough samples you can figure out what
Re:speaking of OTPs (Score:3, Informative)
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)
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)
Re:IAAQCR (I Am A Quantum Computation Researcher) (Score:3, Informative)
And I know of at least one successful QC implementation in solid-state that uses pulsed lasers for the gates, whereas the guys trying solid-state with controlled electric fields haven't gotten very far.
Re:Some facts about Quantum Computing (Score:5, Informative)
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.
Re:Some facts about Quantum Computing (Score:3, Informative)
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
Err, no... (Score:2)
Re:Err, no... (Score:3, Insightful)
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.
Get ready for shorting your Intel stock (Score:2)
All the awesome power -- (Score:3, Funny)
-- And Emacs will still be slower than Vim.
ETA (Score:3, Funny)
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)
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)
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)
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)
Quantum gates (Score:3, Funny)
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)
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?
Re:And with this first step... (Score:5, Insightful)
Not for a while, but it really does make you wonder. Pretty much all of the strongest encryption we have to date (except huge one-time pads shared between parties) rely on classical crypto: it's all about computational infeasibility of solving certain equations.
Quantum computing does have the potential to make this obsolete. All SSL -- used by banks, governments, might be breakable. PGP would be breakable.
It seems reasonable that governments will tightly control developments in this field once they catch on to what's at stake. IMHO, an enemy with the power to break classical crypto is a much greater threat than a jackass carrying an exacto knife.
Re:And with this first step... (Score:2)
Re:And with this first step... (Score:2)
First, while the current algorythms with current key lengths would be trivially broken on a full scale quantum computer, the computational power of such a machine is not infinite in pactice. A quantum computer with infinite processing power would be infinite in size. One can imagine a science fiction approach where a quantum computer builds itself to a huge size (using nano machine replication approaches) but that is not on the near time horizon. Thus, similar encryption schemes to those in u
Re:And with this first step... (Score:3, Insightful)
and all of tomorrows encryption becomes relevant.
Re:/.'ed? No worries: (Score:5, Funny)
Hell, I have an awesome algorithm that runs in O(1) time for determining the factors of prime numbers, but no one is writing a news story about me.
mod parent up... (Score:2)
-j
Oooh oooh (Score:2, Funny)
{
return [ aPrime, 1 ];
}
// Profit!
Re:/.'ed? No worries: (Score:3, Informative)
Re:Finally, the answer! (Score:2)
I look forward to a big blue screen with the words:
QUANTUM ENTANLEMENT ERROR
Violation time event
8483823764768409393736483748574057754057~
Re:Here it is... (Score:2, Funny)
Re:Here it is... (Score:5, Funny)
Then they're be another crowd who analyse people moaning about people who write cliched +5 funnies. This mob is starting to come through.
Then people will start a cliched response to that level in the chain, and on, and on it will go until everyone on the planet is involved in the huge chain of cliched jokes, witty responses, and critique. After that, the sheer scale will evolve its own cliched jokes and the process will become... a chain!!!
Then ensuing feedback loop (having already swallowed all of humanity), will eventually achieve a sentience of its own (a product of the infinite monkey syndrome) and the Slashdot servers will grow legs and crawl away.
So please everyone, keep posting your cliched jokes. And if you don't post the jokes, post replies attacking the jokes. And if you don't post attacks, post some insight on the aggresion. And if you don't do that, think of something even more original. Eventually, we will all become the creators of a new form of life after which, I for one will welcome our Slashdot serving overlord.
Re:Here it is... (Score:2)
Re:Guess What - SLASHDOT SUCKS (Score:2)
-j
Re:How fast will they be? (Score:3, Interesting)
It's a bit like asking "how fast would my car go if I doubled the gas tank size?"
Re:So, um? (Score:3, Insightful)
Quantum computers are interesting because they can carry out operations massively parallel by exploiting quantum states instead of by duplicating processing units. It's important to realise that this is a limiting factor of a quantum computer: It WILL NOT speed up problems that can't be restated to take advantage of th