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 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.


Reply via email to