Porte de Toffoli

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]

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]

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

  1. Adriano Barenco, « Elementary gates for quantum computation », dans Phys. Rev. A, vol. 52, mars 1982, p. 3457–3467 [texte intégral, lien DOI] 
  2. 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. 
  3. 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.

Contenu soumis à la licence CC-BY-SA. Source : Article Porte de Toffoli de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Tommaso Toffoli — Naissance 1943 Montereale Valcellina (  Italie) Domicile Cambridge Nationalité Italien Champs …   Wikipédia en Français

  • Calculateur quantique — La Sphère de Bloch est une représentation d’un qubit Un calculateur quantique ou ordinateur[1] quantique, repose sur des propriétés quantiques de la matière : superposition et intrication d éta …   Wikipédia en Français

  • Liberte (metro de Paris) — Liberté (métro de Paris) Pour les articles homonymes, voir Liberté (homonymie). Liberté …   Wikipédia en Français

  • Liberté (métro de Paris) — Pour les articles homonymes, voir Liberté (homonymie). Liberté …   Wikipédia en Français

  • Liberté (métro de paris) — Pour les articles homonymes, voir Liberté (homonymie). Liberté …   Wikipédia en Français

  • Liberté (métro parisien) — Liberté (métro de Paris) Pour les articles homonymes, voir Liberté (homonymie). Liberté …   Wikipédia en Français

  • Lignes de bus RATP de 100 à 199 — Réseau de bus RATP Lignes de 100 à 199 Un Agora S sur la ligne 190 …   Wikipédia en Français

  • Dei Greng — Déi Gréng Déi Gréng Données de base Date de fondation: 23. juin 1983 Porte paroles: Tilly Metz, Carlo de Toffoli Secrétaire général: Tom Graas …   Wikipédia en Français

  • Déi Gréng — Données de base Date de fondation: 23. juin 1983 Porte paroles: Tilly Metz, Carlo de Toffoli Secrétaire général: Tom Graas …   Wikipédia en Français

  • Rideau Hall — Infobox Historic building name = Rideau Hall caption = Main façade of Government House map type = latitude = 45.443753 longitude = 75.685641 location town = 1 Sussex Dr. Ottawa, Ontario location country = Canada architect = Various client =… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”