Understanding simulated annealing information theoretically So I recently rediscovered simulated annealing though a path that others seem to be well aware of. I was aware of Metropolis-Hastings as a sampling algorithm that creates a Markov-Chain who's stationary distribution is the distribution produced by normalizing some function. It's a small leap to realize that you can use this to optimize lots of things and you can even keep rejections that happen to be the minimum you've found so far. But further more you could also reshape the cost function so that it rewards the optimum with much higher probability than anything else (say by exponentiation or squaring the function or something). This has the effect of lowering the entropy of the normalized distribution. If we reshape the target distribution too much though our mixing times could be quite bad. We can solve this by gradually reshaping the target distribution to a low entropy distribution however. Further more higher entropy target distributions should (I think? A proof would be appreciated) have lower mixing times so if our actual target function has low entropy and long mixing times we can fix that. After one researches this line of thinking it quickly becomes clear that this is simulated annealing from a different angle than its generally presented.

The notion of entropy used in physics is deeply connected (or so I'm told) to the notion of entropy used in information theory (which is why Shannon named it as such). The physical notion of entropy is deeply connected to temperature. I've never taken thermodynamics so I don't really understand the bridge between information theoretical entropy, and temperature (which has physical entropy in the middle as the bridge).

Can this link be explained? Given a probability distribution can we define the "temperature" of the distribution? Is there an information theoretical way to define temperature? Perhaps only a subset of distributions have a temperature but we can generate probability distributions that correspond to a given temperature? I'm trying to understand the notion of temperature used in simulated annealing without learning about thermodynamics.

To give a better example of what I'm trying to ask I'll ask by analogy. Understanding what a quantum circuit is doesn't require understanding much of anything about quantum physics for a computer scientist. What's the equivalent understanding of temperature for a computer scientist that knows a bit about information theory?
Along the lines of entropy, what you are trying to get to when using Metropolis or Simulated Annealing is a low entropy state.  You want to find order within the disorder.  Now, Metropolis and Simulated Annealing are slightly different things.  Metropolis' goal is not to find the absolute minimum entropy, it is to recreate a distribution, which may be single mode.  What simulated annealing does is focus the Metropolis to find the absolute minimum.
So in annealing you start at a high temperature, which means basically that anything is possible.  Think of quantum tunneling.  The most improbable thing can happen when temperatures are very high.  So when we begin the optimization, we allow for a whole lot of jumps that you would not see otherwise.  As you cool you focus on just what makes sense so that jumps are made only when they are better.
At a high temperature you will accept propositions at a higher rate to test the space and eventually you stop accepting these wacky ideas to focus on the best solutions only.  In the end you should have a good idea of the optimal solution.