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?
Asked
Active
Viewed 3,797 times
8
-
1Do you know how a NAND gate is built on semiconductor level? – winny Aug 19 '21 at 18:52
-
9Reversible in the sense of putting a signal on the output and seeing a meaningful signal on the input, or reversible in the sense of knowing the inputs for any given output? If the latter, this is ill posed for all but a simple NOT gate, Any gate with more than one input is ill posed, with multiple input combos causing the same output. – Scott Seidman Aug 19 '21 at 18:53
-
1Cheryl, see this. It should help a great deal. – jonk Aug 19 '21 at 19:20
-
Cheryl, do you know of any logic gate that is reversible? (I don't.) – Transistor Aug 19 '21 at 19:55
-
1@Transistor What about the NOT gate? If you know the output, you can guess the input quite easily? – Justme Aug 19 '21 at 20:48
-
6@Justme, I'm reading it as electrically reversible. The question is unclear. – Transistor Aug 19 '21 at 21:04
-
1@Transistor: There is the "identity" gate, which given (x) returns (x); there's the "swap" gate, which given (x,y) returns (y,x). These are both reversible, in both senses - but we don't normally consider them in the context of "gates" because you can achieve their functions with just wiring... – psmears Aug 20 '21 at 09:37
-
3@Transistor Seeing as how the OP mentions "textbook for quantum information" and "classical logic gates", I would assume the question is about Boolean logic gate theory - not any specific actual implementation. – Glen Yates Aug 20 '21 at 15:27
-
1Some context (that ought to be in the question): Logical reversibility – Peter Mortensen Aug 22 '21 at 08:53
-
I vote against closure of this question, because it's about an unclear terminus. However, it would be nice if OP could share a snippet from the textbook to show the context. – Ariser Aug 24 '21 at 08:53
6 Answers
30
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.
Justme
- 147,557
- 4
- 113
- 291
-
2Of course, in the quantum world, we'd say that the inputs would then be existing in all the states, with appropriate probabilities and manifest in a certain way in a certain dimension and time! – kalyanswaroop Aug 19 '21 at 19:06
11
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.
jay
- 3,841
- 9
- 24
8
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
Elliot Alderson
- 31,521
- 5
- 30
- 67
6
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.
Adam Haun
- 21,959
- 4
- 51
- 91
4
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.
Kevin White
- 33,153
- 1
- 48
- 78
-
-
-
1"The only gates that do not lose information are elusive OR or NOR gates." This is incorrect. There is no way to tell me the precise values of
aandbwhen all you know isa OR b = 1, and the same applies toa NOR b = 0– Flater Aug 20 '21 at 12:57 -
@Cheryl The "NOT" gate (inverter) does not lead to information loss, because you can always determine which input state was the cause of the current output. Namely, if the output is 1, then you know that the input must be 0, and vice versa. – Simon Fitch Aug 20 '21 at 23:42
-
3@Flater possibly an elusive OR gate is something we have not yet discovered (as opposed to an exclusive OR gate) :-) – abligh Aug 21 '21 at 08:04
3
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 1.
