commercial quantum computers
A Blochsphere from Wikipedia. Mathematicians call this often CP^1.
Last Tuesday saw the announcement of D-Wave, which gave a demonstration on their World’s First Commercial Quantum Computer. There will be a second demonstration today at the Telus World of Science in Vancouver, Canada.
The first application of their Orion quantum computing system demo is a pattern matching application applied to searching databases of molecules. The second is a third-party planning/scheduling application for assigning people to seats subject to constraints. However it is designed to solve the two dimensional Ising model in a magnetic field.
->more on the demo announcement website by Geordie Rose the CTO of D-wave.
->some technical papers for interested folks
For the readers convinience Scott Aaronson of Shtetl-Optimized also hands out
“The Orion Quantum Computer Anti-Hype FAQ”.
February 16th, 2007 at 4:24 pm
Remark:
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
February 18th, 2007 at 3:20 pm
update Feb 18:
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…… )