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.
