On 5/17/2013 10:29 AM, John Clark wrote:
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
<http://graphics8.nytimes.com/packages/pdf/business/quantum-study.pdf%20>
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.
This is what makes one think the D-wave may just be a special purpose machine, like an
ASIC. For example if you wanted to find the EM field that minimizes the energy for a give
configuration of charges that's a had problem for a general purpose computer using the
best digital algorithm, but it's a trivial problem for a special purpose computer that
just puts charges in those places and measures the field. The D-wave essentially solves
the Ising problem and other problems that can be transformed into the Ising problem. I'd
like to see a paper on its theory of operation.
Brent
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
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/everything-list?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
