Simple simulated annealing template in C++11
I think the algorithm is well abstracted and the code is nicely written, so there is not all too much you can do in order to make it more efficient. Still I have some minor suggestions for improvement:

First, regarding the algorithm itself:

When the check if(e_new &lt; e_best) is successful, you can directly treat the step as accepted. Although this might be negligible, you avoid one more check.

In your check whether to accept the new step, you can think about choosing a cutoff (say ~ 10.0) parameter to bypass the relatively expensive calculation of std::exp as well as the random number generation.


Summarizing 1. and 2., one gets a slightly more verbose but hopefully more efficient code:
    if(e_new &lt; e_best){
        i_best =           i_new ;
        e_best =           e_new ;
        i_old  = std::move(i_new);
        e_old  = std::move(e_new);
        continue;
    }

    auto t = tf(c);
    auto delta_e = e_new - e_old;

    if( delta_e &gt; 10.0 * t) continue;  //as std::exp(-10.0) is a very small number

    if( delta_e &lt;= 0.0 || std::exp( - delta_e / t ) &gt; rf(g) ){
        i_old  = std::move(i_new);
        e_old  = std::move(e_new);
    }

Next, regarding your choice of functions: Here I would try to avoid expensive functions as well. I know, this might often not be possible as the functions are determined by your problem at hand. However, for example, in your temperature function you can think about replacing the std::exp(-20*k) by something more efficient such as 1/(k*k).

Regarding the language:

You can get a bit more of a C++11 touch if you use universal references instead of lvalue references.
template&lt;typename status, typename count, typename energy_function
       , typename temperature_function, typename next_function, typename generator&gt;
status simulated_annealing(status&amp;&amp; i_old, count&amp;&amp; c, energy_function&amp;&amp; ef
                         , temperature_function&amp;&amp; tf, next_function&amp;&amp; nf, generator&amp;&amp; g)
{
    //...
}

This is maybe also a bit more consistent with your std::move's of your status and count-type variables (which, as a side node, will resolve to simple copies when fundamental types such as double or size_t are used).
Further, you can think  about replacing your type count by size_t, since that is what this type is for. But this just because I personally try to avoid template parameters when possible.



Regarding the design:

The nf function can be made more generic by defining a static generator inside
long double nf(long double x){
    static std::mt19937_64 g(std::random_device());
    std::normal_distribution&lt;decltype(x)&gt; d(0, 1);
    return x + d(g);
}

I wouldn't pass a generator here, as it doesn't fit well into a generic desing. (For instance, the next state could also be found deterministically).

The same holds for your main simulated_annealing function. I wouldn't bother the user to define a random number generator, but just define it inside -- moreover since it is used &quot;only&quot; to create random numbers in [0,1] (once you've followed suggestion 4.).


        template&lt;typename status, typename count, typename energy_function
               , typename temperature_function, typename next_function&gt;
        status simulated_annealing(status&amp;&amp; i_old, count&amp;&amp; c, energy_function&amp;&amp; ef
                             , temperature_function&amp;&amp; tf, next_function&amp;&amp; nf)
        {
            std::mt19937_64 g(std::random_device());            
            //...
        }

This you can simply call the routine via
    root = simulated_annealing(root, count, ef, tf, nf);

which is more concise and better reflects the main components of a simulated annealing algorithm.