I think the idea is that from the output state and the program used to generate it, you have the information to exactly reverse the process and get back to the original input.

In something like an AND gate, you can't do that. I output 0...what were the two inputs? {0,0}, {0,1}, or {1,0}? And electrically, in 3/4 of the cases, you've got an input being sent to ground, using the electricity when you discard the bit of information.