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 :

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é :

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 , qui, étant donné deux bits d'entrée, restitue le premier et donne comme second le OU exclusif des deux entrées :

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, x, ..., xm), il y a un circuit composé de portes de Toffoli qui
 prend en entrée x, x, ..., xm — plus quelques bits supplémentaires à 0 ou à 1 ;
 a comme sortie x, x, ..., xm, f(x, x, ..., xm) — 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  à l'université d'Innsbruck en Autriche.

Portes semblables 

 La  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, x, ..., xn) et n bits en sortie. Les n−1 premiers bits sortent inchangés ; le dernier est (x ET ... ET xn−1) XOR xn.
 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.

Références

Bibliographie

Voir aussi 
 Calculateur quantique
 Informatique quantique
 Calcul réversible

Fonction logique
Informatique quantique