- Toffoli gate
In
computer science , the Toffoli gate, invented byTommaso Toffoli , is a universal reversiblelogic gate , which means that any reversible circuit can be constructed from Toffoli gates. It is also known as the "controlled-controlled-not" gate, which also describes its action.Background
A
logic gate "L" is reversible if, for any output "y", there is a unique input "x" such that applying "L"("x") = "y". If a gate "L" is reversible, there is an inverse gate "L"′ which maps "y" to "x" for which "L"("x") = "y". From common logic gates, NOT is reversible, as can be seen from its truthtable below. It can be also described as mapping bits a, b and c to a, b and c XOR (a AND b).The Toffoli gate is universal; this means that for any
boolean function "f"("x"1, "x"2, ..., "x""m"), there is a circuit consisting of Toffoli gates which takes "x"1, "x"2, ..., "x""m" and some extra bits set to 0 or 1 and outputs "x"1, "x"2, ..., "x""m", "f"("x"1, "x"2, ..., "x""m"), and some extra bits (called garbage). Essentially, this means that one can use Toffoli gates to build systems that will perform any desired boolean function computation in a reversible manner.Related logic gates
* The
Fredkin gate is a reversible 3-bit gate that swaps the last two bits if the first bit is 1; a controlled-swap operation.* The "n"-bit Toffoli gate is a generalization of Toffoli gate. It takes "n" bits "x"1, "x"2, ..., "x""n" as inputs and outputs "n" bits. The first "n"−1 output bits are just "x"1, ..., "x""n"−1. The last output bit is ("x"1 AND ... AND "x""n"−1) XOR "x""n".
* The Toffoli gate can be realized by five two-qubit quantum gates.* This gate is one of the reversible-gate cases that can be modeled with billiard balls, the billiard ball modeling was introduced by Fredkin and Toffoli in his paper [1] , an example of how the collisions are used to model an electronic gate is shown in the figure.
Relation to quantum computing
Any reversible gate can be implemented on a
quantum computer , and hence the Toffoli gate is also a quantum operator. However, the Toffoli gate can not be used for universalquantum computation , though it does mean that a quantum computer can implement all possible classical computations. Although it may never be implemented in an actual quantum computer, the Toffoli gate has already played an important role in theoretical research on quantum computing; for example inquantum error correction .See also
*
Fredkin gate
*Reversible computing
*Quantum computing
*Quantum programming References
# T. Toffoli, "Reversible Computing",
MIT Technical Report MIT/LCS/TM-151 (1980).
# E. Fredkin and T. Toffoli. [http://www.digitalphilosophy.org/download_documents/ConservativeLogic.pdf Conservative logic] . International Journal of Theoretical Physics, 21:219–253, 1982.
# Related Gates' figure public online [http://www.InterQuanta.biz/im www.InterQuanta.biz/im ]
Wikimedia Foundation. 2010.
