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 thanfinding the factors of 15:## Advertising

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 quantumlogic gates would be, but it can still do neat stuff. It was tested on 3 differentclasses of problems to see how it compared against a very high end PC using the bestconventional algorithms known. All 3 different classes of problems are NP hard:1) W2SAT problem, Weighted maximum 2-Satisfiability problem, it figures out if theBoolean variables (variables that can have only 2 values, true or false for example) ofa pure Boolean formula can be assigned in such a way as to make the entire formula betrue. For example, suppose you had a densely populated map of n cities and could put alabel identifying the city either just above or just below the city, how could youarrange things so that the labels overlap the least? Even a small increase in the numberof cities makes this problem vastly more difficult, and if the number of choices youhave for places to put labels is greater than 2 the problem is not only NP hard butknown 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 aspecial case of QAP.3) QUBO problem, Quadratic Unconstrained Binary Optimization problem, it concerns theminimization of quadratic polynomials. QUBO is a NP hard problem and is a patternmatching and image recognition technique used in machine learning. The enormouslyimportant protein folding problem is also QUBO as is anything where you have a lot ofdifferent things that can attract or repel each other and you want to arrange things insuch 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 thebest 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 thehigh powered PC half a hour to find a solution that only took the D-wave chip half asecond to solve; it was 3600 times faster. In fact, although not a general purposecomputer, if you just restrict yourself to QUBO problems the D-Wave chip would be the10'th fastest supercomputer on Earth equal in performance with IBM/DARPS Trial Subset, aconventional machine with 63,360 64-bit cores. Not bad for a thumbnail sized chip evenif you do need to carefully shield it and cool it down to just .02 degrees aboveabsolute 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 inthe chip consist of Niobium loops that according to the weird laws of Quantum Mechanicscan have a electric current flowing around them clockwise (+1) counterclockwise (-1) orboth (+1 and -1). The behavior of one loop influences the behavior of nearby loops andinput and output is achieved by a structure of Josephson junctions.In December 2012 D-wave made a chip with 503 working qubits, preliminary indications arethat it is about 5 times as fast as the chip used in the contest, if so then it would bethe 5'th fastest supercomputer on the QUBO problem. D-wave says that during the lastdecade the number of qubits in its chips has doubled every year, and that is better thanMoore'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 everything-list+unsubscr...@googlegroups.com. To post to this group, send email to everything-list@googlegroups.com. Visit this group at http://groups.google.com/group/everything-list?hl=en. For more options, visit https://groups.google.com/groups/opt_out.