# Porte de Toffoli

En informatique, la porte de Toffoli, est une porte logique. Elle est réversible et universelle, ce qui signifie que n'importe quel circuit réversible peut être construit à partir de portes de Toffoli. Elle agit comme une porte NON à double contrôle, d'où le nom qu'on lui donne également de « controlled-controlled-not gate » (CCNOT).
Elle est due à Tommaso Toffoli.

## Définition

La porte de Toffoli est une porte logique à 3 bits en entrée et 3 bits en sortie. Si les deux premiers bits sont égaux à 1, le troisième bit est inversé, comme le montrent les représentations suivantes :
| Table de vérité | Matrice de permutation |
| ENTRÉE SORTIE  0 0 0 0 0 0  001001 010010 011011 100100 101101 110111 111110 | $\left[\ {\begin{matrix}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{matrix}}\ \right]$ |
Autrement dit, pour trois bits en entrée a, b, et c nous obtenons en sortie a, b, et (c XOR (a ET b)).

## Réversibilité
### Définition

Une porte logique L est réversible si, pour toute sortie y, il existe une entrée x unique telle que L(x) = y. Si une porte L est réversible, il existe une porte inverse L’ pour laquelle L’(y) = x. Par exemple, la porte NON est réversible, comme le montre sa table de vérité :
| ENTRÉE | SORTIE |
| 0 | 1 |
| 1 | 0 |
Par contre, la porte ET n'est pas réversible, les entrées 00, 01 et 10 ayant toutes trois pour sortie 0.

### Importance

On s'est intéressé aux portes logiques réversibles dans les années 1960, parce que les portes réversibles dissipent moins de chaleur que les autres (en principe elles pourraient même à la limite n'en dissiper aucune). Dans une porte classique, les états d'entrée ne sont pas systématiquement conservés et nous obtenons généralement moins d'information en sortie qu'en entrée. Cette perte entraîne aussi une perte d'énergie, sous forme de chaleur, selon le principe de l'entropie en thermodynamique. Autrement dit, il faut de l'énergie pour permettre la transformation des bits d'information. Une porte réversible ne fait que modifier l'état des bits sans perte d'information, l'énergie est donc conservée.
Plus récemment, l'intérêt est venu de l'informatique quantique. La physique quantique impose l'utilisation de transformations réversibles, mais permet en contrepartie de travailler avec des états plus larges pour réaliser des calculs à l'aide du principe de superposition. Les portes réversibles forment un sous-ensemble des portes autorisées par l'informatique quantique.

### Universalité et porte de Toffoli

Selon le principe des tiroirs, toute porte réversible doit avoir le même nombre de bits en entrée et en sortie.
* Pour un seul bit d'entrée, il existe deux portes réversibles. La première est la porte NON qui inverse 0 et 1, et la seconde la porte d'identité qui n'entraîne aucun changement.
* Pour deux bits d'entrée, il n'existe qu'une seule porte non triviale la porte CNOT (en), qui, étant donné deux bits d'entrée, restitue le premier et donne comme second le OU exclusif des deux entrées :
| Table de vérité | Matrice de permutation |
| INPUT OUTPUT  0 0 0 0  0101 1011 1110 | $\left[\ {\begin{matrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\\\end{matrix}}\ \right]$ |
Malheureusement, il existe des fonctions réversibles qui ne peuvent pas être réalisées en utilisant seulement ces portes. Autrement dit, le jeu de portes composé de NON et de XOR n'est pas universel (voir l'intégralité fonctionnelle). Si nous tenons à réaliser une fonction quelconque à l'aide de portes réversibles, nous avons besoin d'une autre porte. La porte de Toffoli, proposée en 1980 par Tommaso Toffoli, est une solution$^,$.
La porte de Toffoli est universelle, ce qui signifie que, quelle que soit la fonction booléenne f(x$_1$, x$_2$, ..., x$_m$), il y a un circuit composé de portes de Toffoli qui
* prend en entrée x$_1$, x$_2$, ..., x$_m$ — plus quelques bits supplémentaires à 0 ou à 1 ;
* a comme sortie x$_1$, x$_2$, ..., x$_m$, f(x$_1$, x$_2$, ..., x$_m$) — plus quelques autres bits, inutilisés.
On peut donc construire avec des portes de Toffoli des systèmes qui réaliseront de façon réversible une fonction booléenne quelconque.

## Liens avec l'informatique quantique

Toute porte réversible peut être implantée sur un ordinateur quantique. La porte de Toffoli est donc aussi un opérateur quantique. Mais elle n'est pas un opérateur quantique universel, même s'il est vrai que l'ordinateur quantique peut réaliser tous les calculs classiques.
Une porte de Toffoli a été réalisée en janvier 2009 à l'université d'Innsbruck en Autriche.

## Portes semblables

* La porte de Fredkin (en) est une porte réversible à trois bits qui permute les deux derniers bits si le premier est à 1 (permutation contrôlée).
* La porte de Toffoli à n bits est une généralisation de la porte de Toffoli. Elle a n bits en entrée (x$_1$, x$_2$, ..., x$_n$) et n bits en sortie. Les n−1 premiers bits sortent inchangés ; le dernier est (x$_1$ ET ... ET x$_{n−1}$) XOR x$_n$.
* On peut construire une porte de Toffoli avec cinq portes quantiques à 2 qubits.
* Cette porte est l'une des portes réversibles modélisables par boules de billard. Cette modélisation est due à Fredkin et Toffoli.