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.
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)
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.
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 consumer market)? How long until we have an end-user quantum computer? And how hard will it be to defeat the built in DRM ;)
I want peace on earth and goodwill toward man.
We are the United States Government! We don't do that sort of thing.
(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!
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.
"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.
"Derp de derp."
"All of todays encryption becomes irrelevant"
and all of tomorrows encryption becomes relevant.
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!
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 way of generating the random data you need in the first place? How random does it truly have to be? I read somewhere that the way the Government does it is to use radio noise. I've never heard a better way (though I hope RIAA doesn't found out ;) that would be as easy to implement.
I want peace on earth and goodwill toward man.
We are the United States Government! We don't do that sort of thing.
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 superposition of states in a quantum system can be interpreted as multiple universes, each containing a possible outcome. I'm pretty sure that this means that every quantum computer is inherently an inter-dimensionally multiplexed beowulf cluster of itself. Until you look at it.
function getFactors( aPrime )
{
return [ aPrime, 1 ];
}
// Profit!
Vino, gyno, and techno -Bruce Sterling
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!
Raw clock cycle rate has surprisingly little to do with processor speed, unless you only ever talk about a single platform. A quantum computer is so different from a modern CPU as to make the comparison nonsensical.
It's a bit like asking "how fast would my car go if I doubled the gas tank size?"
Endless arguments over trivial contradictions in books written by ignorant savages to explain thunder in the dark.
Recursion (n): See recursion
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.
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
-- And Emacs will still be slower than Vim.
Chr0m0Dr0m!C
Just reading in the number and printing it is O(n), unfortunately (takes time proportional to the number of characters of the input).
I believe posters are recognized by their sig. So I made one.
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?
"Everything you know is wrong. (And stupid.)"
Moderation Totals: Wrong=2, Stupid=3, Total=5.
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...
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.
- 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.
Democracy is two wolves and a sheep voting on lunch.
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 the parallelism that a quantum computer offers.
The most likely use of quantum computers for the foreseeable future would be as simple co-processors for a conventional computer, with just a small number of qubits, as there are many smaller tasks that could likely be speeded up dramatically. Imagine doing string searches and comparisons where every character is compared against the pattern at once for instance - would have a dramatic impact on query times for databases and full text search systems... Systems depending on large amounts of matrix calculations would be another.
Applying quantum computing in piecemeal for algorithms that are small, self contained and frequently used will be immensely beneficial long before software engineers catch up and get experience with developing algorithms for quantum computers.
Disclaimer: I haven't spent much time reading up on quantum computers, so I'm likely completely clueless about the subject :-)
"Unless you have someone on a gray coat to take a bible inside a black suitcase chained to his arm to the recipient of your message."
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. Internet got us here 8)
So, my DSL modem is black, and has a grey cat5 cable connected to it. I think I'll use it as my courrier 8)
It takes 40+ muscles to frown, but only four to extend your arm and bitchslap the motherfucker
Just because it's hard to find an answer, doesn't mean it's hard to verify it. Consider the canonical example of factorisation - checking the results is trivial.
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.
Why are you letting these clowns ruin our country?
It seems to me that quantum computing will mean the end of privacy for consumers like you and me. Currently I can use a 4096 bit PGP key to encrypt something so that pretty well noone on earth, even those with the most massive supercomputers, will be able to see my secret message. Once quantum computing comes out this goes down the drain. If my 4096 bit key can be cracked in a few hours then I need to get a bigger key. Unfortunately at first these quantum computers will be reserved for governments only, for many people who use encryption that is exactly the type of people that they don't want spying on them (government conspirists). In order to match the raw computing speed of the governements massive quantum computer my athlon tbird 1400 may have to generate a 4294967296 bit key. A feat which may take days, even worse when this key is used for encryption. Personal privacy worked when computers merely scaled linearly (if you double the computing power , you basically double the processing power) but with the advant of quantum computers those rules just don't apply any more
History will be kind to me, for I intend to write it - Sir Winston Churchill
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.
I thought it had been shown that to make a quantum computer you needed the gates to be made of cats...
Human genome = 3 billion base pairs = 6 GBit. Windows + Office = 20 Gbit. Which is more impressive?
This is not the first controlled-not gate for a quantum computing system but rather the first in this solid state system.
Other implementations of a controlled-not gate (or its close relative, a controlled-phase gate) include:
Caltech Quantum Optics implemented a controlled-phase gate between photons using a strongly coupled atom in a cavity.
Serge Haroche's group implemented a controlled-phase between an atom and a photon using microwave cavities and atomic Rydberg states.
NIST Ion Storage Group: implemented a two qubit gate (which could be turned into a controlled-not) and a four qubit gate using trapped ions.
NMR quantum computing has been implemented by various groups including the biggest quantum computation to date, factoring 15, done by Isaac Chuang's group (IBM and now MIT.)
A proof of principle implementation of a controlled-not in the linear optics quantum computing scheme has been implemented at the University of Queensland.
I'm leaving out quite a few other cool experiments: but the above links should give you a good idea of the what early steps have been taken in quantum computing.
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?
Bruce Lane, KC7GR,
Blue Feather Technologies
Picture these staggering fast processing speeds applied to genetic algorithms/programming. For those who don't know, in a very rough sense (don't nitpick) this involves:
1. You want a program that take input X and produces output Y
2. Generate a whole bunch of random programs. Most will do nothing even resembling producing the output Y, but some will suck more than others.
3. Feed the input X, and see what output each program produces. Take the least terrible program from the batch, make a bunch of copies
4. Then for each copy, change it randomly a little, eg flip a few bits.
5. If there isn't any program in the bunch that's good enough for you, go back to 3.
6. Otherwise, you have your program and didn't have to write it yourself. In fact, you don't even need to have the slightest idea how to solve the problem, just how to state it.
The only problem with this is that it may take a really, really long time to evolve an acceptable program. Often too long to be worth bothering. But with speeds as ridiculous as they propose for quantum computers, what program couldn't you evolve in say, a day? Or, for that matter, why not just generate every possible piece of machine code of a given length, run them all through an emulator at sickening speeds, and see if any of them solved the problem? I think that if you have truly sick processing power like this, then almost any problem is solvable with relative ease. Maybe I overstate the case, but you see what I'm getting at.