Porte XOR

En cherchant des portes XOR à 3 entrées (pour simuler un additionneur 2x1 bits) l'algorithme génétique ne trouve rien. Mauvais algorithme ou réel problème ?

Le problème

Soit des objets de la forme M = (x, y, z, Ex, Ey, Ez) où x, y, z sont des vecteurs qui correspondent à des coordonnées dans l'espace et Ex, Ey, Ez sont les résultats d'une fonction f pour toutes ces coordonnées : $f(x, y, z) = (Ex, Ey, Ez)$.

La fonction f représente la simulation (discrète) d'un laser à une position donnée avec une longueur d'onde, une phase, une polarisation fixée.

Pour représenter une porte logique à 3 entrées, on a besoin de 6 fonctions f : 3 entrées à 2 positions (0 ou 1) qui nous donnerons 8 états possibles ($2^8$).

Par linéarité, la fonction finale d'une telle porte correspondant au mot binaire abc, avec $a, b, c \in \{0, 1\}$ vaut : $F_{abc} = f_{(0, a)} + f_{(1, b)} + f_{(2, c)}$

Cette fonction $f_{abc}$ a des valeurs dans $\mathbb{C}^3$, le seuil que l'on cherche se fait sur la somme de ses modules:

$F_{abc} = (g_{(x, abc)}, g_{(y, abc)}, g_{(z, abc)})$, où $g_{(\_, abc)} = g_{(\_, abc)}^r + i*g_{(\_, abc)}^i$, et $g_{(\_, abc)} = f_{\_, (0, a)} + f_{\_, (1, b)} + f_{\_, (2, c)}$

$v = \lvert g_{x,abc} \rvert ^2 + \lvert g_{y,abc} \rvert ^2 + \lvert g_{z,abc} \rvert ^2$

Au final, on va calculer :

$v = \left( f_{x(0, a)}^r+f_{x(1, b)}^r+f_{x(2, c)}^r \right)^2+\left( f_{x(0, a)}^i+f_{x(1, b)}^i+f_{x(2, c)}^i \right)^2 + \left( f_{y(0, a)}^r+f_{y(1, b)}^r+f_{y(2, c)}^r \right)^2+\left( f_{y(0, a)}^i+f_{y(1, b)}^i+f_{y(2, c)}^i \right)^2 + \left( f_{z(0, a)}^r+f_{z(1, b)}^r+f_{z(2, c)}^r \right)^2 + \left( f_{z(0, a)}^i+f_{z(1, b)}^i+f_{z(2, c)}^i \right)^2$

Bien sûr, v est une fonction, mais on va se donner un point $(x, y, z)$ quelconque et le but du jeu sera de voir si on peut trouver un seuil plus grand que 0 à cette position (i.e. à n'importe quelle position).

On peut réécrire notre fonction : $v = \sum_{d \in {x, y, z}} \sum_{p \in {i, r}} (f_{d, (0, a)}^p + f_{d, (1, b)}^p + f_{d, (2, c)}^p)^2$

Par la suite, pour simplifier les calculs, on se fixera une dimension $d$ et une partie $p$ (imaginaire ou réelle):

• $\alpha_0 = f_{d(0, 0)}^p(x, y, z) \implies$ le premier laser en mode 0 logique
• $\alpha_1 = f_{d(0, 1)}^p(x, y, z) \implies$ le premier laser en mode 1 logique
• $\beta_0 = f_{d(1, 0)}^p(x, y, z) \implies$ le deuxième laser en mode 0 logique
• $\beta_1 = f_{d(1, 1)}^p(x, y, z) \implies$ le deuxième laser en mode 1 logique
• $\gamma_0 = f_{d(2, 0)}^p(x, y, z) \implies$ le troisième laser en mode 0 logique
• $\gamma_1 = f_{d(2, 1)}^p(x, y, z) \implies$ le troisième laser en mode 1 logique

Ainsi la valeur de la configuration (0, 1, 0) est $v_{(0, 1, 0)} = (\alpha_0 + \beta_1 + \gamma_0)^2$.

On se fixera un seuil $\varepsilon > 0$, et il faudra que :

• Si la sortie de la porte vaut 1, la valeur de la configuration soit plus grande que $v > \varepsilon$
• Si la sortie de la porte vaut 0, la valeur de la configuration soit plus petite que $v < \varepsilon$

Ce qui nous donnera une liste d'inéquation à vérifier.

Avec 2 entrées

Dans cette version du problème, on n'a pas besoin des $\gamma$.

On se fixe $\varepsilon > 0$

Trouver une porte XOR revient à satisfaire la liste d'inégalités suivantes :

• $E_{00} := \left( \alpha_0 + \beta_0 \right)^2 < \varepsilon \Longleftrightarrow E_{00} := -\alpha_0^2 -2\alpha_0\beta_0 - \beta_0^2 > -\varepsilon$
• $E_{01} := \left( \alpha_0 + \beta_1 \right)^2 > \varepsilon \Longleftrightarrow E_{01} := \alpha_0^2 +2\alpha_0\beta_1 + \beta_1^2 > \varepsilon$
• $E_{10} := \left( \alpha_1 + \beta_0 \right)^2 > \varepsilon \Longleftrightarrow E_{10} := \alpha_1^2 +2\alpha_1\beta_0 + \beta_0^2 > \varepsilon$
• $E_{11} := \left( \alpha_1 + \beta_1 \right)^2 < \varepsilon \Longleftrightarrow E_{11} := -\alpha_1^2 -2\alpha_1\beta_1 - \beta_1^2 > -\varepsilon$

En posant, et en développant $(E_{01}+E_{00})$ et $(E_{10}+E_{11})$, on obtient :

• $E_{01}+E_{00} := \beta_1^2 - \beta_0^2 + 2\alpha_0\left( \beta_1 - \beta_0 \right) > 0$
• $E_{10}+E_{11} := \beta_0^2 - \beta_1^2 + 2\alpha_1\left( \beta_0 - \beta_1 \right) > 0$

Comme $\left( \beta_1 - \beta_0 \right) = - \left( \beta_0 - \beta_1 \right)$, on peut finalement écrire:

$E=(E_{01}+E_{00})+(E_{10}+E_{11}) := 2\left( \alpha_0 - \alpha_1 \right)\left( \beta_1 - \beta_0 \right) > 0$

Ce qui ne pose pas de soucis, donc on peut trouver une porte XOR à 2 entrées.

Avec 3 entrées

Pour trouver une porte XOR à 3 entrées, il faut satisfaire la liste d'inégalités suivantes :

• $E_{000} := \left( \alpha_0+\beta_0+\gamma_0 \right)^2 < \varepsilon \Longleftrightarrow E_{000} := -\alpha_0^2 - 2\alpha_0\beta_0 - \beta_0^2 - 2\alpha_0\gamma_0 - \gamma_0^2 - 2\gamma_0\beta_0 > -\varepsilon$
• $E_{001} := \left( \alpha_0+\beta_0+\gamma_1 \right)^2 > \varepsilon \Longleftrightarrow E_{001} := \alpha_0^2 + 2\alpha_0\beta_0 + \beta_0^2 + 2\alpha_0\gamma_1 + \gamma_1^2 + 2\gamma_1\beta_0 > \varepsilon$
• $E_{010} := \left( \alpha_0+\beta_1+\gamma_0 \right)^2 > \varepsilon \Longleftrightarrow E_{010} := \alpha_0^2 + 2\alpha_0\beta_1 + \beta_1^2 + 2\alpha_0\gamma_0 + \gamma_0^2 + 2\gamma_0\beta_1 > \varepsilon$
• $E_{011} := \left( \alpha_0+\beta_1+\gamma_1 \right)^2 < \varepsilon \Longleftrightarrow E_{011} := -\alpha_0^2 - 2\alpha_0\beta_1 - \beta_1^2 - 2\alpha_0\gamma_1 - \gamma_1^2 - 2\gamma_1\beta_1 > -\varepsilon$
• $E_{100} := \left( \alpha_1+\beta_0+\gamma_0 \right)^2 > \varepsilon \Longleftrightarrow E_{100} := \alpha_1^2 + 2\alpha_1\beta_0 + \beta_0^2 + 2\alpha_1\gamma_0 + \gamma_0^2 + 2\gamma_0\beta_0 > \varepsilon$
• $E_{101} := \left( \alpha_1+\beta_0+\gamma_1 \right)^2 < \varepsilon \Longleftrightarrow E_{101} := -\alpha_1^2 - 2\alpha_1\beta_0 - \beta_0^2 - 2\alpha_1\gamma_1 - \gamma_1^2 - 2\gamma_1\beta_0 > -\varepsilon$
• $E_{110} := \left( \alpha_1+\beta_1+\gamma_0 \right)^2 < \varepsilon \Longleftrightarrow E_{110} := -\alpha_1^2 - 2\alpha_1\beta_1 - \beta_1^2 - 2\alpha_1\gamma_0 - \gamma_0^2 - 2\gamma_0\beta_1 > -\varepsilon$
• $E_{111} := \left( \alpha_1+\beta_1+\gamma_1 \right)^2 > \varepsilon \Longleftrightarrow E_{111} := \alpha_1^2 + 2\alpha_1\beta_1 + \beta_1^2 + 2\alpha_1\gamma_1 + \gamma_1^2 + 2\gamma_1\beta_1 > \varepsilon$

En posant, et en développant $(E_{001}+E_{000})$, $(E_{010}+E_{011})$, $(E_{100}+E_{101})$ et $(E_{111}+E_{110})$, on obtient :

• $E_{001}+E_{000} := \gamma_1^2 - \gamma_0^2 + 2\left(\alpha_0 + \beta_0 \right)\left( \gamma_1 - \gamma_0\right) > 0$
• $E_{010}+E_{011} := \gamma_0^2 - \gamma_1^2 + 2\left(\alpha_0 + \beta_1 \right)\left( \gamma_0 - \gamma_1\right) > 0$
• $E_{100}+E_{101} := \gamma_0^2 - \gamma_1^2 + 2\left(\alpha_1 + \beta_0 \right)\left( \gamma_0 - \gamma_1\right) > 0$
• $E_{111}+E_{110} := \gamma_1^2 - \gamma_0^2 + 2\left(\alpha_1 + \beta_1 \right)\left( \gamma_1 - \gamma_0\right) > 0$

On peut recommencer une nouvelle fois, avec : $E_0=(E_{001}+E_{000})+(E_{010}+E_{011})$ et $E_1=(E_{100}+E_{101})+(E_{111}+E_{110})$, on a :

• $E_0 := 2\left(\beta_0 - \beta_1 \right)\left(\gamma_1 - \gamma_0 \right) > 0$
• $E_1 := 2\left(\beta_0 - \beta_1 \right)\left(\gamma_0 - \gamma_1 \right) > 0$

On obtient une contradiction car $\gamma_1 - \gamma_0 = -\left( \gamma_0 - \gamma_1 \right)$.

En posant $a = \left(\beta_0 - \beta_1 \right)\left(\gamma_0 - \gamma_1 \right)$, on aurait $a > 0$ et $-a > 0$.

Impossible. Donc, on ne peut pas trouver de porte XOR à 3 entrées (et plus).