Logically (and therefore thermodynamically) reversible. By Landauer's principle, the only reason a computer must emit heat (and therefore use energy) is to perform irreversible operations. Therefore, if you want a computer that (potentially) uses the minimum energy, it needs to be reversible in this sense.

An irreversible operation is anything that maps many (possible) states to the same state. Setting a bit to zero is irreversible (because it destroys the information about what bit was there previously). An AND gate is irreversible (because both TF and FT map to F). A NOT gate is reversible (because you can infer the input from the output.)

There are universal reversible gates (Toffoli and Fredkin gates are examples, but there are many others), so you can (theoretically) build a (usable) computer whose logical operations are completely reversible.

"Reversible" means that the physical processes which implement the computation (e.g. electricity flowing through wires, marbles running down tracks, etc.) can all be run backwards as well as forwards.

Think about pumping water up a hill: we have to spend energy to move it up; but it's reversible: by moving the water back down we receive energy (e.g. hydroelectric). This isn't completely reversible, since we lose a lot of energy to friction and turbulence that we can't get back. Some microscopic systems don't have such losses, e.g. gas molecules will bounce around without losing energy (gases don't spontaneously cool down). Could we use such microscopic systems to implement a computer?

From the computational side, the only logical operation which is irreversible is discarding information, e.g. overwriting some stored value with a different value. As long as we have the same amount of information out as we put in, we can run a computation in reverse: calculating the input, given the output.

Most computations take a big bunch of data as input, and produce some small output (e.g. averaging a single field from a list of records). This clearly throws away information. We can adjust this calculation to be reversible, by outputting the value we want (e.g. that average) as well as a bunch of extra "junk", which encodes all of the input data that we didn't use. Given a pair of an average and some "junk", we can compute the input which gave rise to that pair.

So why do this? If our computation is reversible, we can run our computer forwards, copy out the portion of the result we care about to somewhere else, then run the computer backwards to get it back to the state it started in. This way, we've performed our computation without using up any energy. There may be a slight loss outside the computer, if we store that result by overwriting some previous value in an irreversible way; but even this energy cost depends only on the size of the value we're copying out. We can perform an arbitrarily large amount of computation, e.g. a lengthy brute force search, and as long as the portion of the output we care about (i.e. not the "junk") is small, say a single integer, we can recover almost all of the energy used by that computation.