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?
\$\begingroup\$
\$\endgroup\$
10
-
1\$\begingroup\$ Do you know how a NAND gate is built on semiconductor level? \$\endgroup\$– winnyCommented Aug 19, 2021 at 18:52
-
9\$\begingroup\$ Reversible 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. \$\endgroup\$– Scott SeidmanCommented Aug 19, 2021 at 18:53
-
1\$\begingroup\$ Cheryl, see this. It should help a great deal. \$\endgroup\$– jonkCommented Aug 19, 2021 at 19:20
-
6\$\begingroup\$ @Justme, I'm reading it as electrically reversible. The question is unclear. \$\endgroup\$– TransistorCommented Aug 19, 2021 at 21:04
-
3\$\begingroup\$ @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. \$\endgroup\$– Glen YatesCommented Aug 20, 2021 at 15:27
|
Show 5 more comments
6 Answers
\$\begingroup\$
\$\endgroup\$
1
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.
-
2\$\begingroup\$ Of 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! \$\endgroup\$ Commented Aug 19, 2021 at 19:06
\$\begingroup\$
\$\endgroup\$
2
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.
-
-
\$\begingroup\$ Thanks @PeterMortensen . I will correct that. \$\endgroup\$– jayCommented Aug 22, 2021 at 12:16
\$\begingroup\$
\$\endgroup\$
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
answered Aug 19, 2021 at 19:22
\$\begingroup\$
\$\endgroup\$
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.
answered Aug 19, 2021 at 20:49
\$\begingroup\$
\$\endgroup\$
5
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.
answered Aug 20, 2021 at 0:17
-
\$\begingroup\$ Does NOT gate also lead to information loss? If so, why? \$\endgroup\$– ClaireCommented Aug 20, 2021 at 2:07
-
\$\begingroup\$ If A XOR B is 1, can you tell me whether A = 1 or B = 1? \$\endgroup\$ Commented Aug 20, 2021 at 4:09
-
1\$\begingroup\$ "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\$\endgroup\$– FlaterCommented Aug 20, 2021 at 12:57 -
\$\begingroup\$ @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. \$\endgroup\$ Commented Aug 20, 2021 at 23:42
-
3\$\begingroup\$ @Flater possibly an elusive OR gate is something we have not yet discovered (as opposed to an exclusive OR gate) :-) \$\endgroup\$– ablighCommented Aug 21, 2021 at 8:04
\$\begingroup\$
\$\endgroup\$
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.
