- Porte de Toffoli
-
En informatique, la porte de Toffoli (également CCNOT porte), inventée par Tommaso Toffoli, est une porte logique universelle réversible, ce qui signifie que n'importe quel circuit réversible peut être construite à partir de portes de Toffoli. Elle agit comme une porte NON à double contrôle d'où le nom de "controlled-controlled-not gate" (CCNOT).
Sommaire
Introduction
Une porte logique L est réversible si, pour une sortie y, il y a une entrée x unique tel que l'application de L(x) = y. Si une porte L est réversible, il y a une porte inverse L qui relie y à x pour laquelle L (x) = y. La porte logique NON est réversible, comme on peut le voir à l'aide de sa table de vérité représentée ci-dessous.
ENTRÉE SORTIE 0 1 1 0 La porte commune ET n'est pas réversible cependant, car toutes les entrées 00, 01 et 10 ont pour sortie 0.
Les portes logiques réversibles sont étudiées depuis les années 1960. La motivation initiale était que les portes réversibles dissipent moins de chaleur (en principe pas de chaleur). Dans une porte classique, les états d'entrées sont perdus, puisque nous obtenons moins d'information en sortie que ce qui était présent à l'entrée. Cette perte d'information entraîne une perte d'énergie sous forme de chaleur selon le principe de l'entropie en thermodynamique. En d'autres termes de l'énergie est nécessaire 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, le développement de ces portes a été motivé par l'informatique quantique[1]. 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 quantique. Ainsi, les portes réversibles forment un sous-ensemble de portes autorisé par la mécanique quantique, ce qui permet d'envisager la réalisation d'ordinateurs quantiques.
Universalité et porte de Toffoli
Toute porte réversible doit avoir le même nombre de bits en entrée et en sortie, selon le principe des tiroirs. Pour un 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 entraîne aucun changement. Pour deux bits d'entrée, il existe qu'une seul porte la contrôle NON (CNOT), qui consiste à effectuer une transformation XOR entre les deux bits et le résultat est codé sur le seconde bit et le premier bit reste inchangé.
Table de vérité Représentation matricielle INPUT OUTPUT 0 0 0 0 0 1 0 1 1 0 1 1 1 1 1 0 ![\left[
\begin{matrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \\
\end{matrix}
\right]](c/4bc1d703a5314401f4455b9139f09ba6.png)
Malheureusement, il existe des fonctions réversibles qui ne peuvent pas être réalisées en utilisant juste ces portes. En d'autres termes, le jeu de portes composé de NON et de XOR n'est pas universelle (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. L'utilisation de la porte de Toffoli, proposée en 1980 par Tommaso Toffoli, est une solution[2] [3]
Cette porte permet de computer 3-bit d'information. Si les deux premiers bits sont égales à 1, le troisième bit est inversé, comme le montre la table de vérité suivante :
Table de vérité Représentation matricielle 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 ![\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]](5/d65613a083c68fae4c948fd157f82ff0.png)
En d'autres termes, pour trois bits en entrée a, b, et c nous obtenons en sortie a, b, et c XOR (a et b).
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 existe un circuit composé de portes de Toffoli.
Référence
- Adriano Barenco, « Elementary gates for quantum computation », dans Phys. Rev. A, vol. 52, mars 1982, p. 3457–3467 [texte intégral, lien DOI]
- Toffoli, Tommaso (1980). "Reversible computing" in Automata, Languages and Programming, Seventh Colloquium. J. W. de Bakker and J. van Leeuwen : 632-644, Noordwijkerhout, Netherlands: Springer Verlag.
- Edward Fredkin, « Conservative logic », dans International Journal of Theoretical Physics, Springer Netherlands, vol. 21, no 3, avril 1982, p. 219–253 (ISSN 0020-7748) [texte intégral, lien DOI]
Liens externes
Voir aussi
Wikimedia Foundation. 2010.
