7
\$\begingroup\$

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?

\$\endgroup\$
10
  • 1
    \$\begingroup\$ Do you know how a NAND gate is built on semiconductor level? \$\endgroup\$
    – winny
    Aug 19 '21 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\$ Aug 19 '21 at 18:53
  • 1
    \$\begingroup\$ Cheryl, see this. It should help a great deal. \$\endgroup\$
    – jonk
    Aug 19 '21 at 19:20
  • 6
    \$\begingroup\$ @Justme, I'm reading it as electrically reversible. The question is unclear. \$\endgroup\$
    – Transistor
    Aug 19 '21 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 Yates
    Aug 20 '21 at 15:27
29
\$\begingroup\$

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.

\$\endgroup\$
1
  • 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\$ Aug 19 '21 at 19:06
11
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ *Wikipedia \$\endgroup\$ Aug 22 '21 at 8:54
  • \$\begingroup\$ Thanks @PeterMortensen . I will correct that. \$\endgroup\$
    – jay
    Aug 22 '21 at 12:16
8
\$\begingroup\$

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

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ Does NOT gate also lead to information loss? If so, why? \$\endgroup\$
    – Alexia.
    Aug 20 '21 at 2:07
  • \$\begingroup\$ If A XOR B is 1, can you tell me whether A = 1 or B = 1? \$\endgroup\$ Aug 20 '21 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 a and b when all you know is a OR b = 1, and the same applies to a NOR b = 0 \$\endgroup\$
    – Flater
    Aug 20 '21 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\$ Aug 20 '21 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\$
    – abligh
    Aug 21 '21 at 8:04
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.