Ganesh Swami

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

In my non-linear physics class, we are covering topics that I find very interesting: Fast-slow dynamics.

Consider the system of coupled differential equations above. If the parameter r is extremely small, the equations exhibit two time-scales. From the perspective of the fast equation, the slow equation is almost constant and from the perspective of the slow equation, the fast equation has already reached steady-state. Thus, by appropriately re-scaling time, you can make approximations about the final behavior of the system. I’m still trying to understand the rigorous mathematical analysis that has gone into these equations. If you want to learn more about this re-scaling trick: search for “adiabatic elimination” and “center manifold.”

These techniques are often used in the field of weather prediction. You have dynamics that can act either locally or globally. By making robust approximations, you can get away with weak assumptions about the local effects. This lets you use a bigger timestep that can give you more relevant results.

From my own experience, I can draw parallels to the simulation of chemical systems. In protein simulations, you have solvent effects that are high frequency actions. This forces you to use a small timestep. Some concrete numbers: water molecules have motions in the picosecond range, while we really are only interested in the motion of the proteins on the nano/micro second range. But the action of the solvent is crucial to the dynamics of the protein, so we really cannot get away with ignoring solvent effects. I wonder if I can use a similar analysis to enable the use of a bigger timestep? Probably not, as somebody would have done this already.

I’m pretty exhausted from the talk/discussion that I led at the MIAL today. I spent a lot of time getting the slides to look right, specially the equations. I did this by keying LaTeX equations into emacs, compiling them and importing the resulting PostScript into the Gimp. I imported them at a resolution of 500, which gave me an image of about 4000×4000 pixels (that should be enough for anyone.) From there I cut the equations and pasted them into Powerpoint. I scaled them down keeping the aspect ratio fixed.

There’s got to be a better way.