Editing Toffoli gate (section)

== Background ==

An input-consuming [[logic gate]] ''L'' is reversible if it meets the following conditions: (1) ''L''(''x'') = ''y'' is a gate where for any output ''y'', there is a unique input ''x''; (2) The gate ''L'' is reversible if there is a gate ''L''´(''y'') = ''x'' which maps ''y'' to ''x'', for all ''y''.

An example of a reversible logic gate is a [[NOT gate|NOT]], which can be described from its truth table below:

{| class="wikitable" style="text-align:center"
! Input !! Output
!Condition (1)
!Condition (2)
|-
| 0 || 1
|''x'' = 0 ''y'' = 1
|''y'' = 1 ''x'' = 0 
|-
| 1 || 0
|''x'' = 1 ''y'' = 0
|''y'' = 0 ''x'' = 1 
|}

The common [[AND gate|AND]] gate is not reversible, because the inputs 00, 01 and 10 are all mapped to the output 0.

{| class="wikitable" style="text-align:center"
! Input !! Output
!Condition (1)
|-
| 00 || 0
|''x'' not unique for ''y'' = 0
|-
| 01 || 0
|''x'' not unique for ''y'' = 0
|-
|10
|0
|''x'' not unique for ''y'' = 0
|-
|11
|1
|''x'' = 11 ''y'' = 1
|}

Reversible gates have been studied since the 1960s. The original motivation was that reversible gates dissipate less heat (or, in principle, no heat).<ref>{{cite journal|last=Landauer|first=R.|date=July 1961|title=Irreversibility and Heat Generation in the Computing Process|journal=IBM Journal of Research and Development|volume=5|issue=3|pages=183–191|doi=10.1147/rd.53.0183|issn=0018-8646}}</ref>

More recent motivation comes from [[quantum computing]]. In [[quantum mechanics]] the quantum state can evolve in two ways: by the [[Schrödinger equation]] ([[unitary transformation]]s), or by their [[Wave-function collapse|collapse]]. Logic operations for quantum computers, of which the Toffoli gate is an example, are unitary transformations and therefore evolve reversibly.<ref name="Williams">{{cite book|author=Colin P. Williams |year=2011 |title=Explorations in Quantum Computing |publisher=[[Springer Science+Business Media|Springer]]|isbn=978-1-84628-887-6|pages=25–29,61}}</ref>