Quantum computing is one of those weird ideas out there that will either change the world or go the way of cold fusion, so I periodically think I need to learn more about the area. I am by no means an expert (or even knowledgeable) in the area. My expertise comes from reading Scott Aaronson’s blog, which makes me as knowledgeable as about about a million other people out there. Seeing a series of papers showing how quantum computing can factor numbers is interesting, until you realize that the number involved are still well in the range of what my eight year old can do in his head. There are a lot better ways to spend my research time.
So, when a paper comes out involving using quantum computers to solve NP-hard problems (for a paper just presented at the ACM Conference on Computing Frontiers), I didn’t exactly leap at the opportunity to read it. That was until I saw the senior author: Cathy McGoech (the other coauthor is doctoral student Cong Wang). Cathy is the real deal. I have met her a few times, but I don’t know her well personally. But her research has had a big effect on me. Cathy, together with David Johnson (of Johnson and Garey fame) began the DIMACS Challenges twenty years ago. The goal in these challenges is to look at real-life algorithmic performance. The two of them ran the first Challenge (on Network Flows and Matchings); I ran the second Challenge, on cliques, coloring, and satisfiability. Cathy was extremely influential in how I thought about the Challenge. In particular, how can one distinguish between “fast coding” and “fast algorithms”? And what do interesting computational questions look like? I certainly never got to her level of sophistication when it comes to experimental design and evaluation, but her work made me better.
My research has moved off in my dillettante way to other things; Cathy has continued to work very hard to put experimental algorithmics on a solid footing. She even has a new book out on the topic (which I just ordered).
All this means: if Cathy is saying something about a computational evaluation, it is going to be worth listening to.
Short synopsis: Cathy and her coauthor got access to a D-Wave Two platform, heuristically solved a number of instances of three NP-Hard problems (Quadratic Unconstrained Binary Optimization, Weighted Maximum Two-Satisfiability, and Quadratic Assignment), and generally performed much faster than methods such as CPLEX.
The D-Wave platform has caused some controversy, since it is unclear what exactly happens in the system. The “holy grail”, as I understand it (it is not Aaronson’s fault if I get this wrong!) is quantum entanglement. This sort of “action at a distance” is key to much of the theory behind quantum computing. Does D-Wave get this? The paper covers this:
Finally there has been some debate as to whether D-Wave chips form a ‘truly’ quantum system; this has been demonstrated for smaller (8 and 16 qubit) systems … but
not, as yet, for the full hardware graph. Boixo et al.
report that the hardware demonstrates quantum tunneling
(which would be inconsistent with classical annealing), and
find some evidence of qubit entanglement. A recent review
article in Science [ Science, 13 May 2011] concludes that the hardware is at least a little quantum mechanical.
I suppose the researchers ended up at least a little tenured for this work.
But how does it work? Generally, pretty well:
In all three experiments the V5 hardware or its hybrid counterpart Blackbox found
solutions that tied or bettered the best solutions found by
software solvers. Performance was especially impressive on
instances that can be solved directly in hardware. On the
largest problem sizes tested, the V5 chip found optimal so-
lutions in less than half a second, while the best software
solver, CPLEX, needed 30 minutes to find all optimal solutions.We have also carried out some tests to compare V6 to
the software solvers; very preliminary results suggest that
on QUBO instances with n = 503, the hardware can find
optimal solutions around 10,000 times faster than CPLEX.
Pretty impressive sounding, and certainly something worth paying attention to.
But still, it is important to understand some key aspects of this work:
1) The solutions found are “just” heuristic solutions. There is no proof of optimality, nor can there be with the setup being used. In essence, we are getting a very fast population search with what looks like simulated annealing.
2) The comparator is primarily CPLEX, a code designed for finding and proving optimal solutions. I have refereed 3 papers in the last month alone that give heuristics that are orders of magnitude faster than CPLEX in finding good solutions. Of course, CPLEX is generally infinitely faster in proving optimality (since it wins whenever it proves optimality). Beating CPLEX by orders of magnitude on some problems in finding good solutions (particularly with short times) does not require fancy computing.
3) The problems chosen are not exactly in CPLEX’s sweet spot. Consider maximum weighted 2-SAT, where the goal is to maximize the weight of satisfied clauses in a satisfiability problem, where each clause has exactly two variables. The natural linear relaxation of this problem results in a solution with all variables taking on value .5, which gives no guidance to the branch-and-bound search. Now CPLEX has a lot of stuff going on to get around these problems, but there are certainly NP-Hard problems for which CPLEX has better relaxations, and hence better performance. And if you take any sort of problem and add complicating constraints (say, max weighted 2-sat with restrictions on the number of TRUE values in various subsets of variables), I’ll put my money on CPLEX.
4) The D-Wave system is still a bit pricey: at about $10,000,000, there are cheaper ways to get the sort of speedup that McGeoch and Wang found.
Cathy understands the comparator issue:
It would of course be interesting to see if highly tuned
implementations of, say, tabu search or simulated annealing
could compete with Blackbox or even QA on QUBO prob-
lems; some preliminary work on this question is underway.
Despite these qualms, Cathy has gotten me interested.
Google too, by the looks of it.
Be sure to check out Scott Aaronson’s take on this, as he resumes his role as “Chief D-Wave Skeptic”.