Toffoli gate

In logic circuits, the Toffoli gate (also CCNOT 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 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. [ 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 ] {displaystyle {egin{bmatrix}1&0&0&0\0&1&0&0\0&0&0&1\0&0&1&0\end{bmatrix}}} [ 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 ] {displaystyle {egin{bmatrix}1&0&0&0&0&0&0&0\0&1&0&0&0&0&0&0\0&0&1&0&0&0&0&0\0&0&0&1&0&0&0&0\0&0&0&0&1&0&0&0\0&0&0&0&0&1&0&0\0&0&0&0&0&0&0&1\0&0&0&0&0&0&1&0\end{bmatrix}}} In logic circuits, the Toffoli gate (also CCNOT 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 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, 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′(y) = x. From common logic gates, NOT is reversible, as can be seen from its truth table below.