[ExI] D-Wave's Quantum Computer

[John Clark]

At last there is a report of a Quantum Computer solving a more interesting
problem than finding the factors of 15:

http://graphics8.nytimes.com/packages/pdf/business/quantum-study.pdf

D-Wave's chip is not a general purpose Quantum Computer like a machine with
quantum logic gates would be, but it can still do neat stuff. It was tested
on 3 different classes of problems to see how it compared against a very
high end PC using the best conventional algorithms known. All 3 different
classes of problems are NP hard:

1) W2SAT problem, Weighted maximum 2-Satisfiability problem, it figures out
if the Boolean variables (variables that can have only 2 values, true or
false for example) of a pure Boolean formula can be assigned in such a way
as to make the entire formula be true. For example, suppose you had a
densely populated map of n cities and could put a label identifying the
city either just above or just below the city, how could you arrange things
so that the labels overlap the least? Even a small increase in the number
of cities makes this problem vastly more difficult, and if the number of
choices you have for places to put labels is greater than 2 the problem is
not only NP hard but known to be NP complete hard; in fact it was the very
first NP complete problem found.

2) QAP problem, Quadratic Assignment Problem. The Traveling Salesman
Problem is a special case of QAP.

3) QUBO problem, Quadratic Unconstrained Binary Optimization problem, it
concerns the minimization of quadratic polynomials. QUBO is a NP hard
problem and is a pattern matching and image recognition technique used in
machine learning. The enormously important protein folding problem is also
QUBO as is anything where you have a lot of different things that can
attract or repel each other and you want to arrange things in such a way
that the entire system has the lowest possible energy.

This is how D-wave's chip did in the competition with a very high end PC
running the best algorithms known:

1) W2SAT problem: The D-wave chip did as well as the conventional computer
but no better.

2) QAP problem: D-wave did better than the PC but not dramatically better.

3) QUBO problem: This is where things really got interesting, on average it
took the high powered PC half a hour to find a solution that only took the
D-wave chip half a second to solve; it was 3600 times faster. In fact,
although not a general purpose computer, if you just restrict yourself to
QUBO problems the D-Wave chip would be the 10'th fastest supercomputer on
Earth equal in performance with IBM/DARPS Trial Subset, a conventional
machine with 63,360  64-bit cores. Not bad for a thumbnail sized chip even
if you do need to carefully shield it and cool it down to just .02 degrees
above absolute zero.

D-Wave made the chip used in the competition in September of 2012 and it
had 439 qubits, it's a 512 qubit chip but due to manufacturing defects only
439 worked. The qubits in the chip consist of Niobium loops that according
to the weird laws of Quantum Mechanics can have a electric current flowing
around them clockwise (+1) counterclockwise (-1) or both (+1 and -1).  The
behavior of one loop influences the behavior of nearby loops and input and
output is achieved by a structure of Josephson junctions.

In December 2012 D-wave made a chip with 503 working qubits, preliminary
indications are that it is about 5 times as fast as the chip used in the
contest, if so then it would be the 5'th fastest supercomputer on the QUBO
problem. D-wave says that during the last decade the number of qubits in
its chips has doubled every year, and that is better than Moore's law.

  John K Clark
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.extropy.org/pipermail/extropy-chat/attachments/20130517/e097fc52/attachment.html>