Quantum Computer To Launch Next Week

judgecorp writes "D-Wave Systems of British Columbia is all set to demonstrate a 16-qubit quantum computer. Simple devices have been built in the lab before, and this is still a prototype, but it is a commercial project that aims to get quantum devices into computer rooms, solving tricky problems such as financial optimization. Most quantum computers have to be isolated from the outside world (look at them and they stop working). This one is an 'adiabatic' quantum computer — which means (in theory, says D-Wave) that it can live with thermal noise and give results without having to be isolated. There's a description of it here — and pretty pictures too."

Comments

Computer is snake oil

[LiquidCoooled]

It is not a general quantum computer.
It is a single instance specific formula calculator.

Any problem that can be recast as a two-dimensional Ising model in a magnetic field problem (AKA quadratic integer programming) can in principle be solved using the approach we'll be demo'ing.

Thats from their blog

There were some interesting questions asked and lots of people are sceptical.

Quantum mystery

[suv4x4]

Most quantum computers have to be isolated from the outside world (look at them and they stop working)

This is often misunderstood. Quantum computers don't stop working when you "look at them", the "observer" metaphor is just a fancy way to say that the wave propagation of a particle collapses when it interacts with another particle.

Basically, imagine they are waves, propagating from the point of last interaction like expanding spheres. When two particles (spheres) touch each other, they collapse back to being single-point particles, and continue propagation anew until the next collision.

Which means, look at them all you want, just don't crack the casing open and point a torch inside.

The article is full of wrong crap

[rbarreira]

It has been predicted that quantum computing will make current computer security obsolete, cracking any current cryptography scheme

Wrong. As far as current knowledge goes, a quantum computer is not a big help for cracking symmetric ciphers such as Triple DES or AES. It is a big help for RSA, since it can factor numbers in O(number size) time.

I Don't Know If It's "Snake Oil" Exactly

[eldavojohn]

There were some interesting questions asked and lots of people are sceptical.

Disclaimer, I'm not a physicist.

Well, most importantly, a while back I had read up on the research being done at Los Alamos National Laboratory on quantum computers. Granted, this was 4 or 5 years ago, they have an interesting paper[PDF warning] where, if you'll look at figures 1 & 2, you'll notice that the number of bits you are able to factor is directly related to the decoherence time.

Now, if you're not familiar with Shor's Algorithm, the values in the first figure might not mean much but, in layman's terms, I believe they were experiencing problems with 8 or more qubits. I remember reading that decoherence would destroy the relationship between the qubits before they could prepare them and do a meaningful computation. I had always thought that this would be an upper bound until someone figured out a way around it. If this computer is also using similar means, I'd like to know what special modification they did to overcome these coherence problems.

You're correct that there are a lot of important questions to be answered but a 16 qubit computer that is a "a single instance specific formula calculator" as you put it still interests me greatly and may be a giant leap forward in our ability to understand future computers that may be true full blown quantum computers. Why downplay this unless you can directly point out a problem with what they're doing and what they claim they can do?

Single purpose... but solves NP-C, silly!

[sanermind]

It's not a big deal that it only solves a particular NP-complete problem.. because if you can solve and one NP-complete problem, you can solve ALL of them. From the wikipedia article

a deterministic, polynomial-time solution to any NP-complete problem would also be a solution to every other problem in NP

Anyone who took computer science at a decent school and remembers any of it would remember the whole issue of whether P=NP or not. One of great unsolved problems in mathematics, and the fundamental promise of quantum computers vs. classical ones. And the little tidbit that NP-c problems are cross equivalent.. that if you could solve any ONE of them, you could use that method, translating all others into a formalism that could be solved by the original solution. This is a VERY big thing if it's actually working. Still only 16 bits, but jeesh. Still, I'm not sure what the 'adiabatic' nature means. From perusing the article (which was over my head, to be sure) it sounds like they've achieved some sort of partially locked quantum state that's allowed to evolve slowly, not instantaniously. Sort of a quantum anealing, if you will? They are perhaps wiggling the system on a sort of clock while quantum information exchange can happen in parts between certain but not all parts of the system? In which case, it's still pretty neat, but I don't know about scaling.. It may still take quite some (unrealistic) time to solve problems of larger size with more bits

Re:Single purpose... but solves NP-C, silly!

[Gospodin]

How could the rules possibly change in this way? Suppose I have an NPC problem I wish to solve (call it P), and a known quantum algorithm that solves a different NPC problem in poly time (call it Q). In poly time I transform P into Q. In poly time I solve Q using the quantum computer. Then in poly time I transform the solution to Q into a solution for P. If I want, I can then check the solution to P in poly time using a conventional computer (this is guaranteed by the definition of NPC). I only need to invoke quantum computing when I'm solving Q - no other step requires nonpoly time.

Meaning of "adiabatic" (since you asked :-) )

[da cog]

The idea behind an "adiabatic" quantum computer is that you can somehow set up a system so that the solution to a problem that you want to solve is encoded in the system's ground state. Thus, in principle all you have to do is cool the system down so that it's at its lowest possible energy level, measure it, and then "decode" the measurements to obtain your solution. The problem with this is that you can't necessarily know when you've gotten the system to be in the ground state; it is possible for it to get "stuck" in a slightly higher-energy state from which it cannot escape, as there might be a forbidden transition between its current level and the ground state.

This is analgous to a situation in atomic physics: if you've got an electron in an n=2, l=0 state, then it is hard for it to fall all the way down to the n=1 state because in order to change energy it has to emit a photon which changes its angular momentum and thus increases l, but there is no n=1, l=1 state there's only a n=1, l=0 state, and so the transition is forbidden. (Of course, this is an over-simplification that neglects things like the fact that the electron can change it's spin, but you get the idea.)

So you don't try to go straight to the ground system that you are interested in, because you don't know for sure that you can get there consistently. Instead, you build a system whose ground state you are sure you can get to, and then you slowly change the configuration of that system until it matches the one that you want to solve. Because you are changing it slowly -- i.e., "adiabatically" -- you should never leave the ground state (even though the ground state itself is changing right under you) and thus when you are done you are guaranteed to be in the ground state of your system of interest, from which you can obtain the solution to your NP complete problem.

There is a catch, though, which is that you have to have the system be *very* cold, and you have to change it *very*, *very* slowly. And here's where the catch can kill you: as the size of your system increases, the gap between the lowest two energy states decreases *exponentially*. This means that you have to make the system exponentially colder, *and* that you have to change it exponentially slower. Thus, adiabatic computers are not expected to be able to solve NP-complete problems in linear time, as there is still a cost in time (and cooling effort) which grows exponentially with the size of your problem. Nonetheless, it's likely that you can get a quadratic speed-up equivalent to Grover's search algorithm by building such a computer.

This, by-the-way, is why many quantum computing people believe that D-wave is ultimately going to fail -- probably not with this particular computer, but with scaling it up to the point where it's actually useful. But hey, maybe we're wrong and they've figured it all out; we can certainly hope that's the case. :-)

Adiabatic Quantum Computing Explained

[da cog]

For those of you who know some quantum mechanics, here's what's going on:

The idea behind an "adiabatic" quantum computer is that you can somehow set up a system so that the solution to a problem that you want to solve is encoded in the system's ground state. Thus, in principle all you have to do is cool the system down so that it's at its lowest possible energy level, measure it, and then "decode" the measurements to obtain your solution. The problem with this is that you can't necessarily know when you've gotten the system to be in the ground state; it is possible for it to get "stuck" in a slightly higher-energy state from which it cannot escape, as there might be a forbidden transition between its current level and the ground state.

This is analgous to a situation in atomic physics: if you've got an electron in an n=2, l=0 state, then it is hard for it to fall all the way down to the n=1 state because in order to change energy it has to emit a photon which changes its angular momentum and thus increases l, but there is no n=1, l=1 state, there's only a n=1, l=0 state, and so the transition is forbidden. (Of course, this is an over-simplification that neglects things like the fact that the electron can change it's spin, but you get the idea.)

So you don't try to go straight to the ground system that you are interested in, because you don't know for sure that you can get there consistently. Instead, you build a system whose ground state you are sure you can get to, and then you slowly change the configuration of that system until it matches the one that you want to solve. Because you are changing it slowly -- i.e., "adiabatically" -- you should never leave the ground state (even though the ground state itself is changing right under you) and thus when you are done you are guaranteed to be in the ground state of your system of interest, from which you can obtain the solution to your NP-complete problem.

There is a catch, though, which is that you have to have the system be *very* cold, and you have to change it *very*, *very* slowly. And here's where the catch can kill you: as the size of your system increases, the gap between the lowest two energy states can decrease *exponentially*. This means that you have to make the system exponentially colder, *and* that you have to change it exponentially slower. In general systems do not behave this badly, but it is expected (and possibly has been shown, I don't remember) that systems which can solve NP-complete problems *do* behave this badly. Thus, adiabatic computers are not expected to be able to solve NP-complete problems in linear time, as there is still a cost in time (and cooling effort) which grows exponentially with the size of your problem. Mind you, you aren't *forced* to move so slowly, but if you don't then you have a good chance of effectively kicking the system into an excited state and thus ending up with something that is not a solution to your problem. Nonetheless, it's likely that you can get somehow a quadratic speed-up (equivalent to Grover's search algorithm) over classical computation by building such a computer.

This, by-the-way, is why many quantum computing people believe that D-wave is ultimately going to fail -- probably not with this particular computer, but with scaling it up to the point where it's actually useful. But hey, maybe we're wrong and they've figured it all out; we can certainly hope that's the case. :-)