It's mentioned in a textbook for quantum information that many classical logic gates such as the NAND gate are inherently irreversible. I'm confused why this is true. What does it mean by reversible? Why isn't NAND reversible?
That is because a logic gate have one or more inputs, and only the inputs determine the output.
If you have two inputs on a logic gate, and you only know the output, you can't determine what the inputs were in all cases, if you only see the output.
If you draw a truth table for all four cases of NAND inputs and outputs, since there is three cases where output is logic one, if the output is logic one, you can't work backwards which of the three cases was input to it.
However, if the output is a logic zero, you know that there's only one case for it to happen, and that's when both inputs are logic one.
Below is quoted from a page on WikiPedia
Reversibility is that the relation of the mapping from states to their successors must be one-to-one.
For a NAND, C = /(A + B), when C='1', "A=0 & B=0, A=0 & B=1, and A=1 & B=0" are mapped as the input combinations. Thus, NAND is irreversible.
This idea has been explored and is often called "adiabatic logic". It can be built with CMOS transistors. I haven't read much about it lately, and my recollection is that the logic circuits are very slow.
More information is here: https://en.wikipedia.org/wiki/Adiabatic_circuit
The practical answer is that developing reversible logic would have meant using more transistors in a time when the numbers of transistors available was severely limited.
From a more abstract perspective, look at it this way. You can't get more information out of a system than you put into it -- that is, the number of possible output states will always be less than or equal to the number of possible input states. There are only so many combinational logic circuits that give you an equal number of input and output states, and most circuits will have fewer output states. This means that combinational logic is, on average, not reversible.
Less abstractly, we use digital logic to process information. Processed information is usually simplified in some way -- we process it because we want to isolate one aspect of the information, or answer some specific question about it. Doing this implies throwing away some information, which means the processing is non-reversible.
In the context of quantum physics the classic gates are irreversible as information is destroyed.
For example if one of the inputs to a 2 input NAND gate is a low then the information available at the other does not affect the output. It's information is lost.
The only gates that do not lose information are elusive OR or NOR gates.
Example: Answer to the mathematical sum,
1 + 7 is
8. Meantime, answers to a question of "What makes the sum to produce
8" could be, for example,
4 + 4,
6 + 2,
3 + 5, and etc. Thus, there is no unique answer for the latter.
For a logic gates NAND, you can only reverse (engineer) the input when the output is
0 (input must have been
1 NAND 1). However, when the output was
1, the input can be any of
0 NAND 0,
1 NAND 0 or
0 NAND 1, because all these combinations lead to the output of logic