There is now a lively discussion about the D-wave announcement

going on on Shtetl Optimized.

In particular Scott Aaronson’s advisor Umesh Vazirani enforced Scott Aronsons critique on the D-wave quantum computer in a post yesterday.

(As a matter of fact the paper http://arxiv.org/pdf/quant-ph/0211152 says that the antiferromagnetically coupled 2 dim Ising model in a magnetic

field is NP-hard. I have no idea where it is shown that it is also NP…..

if its not this would make that Ising problem even more uneasy…… )

In my above post I was deliberately “fuzzy” about D-waves

claim about solving the Ising model, since in the announcement

which I saw and linked (see above) they do not really say which

Ising model they want to solve (and what they mean with “solving”-

i.e. they probably do not want to write down Bethe-Ansatz equations:)

but probably rather want to find an explicit ground state, but who knows?? And in what time?!).

There is a nice overview by Barry Cipra about the NP completeness

of solving nonplanar Ising models and Spin glasses, which is

also on the wikipedia Ising Model site.

And citing from Barry Cipras article:

“NP-completeness, however, doesn’t mean things are completely hopeless.

The complexity result bars algorithms only from

solving all instances of the problem in polynomial time.

Typical spin glasses are random mixtures of coupling constants.

It’s entirely possible that the average spin glass problem can

be solved in polynomial time, even though the worst case may be

exponential. Finally, Ising’s original, ferromagnetic model, in

which all coupling constants are equal (and positive), is a

special case, so it too might yet fall within polynomial time.

Only time but possibly an agonizing, exponential amount of it will tell.”

For fairness one should also mention that Barry Cipra also cites

from Dante’s Inferno.

One should also mention that Wired has

an interview with David Deutsch about the above contents.

And last not least one should may be also mention that the **Minesweeper problem**:

P versus NP” is still somewhat an open problem.

And alas not aleas: Ising is pronounced “Easing” in german not “Eyesing” or “Icing”, which is a favorite english alternative. On the other hand the Ising model problem is not easy.

update Feb 17: the link about the Ising model on the D-wave site is still broken, but D-wave **now** refers to the Ising model as the 2 dimensional Ising model in

a magnetic field and probably therefore they refer to the discussion in the adiabatic quantum computer link at http://arxiv.org/pdf/quant-ph/0211152