Slashdot Mirror
Quantum Computing Breakthrough in Japan
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."
- 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.The grass is only greener, if you don't take care of your own lawn.
But that's really neither here nor there.
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.
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.
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.
(with appologies to Mr. Heisenberg)
Blockwars: realtime, multiplayer, and free!
"They do not preach that their god will rouse them, a little before the Nuts work loose." Kipling, 'The Sons of Martha'
From the article,
Once they get prime numbers licked, they'll move on to the composite ones. To live in such heady times!
Yeah! It's called J2EE. You should check it out sometime. I'm sure the next incarnation, J3EE, will suck the living juice out of any quantum computer thrown at it.
yes, and well only need, maybe, 5 in the world...
The Kruger Dunning explains most post on
Then again, if you chart processor and memory usage, you will find that nothing will run Windows 2015
At least call it by its proper codename. It's called Longhorn, not Windows 2015
Have you tried Linux yet?
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.
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.
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?
I don't know where it is, but it's moving at exactly 3.65 m/s.
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.
Refuse to make a statement in your sig!
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)
The Raven
The new cliche will be pointing out cliches. The slashdotters who involve themselves in writing cliche +5 funnies will attract another crowd who moan about cliched +5 funnies.
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.
Refuse to make a statement in your sig!
Recursion (n): See recursion
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.
The Raven
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.
You may be thinking of Polish Military Intelligence, but they did not "break" Enigma as such. They managed to break an Enigma system - the combination of machine and method of operation - which was to modern eyes fairly weak. Just before the invasion of Poland in 1939 the Germans changed they system and the Poles could not read it anymore (not because they couldn't figure it out, but that the methods used to crack it were too slow - they couldn't build the bombes which were an essential part of the cracking).
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.