Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Toffoli gate
Summary
In logic circuits, the Toffoli gate (also CCNOT gate), invented by Tommaso Toffoli, is a universal reversible logic gate, which means that any classical reversible circuit can be constructed from Toffoli gates. It is also known as the "controlled-controlled-not" gate, which describes its action. It has 3-bit inputs and outputs; if the first two bits are both set to 1, it inverts the third bit, otherwise all bits stay the same.
An input-consuming logic gate L is reversible if it meets the following conditions:
L(x) = y is a gate where for any output y, there is a unique input x.
The gate L is reversible if there is a gate L′(y) = x which maps y to x.
From common logic gates, NOT is reversible, as can be seen from its truth table below.
The common AND gate is not reversible, because the inputs 00, 01 and 10 are all mapped to the output 0.
Reversible gates have been studied since the 1960s. The original motivation was that reversible gates dissipate less heat (or, in principle, no heat).
More recent motivation comes from quantum computing. In quantum mechanics the quantum state can evolve in two ways, by Schrödinger's equation (unitary transformations), or by their collapse. Logic operations for quantum computers, of which the Toffoli gate is an example, are unitary transformations and therefore evolve reversibly.
Any reversible gate that consumes its inputs and allows all input computations must have no more input bits than output bits, by the pigeonhole principle. For one input bit, there are two possible reversible gates. One of them is NOT. The other is the identity gate, which maps its input to the output unchanged. For two input bits, the only non-trivial gate is the controlled NOT gate, which XORs the first bit to the second bit and leaves the first bit unchanged.
Unfortunately, there are reversible functions that cannot be computed using just those gates. In other words, the set consisting of NOT and XOR gates is not universal. To compute an arbitrary function using reversible gates, another gate is needed.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.