Automate quantique

Soit ${\displaystyle n}$ un entier positif. Un automate quantique au sens de Moore et Crutchfield, appelé automate « measure once » ou « MO », sur un alphabet ${\displaystyle \Sigma }$ est définie par les quatre données suivantes :

• un ensemble ${\displaystyle Q=\{q_{1},\ldots ,q_{n}\}}$ d'états. À chaque état ${\displaystyle q_{i}}$ est associé un élément noté ${\displaystyle |q_{i}\rangle }$ d'un espace de Hilbert ${\displaystyle H_{n}}$ de dimension ${\displaystyle n}$, en général ${\displaystyle \mathbb {C} ^{n}}$, de sorte que ${\displaystyle \{|q_{1}\rangle ,\ldots ,|q_{n}\rangle \}}$ forme une base orthonormée de ${\displaystyle H_{n}}$. On suppose en général que ${\displaystyle q_{i}}$ est le ${\displaystyle i}$-ème vecteur unité,
• un matrice unitaire ${\displaystyle U_{a}}$ d'ordre ${\displaystyle n}$ pour chaque lettre ${\displaystyle a}$ de ${\displaystyle \Sigma }$. Cette matrice est la représentation d'un opérateur unitaire dans la base choisie.
• un vecteur ${\displaystyle s}$ d'ordre ${\displaystyle n}$ de norme ${\displaystyle \Vert s\Vert =1}$, état quantique initial.
• une matrice de projection orthogonale ${\displaystyle P}$ d'ordre ${\displaystyle n}$, correspondant à un projecteur orthogonal. Ce projecteur peut être remplacé parfois par un ensemble fini d'états terminaux, et la projection opère par projection sur ces états.

Les matrices et vecteurs sont à coefficients complexes.

Un état (quantique) est un vecteur ${\displaystyle |q\rangle }$ qui se décompose sur la base ${\displaystyle Q}$ et s'écrit, dans la notation bra-ket ou notation de Dirac usuelle en mécanique quantique, comme combinaison linéaire à coefficients complexes :

${\displaystyle |q\rangle =\alpha _{1}|q_{1}\rangle +\alpha _{2}|q_{2}\rangle \cdots \alpha _{n}|q_{n}\rangle }$,

avec la condition additionnelle

${\displaystyle |\alpha _{1}|^{2}+\cdots +|\alpha _{n}|^{2}=1}$.

Cette écriture s'exprime en disant que ${\displaystyle |q\rangle }$ est la superposition des états ${\displaystyle |q_{i}\rangle }$, le nombre ${\displaystyle \alpha _{i}}$ est l'amplitude de l'état ${\displaystyle |q_{i}\rangle }$. Ainsi, chaque état quantique définit un certain « nuage » des états de ${\displaystyle Q}$: il est simultanément dans chacune des états, avec l'amplitude correspondante. Notamment, l'état quantique initial ${\displaystyle s}$ est aussi une combinaison linéaire des états ${\displaystyle |q_{i}\rangle }$ de norme 1.

Pour un mot ${\displaystyle w=a_{1}a_{2}\cdots a_{m}}$, le vecteur

${\displaystyle U_{a_{m}}U_{a_{m-1}}\cdots U_{a_{1}}\,s}$

est l'état quantique atteint après la lecture du mot ${\displaystyle w}$; comme il est représenté en vecteur colonne, les matrices s'appliquent en sens inverse. Dans les articles proches de la théorie des automates, on trouve la notation « duale », où les vecteurs d'états sont des vecteurs lignes, et l'écriture du produit des matrices correspond alors à la suite des lettres d'entrée lues[1].

La probabilité d'observation d'un état ${\displaystyle |q\rangle }$ est le nombre ${\displaystyle P|q\rangle }$, où ${\displaystyle P}$ est la matrice de projection donnée dans la définition. Une variante de définition consiste à donner un ensemble ${\displaystyle F}$ d'états terminaux. Alors la probabilité d'observation de ${\displaystyle |q\rangle =\alpha _{1}|q_{1}\rangle +\alpha _{2}|q_{2}\rangle \cdots \alpha _{n}|q_{n}\rangle }$ est

${\displaystyle \sum _{q\in F}|\alpha _{q}|^{2}}$.

En écrivant

${\displaystyle P=\sum _{q\in F}|q\rangle \,\langle q|}$,

on voit que ${\displaystyle P}$ est une projection sur les états terminaux et que

${\displaystyle P|q\rangle =\sum _{q\in F}\alpha _{q}|q\rangle }$

de sorte que la probabilité d'observation s'écrit

${\displaystyle \sum _{q\in F}|\alpha _{q}|^{2}=\Vert P|q\rangle \Vert ^{2}}$.

La probabilité d'acceptation d'un mot ${\displaystyle w=a_{1}a_{2}\cdots a_{m}}$ est par définition le nombre

${\displaystyle {\text{Pr}}(w)=\Vert P\,U_{a_{m}}U_{a_{m-1}}\cdots U_{a_{1}}\,s\Vert ^{2}}$.

C'est donc la probabilité d'observation de l'état quantique obtenu après lecture du mot w. L'opération qui consiste à évaluer ce nombre est une mesure.

Le langage ${\displaystyle L}$ est accepté ou reconnu avec la probabilité ${\displaystyle p}$ est l'ensemble des mots ${\displaystyle w}$ tels que ${\displaystyle {\text{Pr}}(w)>p}$ (acceptation par seuil strict) ou ${\displaystyle {\text{Pr}}(w)\geq p}$ (acceptation par seuil large).

Pour se rapprocher de notations employées par ailleurs en théorie des automates, l'état d'un mot ${\displaystyle w}$ est parfois noté ${\displaystyle \langle w|}$. Pour un mot${\displaystyle w=a_{1}a_{2}\cdots a_{m}}$, on a alors

${\displaystyle \langle w|=s^{*}U_{a_{1}}U_{a_{2}}\cdots U_{a_{m}}}$

où ${\displaystyle s^{*}}$ est l'adjoint de l'état ${\displaystyle s}$.

À la place de la notation matricielle, on rencontre aussi des fonctions de transition ${\displaystyle \delta :Q\times A\times Q\to \mathbb {C} }$ plus familières en théorie des automates. Une matrice ${\displaystyle U_{a}}$ est considérée comme une application de l'ensemble des états dans lui-même, avec ${\displaystyle (U_{a})_{k,j}=\delta (k,a,j)}$ et les coefficients du vecteur ${\displaystyle tU_{a}}$ sont

${\displaystyle (tU_{a})_{j}=\sum _{q\in Q}t_{k}\delta (k,a,j)}$.

Enfin, on peut aussi travailler avec des nombres réels au lieu des nombres complexes. Le matrices unitaires sont alors des matrices orthogonales.

Pour un automate quantique ${\displaystyle {\mathcal {A}}}$, notons ${\displaystyle f_{\mathcal {A}}}$ la fonction définie par

${\displaystyle f_{\mathcal {A}}(w)={\text{Pr}}(w)}$

qui associe à tout mot sa probabilité d'acceptation. C'est la fonction calculée par l’automate. Dans leur article[2], Moore et Crutchfield démontrent un certain nombre de propriétés de ces fonctions[3]. D'abord : La série formelle en variables non commutatives

${\displaystyle \sum _{w\in \Sigma ^{*}}f_{\mathcal {A}}(w)}$

est est une série formelle rationnelle (en). Les propriétés de clôture suivantes sont vraies : Soient ${\displaystyle f}$ et ${\displaystyle g}$ sont des fonctions calculées par des automates finies quantiques.

• (convexité) : ${\displaystyle \alpha f+\beta g}$ est calculable par un automate fini quantique si ${\displaystyle |\alpha |^{2}+|\beta |^{2}=1}$.
• (intersection) : ${\displaystyle fg}$ est calculée par un automate fini quantique.
• (complément): ${\displaystyle 1-f}$ est calculée par un automate fini quantique.
• (morphisme inverse): Si ${\displaystyle h:\Delta ^{*}\to \Sigma ^{*}}$ est un morphisme, alors ${\displaystyle fh}$ est calculable par automate fini quantique.

Il existe aussi une sorte de lemme d'itération pour ces fonctions; il dit que pour tout ${\displaystyle w}$ et tout ${\displaystyle \epsilon }$, il existe ${\displaystyle k}$ tel que pour tout ${\displaystyle u}$ et ${\displaystyle v}$, on a ${\displaystyle f_{\mathcal {A}}(uw^{k}v)-f_{\mathcal {A)}}(uv)|<\epsilon }$.

Un certain nombre de résultats concerne la décidabilité de questions pour un automate fini quantique ${\displaystyle {\mathcal {A}}}$, avec la notation ${\displaystyle f_{\mathcal {A}}(w)={\text{Pr}}(w)}$ et pour une valeur de seuil ${\displaystyle \lambda }$ donnée. Les questions suivantes sont indécidables :

• Existe-t-il un mot ${\displaystyle w}$ tel que ${\displaystyle f_{\mathcal {A}}(w)\geq \lambda }$,
• Existe-t-il un mot ${\displaystyle w}$ tel que ${\displaystyle f_{\mathcal {A}}\leq \lambda }$,
• Existe-t-il un mot ${\displaystyle w}$ tel que ${\displaystyle f_{\mathcal {A}}(w)=\lambda }$.

En revanche, les questions suivantes sont décidables[4] :

• Existe-t-il un mot ${\displaystyle w}$ tel que ${\displaystyle f_{\mathcal {A}}(w)>\lambda }$,
• Existe-t-il un mot ${\displaystyle w}$ tel que ${\displaystyle f_{\mathcal {A}}(w)<\lambda }$.

Tous ces problèmes sont en revanche indécidables pour les automates probabilistes.

Le langage ${\displaystyle L_{\geq }}$ reconnu par un automate quantique à seuil ${\displaystyle \lambda }$ (respectivement à seuil strict ${\displaystyle L_{>}}$) est l’ensemble

${\displaystyle L_{\geq }=\{w\mid f_{\mathcal {A}}(w)\geq \lambda \}}$

ou, respectivement, ${\displaystyle L_{>}=\{w\mid f_{\mathcal {A}}(w)>\lambda \}}$,

où ${\displaystyle f_{\mathcal {A}}(w)}$ est la probabilité d'acceptation de ${\displaystyle w}$ dans l'automate ${\displaystyle {\mathcal {A}}}$. Le nombre ${\displaystyle \lambda }$ est appelé un point de coupure (« cut point »).

Les problèmes de décider si le langage ${\displaystyle L_{\geq }}$ est vide ou si le langage ${\displaystyle L_{>}}$ est vide sont tous deux indécidables pour les automates probabilistes [5]. En revanche, pour les automates quantiques dans la définition de Moore et Crutchfield, le premier problème est indécidable alors que le deuxième est décidable.

Un point de coupure ${\displaystyle \lambda }$ est dit isolé s'il existe un nombre ${\displaystyle \epsilon }$ tel que

${\displaystyle \vert f_{\mathcal {A}}(w)-\lambda \vert \geq \epsilon }$

pour tout mot ${\displaystyle w}$ ou, de manière équivalente, s'il existe un intervalle non vide autour de ${\displaystyle \lambda }$ qui ne contient la probabilité d'acceptation d'aucun mot. Si un point de coupure est isolé, alors les langages ${\displaystyle L_{\geq }}$ et ${\displaystyle L_{>}}$ sont réguliers. De fait, on sait plus sur ces langages : ce sont des langages à groupes, c'est-à-dire des langages réguliers dont les monoïdes syntaxtiques sont des groupes finis[6] - [7].

Des questions liées sont :

• Étant donné ${\displaystyle {\mathcal {A}}}$ et ${\displaystyle \lambda }$, est-ce que ${\displaystyle \lambda }$ est isolé pour ${\displaystyle {\mathcal {A}}}$ ?
• Étant donné ${\displaystyle {\mathcal {A}}}$, existe-t-il un point de coupure isolé pour ${\displaystyle {\mathcal {A}}}$ ?

Ces questions sont décidables[8]. Il apparaît qu'un objet joue un rôle particulier dans cette étude, faite dans le cadre réel : c'est le groupe ${\displaystyle {\bigl [}\left[G({\mathcal {A}})\right]{\bigr ]}}$ qui est la fermeture, pour la topologie euclidienne, du groupe (mathématiques) engendré par les matrices ${\displaystyle U_{a}}$ orthogonales d'un automate quantique. Ce groupe est compact. De plus, ce groupe est algébrique, ce qui signifie que sa clôture euclidienne est égale à sa clôture de Zariski. Le résultat principal qui permet la preuve est que la clôture de Zariski d'un groupe de matrices finiment engendré est effectivement calculable[8].

Automate à deux états.

Considérons l'automate fini déterministe à deux états donné ci-contre. Un état quantique est un vecteur qui s'écrit en notation bra-ket :

${\displaystyle |q\rangle =|\alpha _{1}|S_{1}\rangle +\alpha _{2}|S_{2}\rangle ={\begin{pmatrix}a_{1}\\a_{2}\end{pmatrix}}}$

où les nombres complexes ${\displaystyle \alpha _{1},\alpha _{2}}$ sont normalisés de sorte que ${\displaystyle |\alpha _{1}|^{2}+|\alpha _{2}|^{2}=1}$. Les matrices de transition unitaires peuvent être simplement

${\displaystyle U_{0}={\begin{pmatrix}0&1\\1&0\end{pmatrix}}}$ et ${\displaystyle U_{1}={\begin{pmatrix}1&0\\0&1\end{pmatrix}}}$.

Si l'on choisit ${\displaystyle S_{1}}$ comme état final, comme indiqué dans le diagramme, la matrice de projection est :

${\displaystyle P={\begin{pmatrix}1&0\\0&0\end{pmatrix}}}$

Si l'état initial est ${\displaystyle |S_{1}\rangle }$ ou ${\displaystyle |S_{2}\rangle }$, le comportement de l'automate est exactement celui de l'automate fini usuel. En particulier, les mots qui sont acceptés le sont avec probabilité un, et le langage accepté a pour expression régulière l'expression : ${\displaystyle (1+01^{*}0)^{*}}$ respectivement ${\displaystyle (1+01^{*}0)^{*}01^{*}}$. Si en revanche ${\displaystyle \alpha _{1}}$ et ${\displaystyle \alpha _{2}}$ sont tous deux non nuls, le comportement est plus compliqué, et si de plus les matrices ${\displaystyle U_{0}}$ et ${\displaystyle U_{1}}$ ne sont pas aussi simples, on peut avoir d'encore d'autres résultats.