Content deleted Content added
→Logical reversibility: toffoli can implement any reversible boolean function given enough ancillas → toffoli can implement any boolean function given enough ancillas (if ancillas are allowed then also non-reversible functions). maybe one could say something about being allowed to output junk values on some outputs as well, but does that have a proper name :|? |
m →Logical reversibility: + link |
||
Line 33:
An [[inverter (logic gate)|inverter]] (NOT) gate is logically reversible because it can be ''undone''. The NOT gate may however not be physically reversible, depending on its implementation.
The [[exclusive or]] (XOR) gate is irreversible because its two inputs cannot be unambiguously reconstructed from its single output, or alternatively, because information erasure is not reversible. However, a reversible version of the XOR gate—the [[controlled NOT gate]] (CNOT)—can be defined by preserving one of the inputs as a 2nd output. The three-input variant of the CNOT gate is called the [[Toffoli gate]]. It preserves two of its inputs ''a,b'' and replaces the third ''c'' by <math>c\oplus (a\cdot b)</math>. With <math>c=0</math>, this gives the AND function, and with <math>a\cdot b=1</math> this gives the NOT function. Thus, the Toffoli gate is [[functional completeness|universal]] and can implement any [[Boolean function]] (if given enough initialized [[ancilla bit]]s).
Similarly, in the [[Turing machine]] model of computation, a reversible Turing machine is one whose transition function is invertible, so that each machine state has at most one predecessor.
|