Re: quantum computer announcement]

[David Farber <dave () farber net>]

Begin forwarded message:

From: Rod Van Meter <rdv () tera ics keio ac jp>
Date: February 4, 2007 10:09:27 PM EST
To: David Farber <dave () farber net>
Subject: [Fwd: [IP] quantum computer announcement]
Reply-To: rdv () tera ics keio ac jp

This is the D-Wave guys, and for those of you who don't know, what they
are working on is Adiabatic Quantum Computing.  I'm very fuzzy on AQC,
but it's not a gate model of programming the device -- you essentially
set it up and let it cool into the solution state, something like a
literal quantum analog version of simulated annealing.

Proving that this device works using truly quantum effects will be very
tricky.  D-Wave itself hasn't published much in the literature, but they
have a little.  They also have a number of reasonably well respected
names among their advisers (who presumably stand to benefit economically
if this thing works).  D-Wave has a lot of VC money, and presumably
those VCs are interested in reality; if the device doesn't work, they
won't make any money.

Their existing device is 16 qubits, Josephson junction-type devices
built using relatively standard VLSI techniques and operated at 4K,  
liquid
helium temperatures (I didn't understand the bit about why it doesn't
have to be an even lower, millikelvin operation, but that's a minor
point).

My guess is that they are unable to demonstrate quantum entanglement
across all 16 qubits in a way that would satisfy the major journals (in
fact, if they could do it across *three*, that would be more than anyone
else for the specific type of qubit they use, and the current record for
any type of qubit that I know of for any type of qubit is 12 qubits).

They claim they will hit 1,000 qubits by the end of 2008, and the basic
device is certainly plausible  -- all you have to do is stamp out more
qubits on the chip.  There is a lot of system engineering to do to
control that many qubits; at the moment, each one takes several U of
rack-mount equipment to control, and several I/O pins on the chip.
Moving much of that on-chip is the obvious goal, and is possible, but
it's work.  (This, plus the basic fact that Josephson junction (JJ)  
devices
are VERY fast, are two big pluses of this approach, from a systems point
of view.)

The harder part will be making quantum states survive long enough, and
work well enough, that 1,000 qubits represents a *useful* device.
Decoherence, or the lifetime of the quantum state, is a MAJOR problem
for the JJ devices.

What D-Wave is demoing is *quadratic* speedup on an NP-complete search
problem.  This is valuable, and in accordance with what we know about
quantum computing and complexity, but not the Holy Grail of quantum
computing.  No one will pay them money to solve 16-bit NP optimization
problems, but people will well before they hit 1,000 qubits,  if it all
works.  They also claim to be working on various simulations of quantum
systems using their device, which *does* have the potential to do
New Science with relatively modest-sounding systems, and is one of the
best potential uses of a quantum computer.

They claim that they have X axis and Z axis control of individual qubits
(you need to be able to reach any point on the unit sphere from any
other), and a ZZ coupling between pairs of qubits.  They also say that
they need an XZ coupling to reach fully general QC, and that will be
tricky.  But my understanding of the theory is that what they have
should be sufficient; there is probably some more technical constraint
that isn't explicitly in the announcement -- like they can only do X on
odd-numbered qubits and Z on even-numbered ones, or somesuch.

There is a good discussion on Dave Bacon's blog, as well:
http://dabacon.org/pontiff/?p=1427

Anyway, the device looks impressive, and may represent a major step
forward.  Hard to know for sure at this stage.  Good luck to the D-Wave
guys, and congrats on their achievements so far!

                --Rod

P.S.  To toot my own horn for a second, Mark Oskin and I had a paper
in JETC last year on the systems issues in building large-scale
quantum computers.  It's available on my web page at
http://www.tera.ics.keio.ac.jp/person/rdv/quantum/index.html
and may make those with a computer systems bent make more sense of the
quantum computing systems.  Personally, I'd rather be building these
systems than thinking about how to build them, but one step at a time...




-------------------------------------------
Archives: http://archives.listbox.com/247/
Powered by Listbox: http://www.listbox.com