Update 20100607: Physics and Cake’s take.
Update 20100607: Shtetl-Optimized’s view. Vicky Choi weighs in with excellent points in the comments section.
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).
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.