[aifer4]

Definitely. Landauer's principle gives a lower bound on the amount of energy a computation requires, which is k_B T ln(2) times the number of bits erased in the process, the decrease in Shannon entropy. Our energy cost analysis is not based on the Landauer limit, but simply on the energy difference between equilibrium states. But our algorithm for estimating the determinant is based on effectively measuring the entropy difference between equilibrium states.

[canjobear]

I always have trouble thinking of computation in terms of “bits erased”. How many bits are erased when I sort an array? Or invert a matrix? Or compute a function like f(x)=1, which seems to maximally erase information, but doesn’t intuitively seem like it should cost a lot of energy.

[aifer4]

To answer your question about sorting an array: For an array of length n, where each element takes one of m possible values, there are n^m possible arrays. But there are only O(n^m/n!) possible sorted arrays, which could be crudely approximated as O(n^(m-n)). The decrease in information is proportional to the log of the ratio of the number of possible states before and after the computation, which is in this case log(n^n) = n log n. See another explanation here https://tildesites.bowdoin.edu/~ltoma/teaching/cs231/fall07/...