{"id":2400,"date":"2009-08-21T10:30:40","date_gmt":"2009-08-21T17:30:40","guid":{"rendered":"http:\/\/dabacon.org\/pontiff\/?p=2400"},"modified":"2009-08-21T10:30:40","modified_gmt":"2009-08-21T17:30:40","slug":"adiabaticly-failing-for-random-instances","status":"publish","type":"post","link":"https:\/\/dabacon.org\/pontiff\/2009\/08\/21\/adiabaticly-failing-for-random-instances\/","title":{"rendered":"Adiabaticly Failing for Random Instances"},"content":{"rendered":"

An interesting paper on the arXiv’s today, arXiv:0908.2782<\/a>, “Adiabatic quantum optimization fails for random instances of NP-complete problems” by Boris Altshuler, Hari Krovi, and Jeremie Roland. Trouble for D-wave<\/a>?
\n
\nAdiabatic quantum algorithms are a set of techniques for designing quantum algorithms based upon the adiabatic theorem in quantum physics. The basic idea is as follows: (1) take the problem you are trying to solve and convert it to a Hamiltonian whose ground state (you could use other energy eigenstates, but in general this is not done) is the solution to this problem, (2) Prepare the system in the ground state of some easily constructed Hamiltonian which has the same number of qubits (or qudits) as the Hamiltonian from (1), and finally (3) turn off the Hamiltonian from (2) while turning on the Hamiltonian from (1). The adiabatic theorem then tells you that if you go slow enough in this dragging of one Hamiltonian to another, then you will end up in the ground state of the Hamiltonian from (1), and hence you can solve your problem by reading out the answer after this evolution. How slowly you have to go depends on a few things, but most importantly it depends on the minimum eigenvalue gap between the ground state and the first excited state of the system during the evolution. If this minimum gap scales inversely as a polynomial in the problem size, then the adiabatic theorem will guarantee that the algorithm succeeds with high probability running in a time polynomial in the size of the problem. I.e. minimum eigenvalue gap = inverse polynomial is good \/ minimum eigenvalue gap = inverse exponential is bad.
\nAdiabatic optimization algorithms are a distinct class of adiabatic algorithms in which the final Hamiltonian you are dealing with is really some “classical” optimization problem (as opposed to more general adiabatic quantum algorithms, which include things like a universal quantum computing simulator and thus there exists an adiabatic quantum algorithm for, say, factoring a number.) There is a long history of studying these problems and at times there has been optimism that adiabatic quantum optimizations might be able to efficiently solve NP-complete problems. This would, of course, be an amazing computationl breakthrough, so there has also been a lot of skepticism about this result. Beyond mere skepticism there has also been work that shows that for particular instances of the adiabatic quantum optimization, and for particular was to carry out the adiabatic evolution, the algorithm will take an exponentially long time to finish. One example of such work is that of van Dam, Mosca, and Vazirani (arXiv:quant-ph\/0206033<\/a>) who explicit examples where a particular scheme for adiabatic quantum optimization requires exponential time. Updated 9\/11\/09 text follows:<\/b> The example used in this paper uses a cost function (target Hamiltonian) which is very non-local and tailored to defeat the algorithm. A more local, i.e. 3-SAT instance of this version of result was produced by van Dam and Vazirani, but never published. However this negative result was followed by a positive result: Farhi, Goldstone and Gutman showed in quant-ph\/0208135<\/a> that if one selects a randomly varying path then the local example of van Dam and Vazirani does not pose a problem.
\nGiven these negative and positive results, the picture is not clear. For example the special cases that make the algorithm fail needed to be hacked to get into a form where they were solved efficiently. This indicates to me, at least, a dangerous slope: anyone attempting to prove that a particular instance is hard will end up in a situation where the authors just modify the algorithm to defeat this instance. But of course, it could be that the randomly varying path approach of Farhi, Goldstone, and Gutman is the end of the story. Of course whatever the answer is as to what the gap is for particular instances, one might also argue that the the specially considered instances are not the ones that one encounters in the real world, and thus these cases are not important from a practical perspective. End updated text 9\/11\/09<\/b>. What the paper above (arXiv:0908.2782<\/a>) does is shows that, in some sense, this is not true. Now because we do not have a model of what a “real world’ instance of an NP-complete problem is from a mathematical perspective, what the authors substitute is a “random instance” of the problem. Whether this is a good proxy is a subject for great debate<\/a>, but that withstanding, the authors plow on ahead. And what they show is that for random instances of an NP-complete problem called exact cover 3, the adiabatic optimization algorithm will require an exponentially long amount of time to solve the instances.
\nWhat does this all mean? Well it is another nail in the coffin for those who believe that adiabatic quantum optimization algorithms can efficiently solve NP-complete problems. Is it the end of the story. Certainly not. Why? Well there are all sorts of interesting questions: the eigenvalue gap estimated by the author scales as O(n-1\/8<\/sup>). I don’t know enough about the classically best algorithms for exact cover 3, but it seems to me that if this is the real scaling then this would imply a polynomially sped up quantum algorithm for this problem. Also its still not at all clear how the initial Hamiltonian and subsequent path it takes to get to the final Hamiltonian influences adiabatic quantum algorithms. Another interesting point is that the eigenvalue gap the authors can prove is exponentially shrinking only starts to show up, by their estimates, when n is above 86000 (maybe lower, but their argument is heuristic for the lower value.) Maybe it is true that adiabatic quantum algorithms are better than classical algorithms up to a certain instance size (a failure of big-O notation, so to speak.)
\nWhat does all this mean for D-wave, who is trying to build an adiabatic quantum optimizer? Well it’s uncertain. They certainly won’t be happy to have another negative theoretical result to bash their heads up against. On the other hand, the real question, of course, is whether when you put the real numbers in, does their adiabatic machine outperform the best classical algorithms. As a betting man, however, I think some priors just got shifted in a negative direction.
\nUpdate 9\/11\/09:<\/b> I have added text above to clarify the story a bit after conversations with Ed Farhi. Also I would recommend anyone interested in this topic to check out the comments below which illuminate the situation even more.<\/p>\n","protected":false},"excerpt":{"rendered":"

An interesting paper on the arXiv’s today, arXiv:0908.2782, “Adiabatic quantum optimization fails for random instances of NP-complete problems” by Boris Altshuler, Hari Krovi, and Jeremie Roland. Trouble for D-wave?<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[65],"tags":[],"class_list":["post-2400","post","type-post","status-publish","format-standard","hentry","category-quantum-computing"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/2400","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/comments?post=2400"}],"version-history":[{"count":0,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/2400\/revisions"}],"wp:attachment":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/media?parent=2400"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/categories?post=2400"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/tags?post=2400"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}