{"id":1786,"date":"2013-05-16T11:46:24","date_gmt":"2013-05-16T15:46:24","guid":{"rendered":"http:\/\/mat.tepper.cmu.edu\/blog\/?p=1786"},"modified":"2013-05-16T11:46:24","modified_gmt":"2013-05-16T15:46:24","slug":"quantum-computing-and-operations-research","status":"publish","type":"post","link":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/2013\/05\/16\/quantum-computing-and-operations-research\/","title":{"rendered":"Quantum computing and operations research"},"content":{"rendered":"

Quantum computing<\/a> is one of those weird ideas out there that will either change the world or go the way of \u00a0cold fusion<\/a>, so I periodically think I need to learn more about the area.\u00a0I am by no means an expert (or even knowledgeable) in the area. \u00a0My expertise comes from reading Scott Aaronson’s blog<\/a>, which makes me as knowledgeable as about about a million other people out there. \u00a0 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<\/a>. \u00a0There are a lot better ways to spend my research time.<\/p>\n

So, when a paper comes out involving using quantum computers to solve NP-hard problems<\/a>\u00a0(for a paper just presented at the ACM Conference on Computing Frontiers<\/a>), I didn’t exactly leap at the opportunity to read it. \u00a0That was until I saw the senior author: Cathy McGoech<\/a>\u00a0(the other coauthor is doctoral student Cong Wang). \u00a0Cathy is the real deal. \u00a0I have met her a few times, but I don’t know her well personally. \u00a0But her research has had a big effect on me. \u00a0Cathy, together with David Johnson<\/a> (of Johnson and Garey fame) began the DIMACS Challenges<\/a> twenty years ago. \u00a0The goal in these challenges is to look at real-life algorithmic performance. \u00a0The two of them ran the first Challenge (on Network Flows and Matchings); \u00a0I ran the second Challenge, on cliques, coloring, and satisfiability. \u00a0Cathy was extremely influential in how I thought about the Challenge. \u00a0In particular, how can one distinguish between “fast coding” and “fast algorithms”? \u00a0And what do interesting computational questions look like? \u00a0I certainly never got to her level of sophistication when it comes to experimental design and evaluation, but her work made me better.<\/p>\n

My research has moved off in my dillettante way to other things; \u00a0Cathy has continued to work very hard to put experimental algorithmics on a solid footing. \u00a0She even has a new book out<\/a> on the topic (which I just ordered).<\/p>\n

All this means: if Cathy is saying something about a computational evaluation, it is going to be worth listening to.<\/p>\n

Short synopsis: \u00a0Cathy and her coauthor got access to a D-Wave Two platform<\/a>, heuristically solved a number of instances of three NP-Hard problems (Quadratic Unconstrained Binary Optimization, Weighted Maximum Two-Satisfiability, and Quadratic Assignment),\u00a0\u00a0and generally performed much faster than methods such as CPLEX<\/a>.<\/p>\n

The D-Wave platform has caused some controversy, since it is unclear what exactly happens in the system. \u00a0The “holy grail”, as I understand it (it is not Aaronson’s fault if I get this wrong!) is quantum entanglement<\/a>. \u00a0This sort of “action at a distance” is key to much of the theory behind quantum computing. \u00a0Does D-Wave get this? \u00a0The paper covers this:<\/p>\n

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
\nnot, as yet, for the full hardware graph. Boixo et al.\u00a0<\/a>
\nreport that the hardware demonstrates quantum tunneling
\n(which would be inconsistent with classical annealing), and
\nfind some evidence of qubit entanglement. A recent review
\narticle in Science [ Science, 13 May 2011<\/a>] concludes that the\u00a0hardware is at\u00a0least a little quantum mechanical.<\/p><\/blockquote>\n

I suppose the researchers ended up at least a little tenured for this work.<\/p>\n

But how does it work? \u00a0Generally, pretty well:<\/p>\n

In all three experiments\u00a0the V5 hardware or its hybrid counterpart Blackbox found
\nsolutions that tied or bettered the best solutions found by
\nsoftware solvers. Performance was especially impressive on
\ninstances that can be solved directly in hardware. On the
\nlargest problem sizes tested, the V5 chip found optimal so-
\nlutions in less than half a second, while the best software
\nsolver, CPLEX, needed 30 minutes to find all optimal solutions.<\/p>\n

We have also carried out some tests to compare V6 to
\nthe software solvers; very preliminary results suggest that
\non QUBO instances with n = 503, the hardware can find
\noptimal solutions around 10,000 times faster than CPLEX.<\/p><\/blockquote>\n

Pretty impressive sounding, and certainly something worth paying attention to.<\/p>\n

But still, it is important to understand some key aspects of this work:<\/p>\n

1) The solutions found are “just” heuristic solutions. \u00a0There is no proof of optimality, nor can there be with the setup being used. \u00a0In essence, we are getting a very fast population search with what looks like simulated annealing.<\/p>\n

2) The comparator is primarily CPLEX, a code designed for finding and proving optimal solutions. \u00a0I have refereed 3 papers in the last month alone that give heuristics that are orders of magnitude faster than CPLEX in finding good solutions. \u00a0Of course, CPLEX is generally infinitely faster in proving optimality (since it wins whenever<\/em> it proves optimality). \u00a0Beating CPLEX by orders of magnitude on some problems in finding good solutions (particularly with short times) does not require fancy computing.<\/p>\n

3) The problems chosen are not exactly in CPLEX’s sweet spot. \u00a0Consider 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. \u00a0The 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. \u00a0Now 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. \u00a0And if you take any sort of problem and add complicating constraints (say, max weighted 2-sat with restrictions on the number of \u00a0TRUE values in various subsets of variables), I’ll put my money on CPLEX.<\/p>\n

4) The D-Wave system is still a bit pricey: \u00a0at about $10,000,000, there are cheaper ways to get the sort of speedup that McGeoch and Wang found.<\/p>\n

Cathy understands the comparator issue:<\/p>\n

It would of course be interesting to see if highly tuned
\nimplementations of, say, tabu search or simulated annealing
\ncould compete with Blackbox or even QA on QUBO prob-
\nlems; some preliminary work on this question is underway.<\/p><\/blockquote>\n

Despite these qualms, Cathy has gotten me interested.<\/p>\n

Google too<\/a>, by the looks of it.<\/p>\n

Be sure to check out Scott Aaronson’s take on this<\/a>, as he resumes his role as “Chief D-Wave Skeptic”.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"

Quantum computing is one of those weird ideas out there that will either change the world or go the way of \u00a0cold fusion, so I periodically think I need to learn more about the area.\u00a0I am by no means an expert (or even knowledgeable) in the area. \u00a0My expertise comes from reading Scott Aaronson’s blog, … Continue reading “Quantum computing and operations research”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12,46],"tags":[],"class_list":["post-1786","post","type-post","status-publish","format-standard","hentry","category-computing","category-research"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1786","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=1786"}],"version-history":[{"count":0,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1786\/revisions"}],"wp:attachment":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=1786"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=1786"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=1786"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}