Spanning Multiple Universes
I haven’t posted anything about D-wave’s quantum computer because I wanted to see for myself. The sheer amount of bad reporting out there is overwhelming. Here, as usual, you get the facts, or my understanding of them atleast.
Some background:
The four complexity classes of interest are:
- P has solution in polynomial time
- NP, nondeterministic polynomial has an algorithm to check the solution in polynomial time. For example, you can check the solution to the factoring problem in polynomial time — just multiply them.
- NP-hard is where any NP problem can be converted to this class in polynomial time.
- NP-complete is the class that is both NP-hard and in NP itself.
All interesting problems are infact NP-complete. D-wave claims that its computer can solve NP-complete problems.
D-wave uses a computational model known as Adiabatic Quantum Computing. The way they do this is by cooling a simple model such as the Ising model to the ground state. Then they slowly (”adiabatically”) evolve the Hamilton to the resulting problem. The system never leaves the ground state of the instantaneous Hamilton the entire time.
From a computational standpoint, reaching the ground state (lowest energy) of the Ising model has been shown to be NP-Complete. But nature reaches the lowest energy all the time. This is what D-wave exploits. They use a dilution refrigerator to cool the system to 4 mK.
The event
Even though I was well in time before the doors opened, there was a huge lineup. The event started on time. The room couldn’t accommodate all of us and many were standing. I recognized a lot of faces — I guess it’s the same set of people hanging out at various nanotech-biotech events.
An introduction was given by the chairman Haig Farris followed by the CEO. The interesting part started when the CTO Geordie Rose took the stage.
He gave us a demo of three applications that used the quantum computer, physically located in their Burnaby location. The first was searching for similar molecular structures from a database. This was solved by computing the maximum independent set for the graph of the molecule. The second example was that of the wedding seating plan. This was an example of constraint matching. The third was solving a Soduku puzzle.
Rose called the quantum computer as a “hardware accelerator” for specific types of problems, integer optimization ones. Currently, their technology is about 100 times slower than conventional computers.
Their biggest issue right now is dealing with noise. Sometimes noise causes the system to move away from the ground state during the evolution process resulting in incorrect final answers. Instead of dealing with this problem with sophisticated error correction algorithms, they run the problem multiple times and choose the answer that appears the most number of times.
From what I gather, solving NP-complete problems opens up a huge field. From problems in operations research, computational chemistry to quantitative finance, the market is huge. D-wave promises a thousand qubits by the end of 2008.
At the end of the event, they gave all of us a huge poster of the chip I posted above. I’m going to frame it as proof that I was witness.
My interest
I’m mainly interesting in calculating electronic strutures in quantum mechanics. This in general cannot be formulated as an integer optimization problem. Their current prototype only uses nearest neighbor couplings, which is inadequate for bigger problems. Rose claims that they have an architecture that can couple between all qubits. That should be interesting.
References
I’ve posted links to papers and background reading that I found useful.
- Scalable Superconducting Architecture for Adiabatic Quantum Computation
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- A fast quantum mechanical algorithm for database search
- Quantum Computation by Adiabatic Evolution
- The Ising Model is NP-Complete
- Possible implementation of adiabatic quantum algorithm with superconducting flux qubits
February 16th, 2007 at 4:28 am
Amazing, the blog claims this post was posted 1 year and 12 months ago. That’s some foresight you’ve got there
While I think the promise of this technology is interesting, I think this demonstration was a bit premature, or maybe just underwhelming. Really, anyone could have put on the same demo and made the same claims. I’ll be watching with a guarded skepticism until they allow this to be verified, or at least show some more impressive results. My interpretation right now is that they’re trying to drum up some more funding, but maybe I’m just being cynical.
February 17th, 2007 at 4:06 am
As far as I understood they admit that quantum computation is not capable of solving NP-hard problems and at one of videos claim that their computer gives quadratic speedup. But if time grows exponentially with size of the problem, then quadratic speedup will allow to solve problems only several bits longer. Probably without understanding of what is adiabatic computation model there is no way to understand why and how this machine works.
February 17th, 2007 at 6:49 pm
Kamil: Even better — my time machine can reach -1 year and 12 months.
Sure, the demo was interesting, but doing some background reading raises a lot of red flags. For one, most of their technology is not published in reputed journals. Geordie says that they are in the business of making quantum computers, not in writing publications. That seems like a weak explanation. But, if this does work out, that’s a sign of the failure of peer review and publications.
Secondly, they’ve proposed adiabatic quantum computing as a model of computation. I’m not really sure if this is a quantum computer according to standard literature.
You’ll have to give them credit though for bringing the spotlight to BC’s high-tech community. They were called the Fairchild Semiconductors of BC. That’s good for engineers like you and me. Cheers.
February 18th, 2007 at 8:46 pm
[...] As Evgeny commented, the D-wave folks didn’t claim to solve NP-hard problems. [...]