The Coldest Point in the Universe is in Burnaby, BC

I attended a presentation yesterday at the Telus Sphere of Science Word of Telus World, or whatever they're calling it these days, by D-Wave systems, The Quantum Computing Company™. These are the folks who surprised a lot people, myself included, by announcing their plans to have a commercial quantum computer ready to complete real work by 2008. The crowd lined up outside the sphere was overwhelmingly male, but other than that a good cross-section of the lower-mainland population. We picked up our pre-registration nametags and were herded into a smallish theater on the second floor.

There was a lot of congratulatory talk and thank-yous for investors and employees, and then the CTO of the company, Geordie Rose took the floor to explain a little bit about the proof-of-concept that they've developed. The computer is a 5-millimeter-square chunk of niobium cooled to a temperature of four millikelvins (hence the title of this post). The 16-qubit proof-of-concept is roughly a hundred times slower than a thousand-dollar PC, but apparently it works, and the company is confident that they can scale it up rapidly to the 1000-qubit mark, where the device will become notably faster for certain classes of problems than existing digital computers.

While most people that know a little bit about computing technologies have predicted that quantum computers are about fifty years away from commercialization, something that is technically a five-qubit computer is available for sale right now. The fifty-year number is basically a wild-ass guess of the people trying to develop so-called "gate model" quantum computers, which mimic the functionality of a conventional microprocessor using quantum devices rather than transistors. D-Wave is using an entirely different approach: an analog computer. Not analog in the sense of "continuously varying," but analog in the sense that the manifestation on their four-by-four grid of qubits is analogous to a graph that represents the problem they are trying to solve.

What sorts of problems might those be? They are currently targeting applications in the life sciences (drug database searches and protein folding), molecular simulations, and more general database searches. In mathematical terms, they hope to dramatically speed up the classes of problems known by mathematicians as NP-complete and NP-hard. As an example he used a graph of the shortest path that visits every city in Sweden (no bork jokes, please). With current technology it would take a state-of-the-art PC about 85 years to solve, but it could potentially be solved in minutes by a quantum computer. One of the things any crypto-geek who's seen Sneakers would ask is can it be used to quickly factor large numbers*. The answer is "yes, it can," although this fact was strongly downplayed by Mr. Rose when someone brought it up in the post-presentation question period. Apparently saying that accelerating NP-complete problem solving was a good way of getting funding for QC research back in the '90's, since that sort of acceleration could have a significant impact on the field of public-key cryptology.

The way that the system is configured is that each of the sixteen qubits is connected by a variable link to each of it's eight nearest neighbors (or five in edge-cases and three in corner cases). Each qubit and each connection is biased in a certain direction, and over time they assume the lowest (or second-lowest) energy state, which represents the best (or second-best) solution to the problem, which is then read and transmitted back to the user. If the qubits represent wedding guests (one of the demonstrations), and Joanne really wants to sit near a window, but not at the same table that John is sitting, that fact is represented in a the set of initial biases, and the lowest-energy state that results is the optimal arrangement of guests at the wedding.

Future work, aside from ramping up the number of qubits also involves connecting each qubit in the array to every other qubit. The other piece of the puzzle, and the reason for the public demo, is to generate interest and get people thinking of interesting optimization problems that a future commercial implementation of this type of computer could support.

The problems that were demonstrated were a molecule search (which can be represented as a max independent set problem), the aforementioned seating plan, and a round of SudoQ. However, the fact that the solutions were obtained about one hundred times slower than a modern PC coupled with the fact that the machine, residing a few kilometers away in Burnaby, was accessed through a somewhat hollywood-OS like interface means that I could not swear in a court of law that they actually had a working quantum computer. But my gut feeling is that they have something working at the level that most early-stage demos do, with a bit of sleight of hand and selective choice of subject matter making the thing appear about as functional as it is, though much, much friendlier.

After the question period was closed, I grabbed a fancy poster of their device in its sample holder on the way out and made my way to the SkyTrain.

* I was a bit chagrined that the question that was actually asked was whether a QC could accelerate the factoring of large prime numbers. I will go on record as saying that I can factor any large prime number in only very slightly more time than it takes you to tell me what the number is.