Annealing to Zen-Budha Ground State

Okay, so talking about D-wave is certainly not good for my Zen-Budha nature. Not good at all! So let’s talk about something related to D-wave but only tangentially so that I can get that Zen-Budha nature back.
One issue that comes up a lot in discussion about D-wave is simulated annealing. Wikipedia does a nice job defining simulating annealing. The basic idea is to mimic cooling in a physical system. Suppose you have a space of different configurations and some sort of energy function on this space. You’re goal is to find the lowest energy configuration because then you will be the coolest physicist on the block…and of course at the same time you might be solving some very hard computational problem. At a given step in the simulated annealing algorithm, you are in a given configuration and then you take a step in a neighborhood of this configuration. The probability of your particular change depends on a parameter T which is roughly the temperature. The simplest update rule is something like Metropolis Monte Carlo: if the energy is decreased, then always accept the change but if the energy is increased, accept this change with a probability [tex]$e^{-1/T}[/tex]. Of course more complex update rules are possible, but you get the idea. Then as a function of time you decrease the temperature and roughly freeze out the system. Hopefully when the temperature has reached zero you will either be at the global minimum energy or will have seen the global optimal energy. Okay, so a cool strategy for finding a global optimum. (Okay, okay, that will be my last temperature joke!)
But if there is one thing you learn when you begin to learn about classical algorithms it is that oftentimes what is good for solving one problem can be bad for solving other problems. Take, for example the maximum matching problem. A matching of a graph is a set of edges which do not share common vertices. The maximum matching problem is to find a matching with the largest number of edges. There is a classical algorithm for finding the maximum matching which runs in a time proportional to the number of edges times the square root of the number of vertices (due to Micali and V. Vazirani). In other words the running time of this algorithm is polynomial.
Now what happens if we run simulated annealing on this problem? Well of course simulated annealing is a meta-algorithm…there is a lot I haven’t specified. But just take a fairly generic and straightforward way of implementing simulated annealing for this problem. Then it was shown by Sasaki and Hajek that there exist bad instances for this approach. In other words simulated annealing fails to find the maximum matching in a time polynomial in the size of the graph. Doh! On the other hand, simulated annealing does find a “close” maximum matching for suitably small temperatures. This later fact is interesting, but what is more interesting to me is the fact that the simulated annealing algorithm fails where a classical polynomial time algorithm is known to exist.
So why does this all matter in the big scheme of things? Because one of the claims made by those who believe in D-wave is that their quantum system will outperform classical simulated annealing. But what does it mean to outperform classical simulated annealing if classical simulated annealing itself isn’t even the best classical algorithm? There is no simple answer to this question as far as I know, but it does give me pause everytime I see simulated annealing compared to some quantum version of this annealing.