# P=NP and other trivia

By **
joe
**

Ok, well, not quite. But apparently the folks over at D-Wave have a quantum computer about to be shown solving a real problem. Talk about accelerated computing …

They are somewhat flippant about pointing out that this is an NP problem solver. So if we have some little NP problem, like, I dunno, Ising models in the presence of a magnetic field, this thing ought to be able to solve it. The question is … how fast. The second question is … how do you program a quantum computer. The third question people are asking is, is this really a quantum computer. If they can repeatably perform NP complete problems (of reasonable scale) in a reasonable time, this could prove to be very interesting. Quantum computers work by exploring (in parallel) multiple states. Think of them as following something like an ergodic principle, but not serially. They do it in a massively parallel way. So massively parallel (even with very few qubits), that you might call a CM-5 a serial computer in comparison. You basically instantiate the starting state, “configure” the Hamiltonian (only real tunables are the potential energy), and then let er rip … or time evolve to your (hopefully stationary) stable state. The stable state is the solution. If it exists. Leave the existence proofs to the mathematicians. Previously, to build a multi-qubit system, you needed a vacuum chamber, some lasers, and some rubidium or similar atoms in an optical trap. With this scenario, you were able to generate an entanglement of wavefunctions. Programming this wasn’t trivial, as there weren’t any compilers for them. Ok, that was the least of the worries. D-wave (their name taken from some of the higher angular momentum states of superconducting systems) appears to be using SQUIDs (superconducting quantum interference devices) which have some interesting properties. This is interesting to me personally as my father worked on some of this stuff at IBM for a while, trying to build computers from Josephson junctions (which are at the heart of SQUIDs). This is exciting news if they have achieved something pragmatic. IBM never could quite control the materials well enough to build a practical circuit. That and the helium refrigerators would have been big turnoffs for customers. Liquid cooling is bad enough. Liquid cooling at 4 degrees above absolute zero is, well, somewhat of a more difficult sell. What worried me was what happened if the cryogenic system developed a leak/blockage. You can’t just call a plumber for this … Even the Hi-Tc stuff I worked with (curiously, at IBM) years later relies upon LN2 (liquid nitrogren). You can have a really bad day with that stuff if you are not careful. LHe (liquid helium) demands even more respect. Best of luck with the demo, I hope it works well, and if they want to talk about pattern matching (or factoring large integers quickly), that could be a fun conversation.