Modèles formels pour l'informatique quantique

2.2.5.2 Portes logiques à deux qubits)

Ces portes réalisent l'opération logique élémentaire « si A est vrai, alors faire B .... ».

15

chapitre2 : Information, donnée quantique

Porte générale «control-U» : U appliqué au qubit cible si le qubit source vaut 1 et cible non changée si la source vaut 0. Source toujours invariante. Cas particulier important : U = o_x Porte C-NOT (bascule conditionnelle)

On peut aussi conditionner l'évolution de la cible à la valeur 0 de la source:

La cible n'évolue que si la source vaut initialement 0 (effet de la première porte o_x). La source revient finalement dans l'état initial (deuxième porte o_x)

Remarque :

- La porte C-NOT peut être réalisée avec une porte de phase-ð et deux Hadamard: - Toute porte «control-U» peut se décomposer en portes C-NOT et portes à un qubit.

- La porte à deux qubits est nécessaire afin de créer de l'intrication.

2.2.5.3 Portes à plus de deux qubits)

Porte unitaire à n qubits peut être engendrée par le produit tensoriel et la composition de certains sous-ensembles de portes à 1 et à 2 qubits.

chapitre2 : Information, donnée quantique

16

FIGURE 2.4 - Decomposition de la porte quantique CNOT

- Porte de Toffoli

Tout d'abord, il serait satisfaisant qu'un ordinateur quantique ait une puissance de calcul au moins aussi importante qu'un ordinateur classique. Pour cela, une porte quantique particulière, appelée porte de Toffoli [Monerau, 2008], qui permet d'obtenir une version quantique du NAND et de la bifurcation dans un circuit. Ainsi, on aura récupéré au moins la puissance de calcul d'un ordinateur classique. La porte de Toffoli s'applique à 3 qubits en entrée (a, b, c) et produit 3 qubits en sortie (a', b', c'). Son action est simple :

Si les deux premiers qubits sont dans l'état 1), elle remplace la valeur du troisième qubit par son complémentaire. Pour fixer les idées, donnons sa table de vérité dans la base de calcul (les 0 et 1 représentent les états 0) et 1) pour plus de clarté) :

Entrées

Sorties

a	b	c	a'	b'		c'	0
0	0	0	0	0		0
0	1	0	0	1		0
1	1	0	1	1		0
1	0	0	1	0		1
0	0	1	0	0		1
0	1	1	0	1		1
1	1	1	1	0		1
1	0	1	1	1

TABLE 2.1 - Table de vérité de porte logique universelle réversible de Toffoli.

Cette table donne la valeur de la porte appliquée aux vecteurs de base de (C²)^®3, et elle caractérise donc bien l'opérateur unitaire sous-jacent. à partir de cette porte quantique, on voit qu'on obtient les opérations «génératrices» du calcul logique classique : NAND et la bifurcation. En effet, si on fixe c = 1), alors c' = NAND(a, b)). De même, si on fixe a = 1) et c = 0), alors b' = c' = b, et on a donc dupliqué b. Mais si un ordinateur quantique peut bien simuler

17

chapitre2 : Information, donnée quantique

un ordinateur classique, il présente bien sûr une puissance de calcul beaucoup plus importante. Tout est dans les états dits «d'intrication» des n-qubits. En effet, comme les n-qubits peuvent être des combinaisons linéaires d'éléments de la base, on peut y stocker plus d'information que si on pouvait simplement se placer sur des vecteurs de la base (comme on le ferait si l'ordinateur était classique).

Malheureusement, les mesures ne renvoient qu'un vecteur de la base, ce qui exclut de mesurer exactement un état intriqué et d'en obtenir les différentes composantes sur chaque vecteur de la base de calcul.

Cependant, comme on va le voir dans les algorithmes quantiques qui suivent, on peut tout de même utiliser cette latitude de calcul pour accélérer des algorithmes classiques.

- Porte CNOT

La porte de Toffoli nous a permis de simuler de manière quantique la logique de NAND. Maintenant, nous allons imiter son caractère «générateur». En effet, on dispose d'une porte de base qui a un rôle analogue à NAND, dans le cas classique dans le sens où elle est universelle parmi les opérateurs unitaires. Elle prend en entrée 2 qubits. Le premier est dit de contrôle, le second est la cible. Son action peut être décrite simplement : si le qubit de contrôle vaut 0), le qubit cible reste tel quel; mais si le qubit de contrôle vaut 1), alors le qubit cible est changé en son complémentaire. Sa table de vérité est donc :

Entrées

Sorties

a	b	a'		b'	0
0	0	0		0
1	0	1		1
0	1	1		1
1	1	0

TABLE 2.2 - Table de vérité de porte logique universelle réversible de CNOT.

Et on nomme cette porte CNOT (Controlled-NOT). CNOT [Monerau, 2008] présente une propriété algébrique intéressante :

Proposition (Universalité de CNOT et des portes sur 1-qubit)

à partir de CNOT et des portes quantiques agissant sur un 1-qubit, on peut créer par composition n'importe quelle porte quantique agissant sur un n-qubit (c'est-à-dire obtenir n'importe quel opérateur unitaire de (C²)^?n).

18

chapitre2 : Information, donnée quantique