Adiabatic quantum computing is the greatest idea in the history of humanity

Update 20100607: Physics and Cake’s take.

Update 20100607: Shtetl-Optimized’s view. Vicky Choi weighs in with excellent points in the comments section.

Update 20100607: The Pontiff’s Tale, not to be confused with The Ancestor”s Tale.

Many areas of science and technology have some adversarial character naturally built into them. For example in cryptography, code-makers and code-breakers have been waging an escalating battle against each other for literally hundreds of years. I suspect that the code-makers are doomed to eventually lose.

Another battleground is in NP-hard combinatorial optimization and NP-complete constraint satisfaction problems. Although both categories are formally intractable, that does not mean that there isn’t a lot of room for some friendly warfare.

Imagine this scenario. Say I’m IBM, and I notice that I can perform a potentially important business function (for example, formally verifying that a particular hardware design behaves the way it should), but I can only do this if I can solve a bunch of 3-SAT problems of a certain type.  So I go and hire ten of the smartest algorithms people I can find, and tell them: OK crack team, you need to come up with an algorithm for solving the particular type of SAT problem my application is generating, and it needs to do it fast enough so that I can use the results. Then these folks go away, think about it for a while, and then return with a solver that exploits the particular structure of the problem the application is generating. The algorithm works superbly and solves those problems! It turns out that these instances weren’t so hard (for 10 phds working for 6 months) after all.

Now here’s where the adversarial opportunity arises. Imagine now I’m Intel, and I have an application I’d like to run that also generates 3-SAT problems (say place and route), so I headhunt the entire team and ask them to apply their solver to this new type of instance. Horribly, they find it doesn’t work! So they go away and a few months later, they come back with a different solver that solves the new set of problems!

Optimization and constraint satisfaction are both like this in the real world. A war rages on between people who try to find instances that can stymie any solver (sometimes unwittingly because they want a real-world problem solved, and sometimes on purpose because it’s fun to come up with hard problems), and the brilliant algorithms developers who look for tiny chinks in the armor to build special-purpose solvers to defeat those instances.

About a year ago at a conference in Japan, one of our scientists was discussing an idea with a well-known theoretical physicist. The idea was one way that you could construct a really hard type of instance that would be difficult for a specific approach to adiabatic quantum optimization. Technically this idea is based on the notion of a first order quantum phase transition. While it is extremely complex to figure out what happens to the algorithm with or without one, it is likely the case that having one is worse than not having one (although even this is not entirely clear, when you add in real thermal environments — but that’s a whole other can of worms).

This other physicist then wrote some papers with some very interesting results and claims. One of the interesting things from a sociological / psychological perspective is the choice of titles for these articles: Adiabatic quantum optimization fails for random instances of NP-complete problems and Anderson localization casts clouds over adiabatic quantum optimization. These choices for titles — so definitive and clear — make a bold statement: these algorithms fail, by which is meant in common parlance that they don’t work at all. They are a bad idea. Don’t go down that road. Surprisingly though, you could have kept every single word in say the first paper identical, and called it “Adiabatic quantum optimization outperforms all known classical algorithms for a wide range of problems” and it still would have fit the text perfectly. Aside: it’s always been a subject of some fascination to me how two people can look at exactly the same thing and come to widely differing conclusions on its meaning (explained beautifully in Bayesian terms in Jaynes’ classic Probability Theory: The Logic of Science).

As you might expect, eventually journalists learned of the titles of these articles and communicated the message in the titles to a wide audience.

But hold on a minute. Maybe there is a way around these problems?  I’m not sure if their argument is technically correct — there are some subtleties in it. But (of course) there are ways around the issue, if it really is an issue — several of these were discovered and published very quickly after these papers came out.

These clever solutions aren’t the end of the story. For now the adiabatic quantum optimizers have the upper hand. But soon there will be another announcement of a hard instance type — but then some smart quantum optimizers will find a way around it. And then another hard problem will be found, and then the quantum optimizers will find a way around it, ad nauseum. Just like in the battle between code-makers and code-breakers, the battle between people finding hard problems for adiabatic quantum optimization, and the legion of smart folks finding ways to defeat those hard problems will continue to rage for some time.

15 thoughts on “Adiabatic quantum computing is the greatest idea in the history of humanity

  1. Pingback: what should i write on my justin bieber shirt? : justin bieber clumb

  2. I think a Justin Bieber shirt with “Adiabatic quantum computing is the greatest idea in the history of humanity” written on it is the greatest idea in the history of humanity.

  3. A nice irony here is this post has 5 comments already why the previous post anouncing arXiv:1006.0028 has zero. And that paper has some impressive and important results. That and some seriously good looking data.

  4. What’s the distribution of 3-SAT instances for which adiabatic QC (of the H(s) = s \sum_{i=1}^n \sigma_x^i + (1-s) \sum_{x\in \{0,1\}^n} f(x) |x><x| flavor) outperforms every known classical algorithm? I wasn't aware that one was known. (The closest to this claim that I've seen is in quant-ph/0201031, which only compares against a specific classical algorithm.)

  5. Hi Aram

    If you believe the argument that the scaling of the minimum gap sets the runtime of the algorithm, simply take an unstructured search problem and map it in to 3-SAT. I believe for those instances you get provable separation based on the O(N) requirement for classical search vs. the possibility of O(\sqrt(N)) for quantum search. There are several other pieces of evidence for structured cases (like Peter Young’s papers) where there might be a range of N (not asymptotically large) where the exponential in the quantum case doesn’t bite you in practice until N gets quite large.

    However…

    After much pondering on the implications of our recent experiments, I think I’ve become convinced that decision problems are not the best types of problems to apply this approach to, at least for now. The reason isn’t so much the exponential vs. polynomial gap question, as the practical issue is that as long as the gap gets smaller as N grows, there eventually reaches a point where the temperature of the environment gets bigger than the typical spacing of energy eigenvalues during evolution. This will happen even for polynomially shrinking gaps. (It even happens for constant gaps, if the gap is small enough.)

    When this happens, the central quantum system attempts to thermalize with the environment, and excited states will get occupied. Note that this mechanism is not all bad. For example, imagine there is only one very small gap. If the system thermalizes prior to the crossing at this gap, there is weight in the state that eventually becomes the global minimum before the anticrossing. because the gap is basically zero, the state maintains its pre-crossing probability and “drags” it into the true ground state. It’s for reasons like this that I don’t completely buy the current argument that the scaling of the minimum gap sets the runtime for these algorithms. Real thermal environments, which are always there, qualitatively change the outcome of these calculations in complicated ways. For example you need to know the density of low-lying energy eigenstates, not just the minimum gap, when the temperature isn’t zero.

    An implication of this is adiabatic quantum optimization in the presence of temperature is intrinsically stochastic / heuristic.

    (Basically what I’m saying is you need to keep an open quantum systems description in any analysis of the complexity of the algorithm. I just don’t believe the results from any T=0 analysis).

    To circle back to your original question: it’s much more likely that adiabatic quantum optimization will find its niche quickly generating Boltzmann-like output probability distributions for Weighted MAX2SAT (with the caveat that the “Boltzmann-like” is heuristic and is not guaranteed for all cases) than exactly solving 3-SAT or the like. This is why I like the machine learning applications space. In that space, Boltzmann machines have alot of utility, underlying very cool approaches to minimally supervised learning (deep neural nets and the like).

  6. Pingback: An Adiabatic Tale of the Cat and Mouse - The Quantum Pontiff

  7. hi, the quantum computer is already here in multiple universities and private homes,but functions as a 1950`s computer,not very well.The way past this is to do accurute measurments on important subjects,like the exact diameter of many galaxies light year magnetic field distance to the exact ,lets say millimeter, so for example the milkyway today is 200,000 light years with a magnetic field of 200,000 times earths gives us the periodic tables nuclear make up.But like measuring quantum nuclie is hard ,but nessary to be exact,you must get the light measurements to the exact millimeter of a galaxy of lets say milkyway 275,984.876599 lightyears, after all like a quantum nulie the galaxy is not even there,its in another place,so to make a quantum computer work (and make it practical)you must freeze a nuclie in all the periodic tables elements to near zero,and get very very accurate measurings of galaxies diameter(which will equal the magnetic field of the galaxy).remember you are measuring a galaxy thats NOT there!So by testing each elements to galaxies you will create a quantum program algorthim, this will of course change the peridic table to elements needed to create a quantum computer that doesn`t need to freeze nuclies,it will work through cloud quantum servers.

  8. _—______—–___-__-__-_—_

    Great website! I think there are many valuable information and advices here. Along the same line, I came across the following website which I found interesting. Traditionally, personality tests such as MBTI have been used as career aptitude test. However, these tests have a very limited scope as they ignore many important factors such as person’s skills, values, and interests.

    There have been many advancements in the area of career aptitude testing. Usage of artificial intelligence to evaluate suitability of a job for a person is one of the these techniques. You can take a complete version of the MBTI personality test plus many others such as memory, IQ, problem solving, and patience tests in OptYourLife. This website’s expert system tries to find the most suitable career path for you using neural network. Moreover, salary of different careers will be considered in the final analysis to provide a more insightful advice for you:

    http://www.optyourlife [dot] com/

    —_-_—_-_-____-_–_-_-__–_

  9. Pingback: CIA and Jeff Bezos Bet on Dwave Systems’ Adiabatic Quantum Computing | Datacentre Management . org

  10. There is a market out there for all types of shoes. These few selling tips can assist you in
    selling effectively and get you on your way to turning into a
    top notch Power – Seller. You can use your own Merchant Account, set-up a new
    Merchant Account, or use Pay – Pal to collect money from your customers
    all over the World.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s