Editing Reversible computing (section)

==Logical reversibility==
For a computational operation to be logically reversible means that the output (or final state) of the operation can be computed from the input (or initial state), and vice versa. Reversible functions are [[bijection|bijective]]. This means that reversible gates (and [[Circuit (computer science)|circuits]], i.e. compositions of multiple gates) generally have the same number of input bits as output bits (assuming that all input bits are consumed by the operation, and that all input/output states are possible).

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. Because AND and NOT together is a [[functional completeness|functionally complete]] set, the Toffoli gate is universal and can implement any [[Boolean function]] (if given enough initialized [[ancilla bit]]s).

Surveys of reversible circuits, their construction and optimization, as well as recent research challenges, are available.<ref>Rolf Drechsler, Robert Wille. From Truth Tables to Programming Languages: Progress in the Design of Reversible Circuits. International Symposium on Multiple-Valued Logic, 2011. http://www.informatik.uni-bremen.de/agra/doc/konf/11_ismvl_reversible_circuit_design_tutorial.pdf</ref><ref>{{cite journal |last1=Saeedi |first1=Mehdi |last2=Markov |first2=Igor L. |title=Synthesis and optimization of reversible circuits—a survey |journal=ACM Computing Surveys |date=1 February 2013 |volume=45 |issue=2 |pages=1–34 |doi=10.1145/2431211.2431220 |arxiv=1110.2574 |s2cid=6302811 }}</ref><ref>Rolf Drechsler and Robert Wille. Reversible Circuits: Recent Accomplishments and Future Challenges for an Emerging Technology. International Symposium on VLSI Design and Test, 2012. http://www.informatik.uni-bremen.de/agra/doc/konf/2012_vdat_reversible_circuits_accompl_chall.pdf</ref><ref>{{cite journal |last1=Cohen |first1=Eyal |last2=Dolev |first2=Shlomi |last3=Rosenblit |first3=Michael |title=All-optical design for inherently energy-conserving reversible gates and circuits |journal=Nature Communications |date=26 April 2016 |volume=7 |issue=1 |pages=11424 |doi=10.1038/ncomms11424 |pmid=27113510 |pmc=4853429 |bibcode=2016NatCo...711424C }}</ref><ref>{{Cite journal|last1 =Ang|first1 = Y. S.|last2 = Yang|first2 = S. A.|last3 = Zhang|first3 = C.|last4 = Ma|first4 = Z. S.|last5 = Ang|first5 = L. K.|date = 2017|title = Valleytronics in merging Dirac cones: All-electric-controlled valley filter, valve, and universal reversible logic gate|journal = Physical Review B|volume = 96|issue = 24|pages = 245410|doi = 10.1103/PhysRevB.96.245410|arxiv = 1711.05906|bibcode = 2017PhRvB..96x5410A| s2cid=51933139 }}</ref>