Ganesh Swami

I was surprised to learn today that there was a difference between statistical and stochastic simulation. I quote from the latest issue of Computing in Science & Engineering:

We can divide existing approaches to uncertainty quantification into two classes: statistical and stochastic. Statistical approaches include brute-force Monte Carlo simulations (MCS), accelerated MCS (such as quasi-Monte Carlo and Markov chain Monte Carlo methods), importance-sampling techniques, variance-reduction schemes, and response surface methods. Stochastic approaches consist of direct methods (such as interval analysis, operator-based approaches, and polynomial chaos expansions) and indirect methods (such as Fokker-Plank and moment equations). This special issue of Computing & Engineering magazine is devoted to recent advances in stochastic methods.

As Evgeny commented, the D-wave folks didn’t claim to solve NP-hard problems.

For the life of me, I couldn’t understand how adiabatic evolution is in line with one of the fundamental theorems of computational complexity. The fundamental theorem being that every NP-hard problem can be converted into any other NP-hard problem in polynomial time. It seems that adiabatic evolution only works on problems were the target Hamiltonian is not too “far” away from the initial Hamiltonian. Furthermore, the evolution time grows exponentially with distance. How’s that polynomial?

That clears up a lot of things, but not all.

PS: Thanks to Adam for the picture. Calin is obviously turned on by NP-completeness….:P

As a British Columbian, D-wave’s story in the Economist makes me happy. This single story might have done more for the province than all the marketing the government has been trying to do. But today, I came across this note to the Economist by Umesh Vazirani:

Sir,

Your article “Orion’s belter” regarding D-Wave’s demonstration of a “practical quantum computer”, sets a new standard for sloppy science journalism. Most egregious is your assertion that quantum computers can solve NP-complete problems in “one shot” by exploring exponentially many solutions at once. This mistaken view was put to rest in the infancy of quantum computation over a decade ago when it was established that the axioms of quantum physics severely restrict the type of information accessible during a measurement. For unstructured search problems like the NP-complete problems this means that there is no exponential speed up but rather at most a quadratic speed up.

Your assertions about D-Wave are equally specious. A 16 qubit quantum computer has smaller processing power than a cell phone and hardly represents a practical breakthrough. Any claims about D-Wave’s accomplishments must therefore rest on their ability to increase the number of qubits by a couple of orders of magnitude while maintaining the fragile quantum states of the qubits. Unfortunately D-Wave, by their own admission, have not tested whether the qubits in their current implementation are in a coherent quantum state. So it is quite a stretch to assert that they have a working quantum computer let alone one that potentially scales. An even bleaker picture emerges when one more closely examines their algorithmic approach. Their claimed speedup over classical algorithms appears to be based on a misunderstanding of a paper my colleagues van Dam, Mosca and I wrote on “The power of adiabatic quantum computing”. That speed up unfortunately does not hold in the setting at hand, and therefore D-Wave’s “quantum computer” even if it turns out to be a true quantum computer, and even if it can be scaled to thousands of qubits, would likely not be more powerful than a cell phone.

Yours sincerely,
Umesh Vazirani
Roger A. Strauch Professor of Computer Science
Director, Berkeley Quantum Computing Center

(via Scott Aaronson)

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

While an advanced math degree isn’t absolutely required to be a programmer, it definitely helps one in designing smart unit tests. Here are two examples where I used mathematical properties to design unit tests. Most of my functions that take one of these objects as an argument runs these tests as a pre-condition. Of course, this is switched off in release builds.

SPD Matrices

A type of MRI modality known as Diffusion Tensor MRI can be used to measure the diffusion properties of molecules in tissues. The diffusion is because of the Brownian motion of the molecules. There is a direct connection between the diffusion constant and the local structure in tissues. DT-MRI is pretty much the only non-invasive imaging system for the white matter in the brain.

By making measurements of the diffusion in different directions, we can represent the local diffusion at a voxel by a tensor. This rank-2 tensor is a symmetric positive definite (SPD) matrix. Normal matrices can be thought of as points in a nine dimensional space, but symmetric matrices only have six degrees of freedom. So, instead of being a linear space, the manifold is that of a hyperboloid.

Therefore, it makes sense that any operation done on these matrices should also be a SPD matrix. For example, the group is not closed under the subtraction operation. Literature has many examples of distance definitions for SPD matrices. The log-Euclidean metric for example will fail if your matrix is not a SPD (log of a negative real number is undefined.)

Some properties of SPD matrices:

• Eigenvalues are positive
• Determinant is positive
• Matrix inverse is positive definite

Special Orthogonal/Euclidean

The class of purely rotational matrices fall under Special Orthogonal, while matrices that combine rotations and translations fall under Special Euclidean. They’re both subclasses of general linear transformations. Almost every physics engine will have routines to generate transformations given an angle and a translation vector. Arbitrary transformations can be generated by the composition of transformations along the basis vectors for that space.

Some important properties of these groups:

• Rows are orthogonal to each other
• Columns are orthogonal to each other
• Matrix transpose equals matrix inverse
• Matrix times its inverse/transpose returns the identity matrix
• Determinant is equal to +1
• Columns and rows are normalized

These tests are particularly useful in making sure a multi-disciplinary group is on the same page. Physicists and almost everybody else uses a right hand coordinate system, while Chemists are trained to use the left hand coordinate system. The confusion possibly arises from the definitions of cis- and trans-, I’m not exactly sure. In fact, a quick look at the bible Computer Simulation of Liquids defines rotation matrices as the inverse of the “standard.”