Wikipédia

Porte de Toffoli

fonction logique

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 modifier

 
Représentation d'une porte de Toffoli

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 
0 0 1 0 0 1
0 1 0 0 1 0
0 1 1 0 1 1
1 0 0 1 0 0
1 0 1 1 0 1
1 1 0 1 1 1
1 1 1 1 1 0

 

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

Définition modifier

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 modifier

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[1].

Plus récemment, l'intérêt est venu de l'informatique quantique[2]. 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 modifier

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 
0 1 0 1
1 0 1 1
1 1 1 0

 

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[3],[4].

La porte de Toffoli est universelle, ce qui signifie que, quelle que soit la fonction booléenne f(x1, x2, ..., xm), il y a un circuit composé de portes de Toffoli qui

  • prend en entrée x1, x2, ..., xm — plus quelques bits supplémentaires à 0 ou à 1 ;
  • a comme sortie x1, x2, ..., xm, f(x1, x2, ..., 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 modifier

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[5].

Portes semblables modifier

 
Représentation Fredkin–Toffoli des portes sous forme de boules de billard
  • 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)[6].
  • La porte de Toffoli à n bits est une généralisation de la porte de Toffoli. Elle a n bits en entrée (x1, x2, ..., xn) et n bits en sortie. Les n−1 premiers bits sortent inchangés ; le dernier est (x1 ET ... ET xn−1) XOR xn.
  • On peut construire une porte de Toffoli avec cinq portes quantiques à 2 qubits[7].
  • Cette porte est l'une des portes réversibles modélisables par boules de billard[8]. Cette modélisation est due à Fredkin et Toffoli[4].

Références modifier

  1. ↑ Voir le principe auquel Rolf Landauer a donné son nom.
  2. ↑ (Barenco et al. 1982)
  3. ↑ (Toffoli 1980)
  4. ↑ a et b (Fredkin et Toffoli 1982)
  5. ↑ (Monz et al.)
  6. ↑ Porte de Fredkin quantique
  7. ↑ (Barenco et al. 1995)
  8. ↑ Voir en:Billiard-ball computer dans la Wikipédia en anglais.

Bibliographie modifier

Voir aussi modifier

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Porte_de_Toffoli&oldid=206945704 ».