At last there is a report of a Quantum Computer solving a more interesting problem than finding the factors of 15:<br><br><a href="http://graphics8.nytimes.com/packages/pdf/business/quantum-study.pdf ">http://graphics8.nytimes.com/packages/pdf/business/quantum-study.pdf </a><br>
<br>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:<br>
<br>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.<br>
<br>2) QAP problem, Quadratic Assignment Problem. The Traveling Salesman Problem is a special case of QAP.<br>     <br>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.<br>
<br>This is how D-wave's chip did in the competition with a very high end PC running the best algorithms known:<br><br>1) W2SAT problem: The D-wave chip did as well as the conventional computer but no better.<br><br>2) QAP problem: D-wave did better than the PC but not dramatically better.<br>
<br>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.<br>
<br>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.<br>
<br>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.<br>
<br>  John K Clark<br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br> <br><br> <br><br>