Toffoli gate

Toffoli gate

In computer science, the Toffoli gate, invented by Tommaso Toffoli, is a universal reversible logic 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 universal quantum 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 in quantum 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.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Quantum gate — A quantum gate or quantum logic gate is a basic quantum circuit operating on a small number of qubits. They are the analogues for quantum computers to classical logic gates for conventional digital computers. Quantum logic gates are reversible,… …   Wikipedia

  • Tommaso Toffoli — (1943 )is a professor of electrical and computer engineering at Boston University. He joined the faculty in 1995. He was born in Montereale Cellina, in north eastern Italy, and raised in Rome. He received his doctorate in physics from the… …   Wikipedia

  • Fredkin gate — The Fredkin gate is computational circuit suitable for reversible computing, invented by Ed Fredkin. It is universal , which means that any logical or arithmetic operation can be constructed entirely of Fredkin gates.The basic Fredkin gate is a… …   Wikipedia

  • Porte de Toffoli — En informatique, la porte de Toffoli (également CCNOT porte), inventée par Tommaso Toffoli, est une porte logique universelle réversible, ce qui signifie que n importe quel circuit réversible peut être construite à partir de portes de Toffoli.… …   Wikipédia en Français

  • Logic gate — A logic gate is an idealized or physical device implementing a Boolean function, that is, it performs a logical operation on one or more logic inputs and produces a single logic output. Depending on the context, the term may refer to an ideal… …   Wikipedia

  • Quantum circuit — In quantum information theory, a quantum circuit is a model for quantum computation in which a computation is a sequence of reversible transformations on a quantum mechanical analog of an n bit register. This analogous structure is referred to as …   Wikipedia

  • Reversible Computing/3 input universal logic gates — Logic gates are used to build computer chips. Reversible logic gates are of interest because they could in principle generate useful results for less heat generated (Landauer 1961). The nand gate is universal among irreversible logic gates, in… …   Wikipedia

  • Billiard ball computer — Fredkin and Toffoli Gate billiard ball model A billiard ball computer, also known as a conservative logic circuit, is an idealized model of a reversible mechanical computer based on newtonian dynamics, proposed in 1982 by Edward Fredkin and… …   Wikipedia

  • Timeline of quantum computing — Timeline of quantum computers1970s* 1970 Stephen Wiesner invents conjugate coding.* 1973 Alexander Holevo publishes a paper showing that n qubits cannot carry more than n classical bits of information (a result known as Holevo s theorem or Holevo …   Wikipedia

  • Liste der Quantengatter — Dies ist eine Auflistung verschiedener Quantengatter und deren Funktion. Inhaltsverzeichnis 1 Quantengatter mit einem Eingang 2 Quantengatter mit zwei Eingängen 3 Quantengatter mit drei Eingängen …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”