Automate quantique

En informatique quantique et en informatique théorique, un automate fini quantique est une généralisation des automates finis où un mot est accepté selon le résultat d'une certaine mesure. Il existe plusieurs modèles des automates finis quantiques ; le plus restrictif est celui des automates dits « measure-once » de Moore et Crutchfield 2000 ; un autre est celui des automates « measure-many » de Kondacs et Watrous 1997. Ces deux modèles sont très différents l'un de l’autre ; le modèle « measure-once » se rapproche plus de la théorie classique des automates finis. D'autres définitions, plus générales, ont été proposées, en généralisation des diverses variantes des automates, par exemple par Yakaryilmaz et Say 2011. Un des objectifs de l’étude des automates fini quantiques est l’étude des langages formels qu'ils acceptent ; un autre est d'étudier les problèmes de décidabilité pour ces classes d'automates et de langages.

Les automates finis quantiques sont similaires aux automates probabilistes, mais la classe des langages reconnus par automates quantiques est strictement contenue dans la classe des langages reconnus par automates probabilistes. Les automates finis quantiques peuvent aussi être vus comme une version quantique des sous-shifts de type fini, ou comme une variante quantique des chaînes de Markov. Les automates finis quantiques sont, à leur tour, des cas particuliers des automates finis dit géométriques ou des automates finis dit topologiques.

Un automate fini quantique opère sur des mots finis $w=a_{1}a_{2}\cdots a_{m}$, dont les lettres $a_{i}$ sont dans un alphabet donné $\Sigma$. Il attribue à chaque mot $w$ une probabilité; en fonction de cette probabilité, le mot est accepté ou rejeté par l'automate. Les langages acceptés par les automates finis quantique ne coïncident pas avec les langages rationnels acceptés par les automates finis, ni avec les langages stochastiques acceptés par les automates finis probabilistes.

Automate fini quantique MO

Des deux définitions d'automate fini quantique les plus usuelles, celle des automates « measure once » ou « MO » donnée par Moore et Crutchfield est la plus simple, et la plus proche des automates probabilistes plus traditionnels.

Définitions

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

• un ensemble $Q=\{q_{1},\ldots ,q_{n}\}$ d'états. À chaque état $q_{i}$ est associé un élément noté $|q_{i}\rangle$ d'un espace de Hilbert $H_{n}$ de dimension $n$, en général $\mathbb {C} ^{n}$, de sorte que $\{|q_{1}\rangle ,\ldots ,|q_{n}\rangle \}$ forme une base orthonormée de $H_{n}$. On suppose en général que $q_{i}$ est le $i$-ème vecteur unité,
• un matrice unitaire $U_{a}$ d'ordre $n$ pour chaque lettre $a$ de $\Sigma$. Cette matrice est la représentation d'un opérateur unitaire dans la base choisie.
• un vecteur $s$ d'ordre $n$ de norme $\Vert s\Vert =1$, état quantique initial.
• une matrice de projection orthogonale $P$ d'ordre $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 $|q\rangle$ qui se décompose sur la base $Q$ et s'écrit, dans la notation bra-ket ou notation de Dirac usuelle en mécanique quantique, comme combinaison linéaire à coefficients complexes :

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

avec la condition additionnelle

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

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

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

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

est l'état quantique atteint après la lecture du mot $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.

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

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

En écrivant

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

on voit que $P$ est une projection sur les états terminaux et que

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

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

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

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

${\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 $L$ est accepté ou reconnu avec la probabilité $p$ est l'ensemble des mots $w$ tels que ${\text{Pr}}(w)>p$ (acceptation par seuil strict) ou ${\text{Pr}}(w)\geq p$ (acceptation par seuil large).

Variantes de notation et de modèle

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

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

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

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

$(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.

Propriétés

Fonction calculée par un automate quantique

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

$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, Moore et Crutchfield démontrent un certain nombre de propriétés de ces fonctions. D'abord : La série formelle en variables non commutatives

$\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 $f$ et $g$ sont des fonctions calculées par des automates finies quantiques.

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

Lemme d'itération

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

Problèmes de décidabilité

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

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

En revanche, les questions suivantes sont décidables :

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

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

Langages de points de coupure

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

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

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

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

Les problèmes de décider si le langage $L_{\geq }$ est vide ou si le langage $L_{>}$ est vide sont tous deux indécidables pour les automates probabilistes . 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 $\lambda$ est dit isolé s'il existe un nombre $\epsilon$ tel que

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

pour tout mot $w$ ou, de manière équivalente, s'il existe un intervalle non vide autour de $\lambda$ qui ne contient la probabilité d'acceptation d'aucun mot. Si un point de coupure est isolé, alors les langages $L_{\geq }$ et $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.

Des questions liées sont :

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

Ces questions sont décidables. Il apparaît qu'un objet joue un rôle particulier dans cette étude, faite dans le cadre réel : c'est le groupe ${\bigl [}\left[G({\mathcal {A}})\right]{\bigr ]}$ qui est la fermeture, pour la topologie euclidienne, du groupe (mathématiques) engendré par les matrices $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.

Exemple

Automate à deux états.

Table de transition

	1	0
S1	S1	S2
S2	S2	S1

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 :

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

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

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

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

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

Si l'état initial est $|S_{1}\rangle$ ou $|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 : $(1+01^{*}0)^{*}$ respectivement $(1+01^{*}0)^{*}01^{*}$. Si en revanche $\alpha _{1}$ et $\alpha _{2}$ sont tous deux non nuls, le comportement est plus compliqué, et si de plus les matrices $U_{0}$ et $U_{1}$ ne sont pas aussi simples, on peut avoir d'encore d'autres résultats.

Automate fini quantique MM

Le modèle d'un automate quantique au sens de Kondacs et Watrous, appelé automate « measure many » ou « MM », diffère du modèle précédent : dans le modèle MO une mesure n'est effectuée qu'en fin de calcul. Dans le modèle MM considéré maintenant, une mesure est faite à chaque étape du calcul. Le principe de la physique quantique dit qu'une mesure est destructrice, et ce principe trouve son expression dans le formalisme proposé.

On a maintenant trois types d'états qui forment une partition de l'ensemble d'états:

• des états d'acceptation $Q_{a}$
• des états de refus ou rejet, $Q_{r}$
• des états de continuation, $Q_{c}$, aussi appelés états neutres.

L'espace de Hilbert $H_{n}$ est décomposé en trois sous-espaces orthogonaux

$H_{n}=H_{a}\oplus H_{r}\oplus H_{c}$

correspondant aux trois types d'états $Q_{a},Q_{r},Q_{c}$. Pour chacun des trois ensembles d'états distingués, il y a une matrice de projection associée, notée $P(a),P(r)$ et$P(c)$ qui projette sur le sous-espace correspond. Elle est définie par

$P(a)=\sum _{q\in Q_{a}}|q\rangle \langle q|$,

et de même pour les deux autres ensembles.

L'automate opère de la manière suivante : Après chaque lecture d'une lettre

• on mesure l'amplitude sur les états d'acceptation,
• on mesure l'amplitude sur les états de refus,
• on continue en ne conservant que les amplitudes des états de continuation.

La mesure consiste à vérifier si la projection est dans un sous-espace approprié. Après la lecture du mot, on a une probabilité d'acceptation et une probabilité de refus.

Plus précisément, soit $|q\rangle$ l'état courant de l'automate. Soit

$|t\rangle =U_{a}|q\rangle$

l'état de l’automate Après la lecture d'une lettre $a$. Une mesure est réalisé en utilisant les opérateurs de projection, qui indiquent dans lequel des trois sous-espaces $\mathbb {H} _{a}$, $\mathbb {H} _{r}$ ou $H_{c}$ se trouve l'image du vecteur. La probabilité est donnée par

$\operatorname {Pr} _{a}(t)=\Vert P_{a}|t\rangle \Vert ^{2}$

pour l'espace des états acceptants, et de manière analogue pour les autres.

Pour une entrée $a_{1}a_{2}\cdots a_{m}$, l'automate opère comme suit : en commençant avec le vecteur initial s, les vecteurs $sU_{a_{1}}$, $sU_{a_{1}}U_{a_{2}}$ sont mesurés tant que le résultat est dans l'espace de continuation. S'il est dans l'espace d'acceptation, le calcul s'arrête et le mot est accepté, s'il est dans l'espace de refus, le calcul s'arrête également, mais le mot est rejeté. On suppose que le mot est délimité par un marqueur de fin, et à la vue de ce marqueur, l'automate doit décider d'accepter ou de rejeter le mot, et il ne peut rester dans un état neutre. C'est donc un automate qui peut accepter ou rejeter un mot sans l'avoir lu dans sa totalité.

Formellement, l'automate définit une fonction sur les mots qui est

$\operatorname {Pr} (a_{1}a_{2}\cdots a_{m})=\sum _{k=1}^{m}\left\Vert s\left(\prod _{i=1}^{k-1}U(a_{i})P(c)\right)U(a_{k})P(a)\right\Vert ^{2}$

qui détermine la probabilité d'acceptation. Là aussi, l'expression « duale » se rencontre fréquemment.

Les mêmes questions que celles posées pour le modèle MO sont toutes indécidables pour le modèle MM.

Les langages reconnus par les automates MM avec un point de coupure isolé sont rationnels, mais ces automates ne sont pas assez puissants pour reconnaître tous les langages réguliers. Par exemple, le langage $\{a,b\}^{*}a$ ne peut être reconnu par une automate MM avec point de coupure isolé.

Des variantes d'acceptation ont été étudiées pour les automates MM. Ainsi, des automates travaillant avec des « probabilités élevées » (par exemple au moins 7/9), les langages acceptés sont reconnus aussi par des automates finis traditionnels réversibles, c'est-à-dire des automates dont les transformations définies par les lettres sont des fonctions partielles bijectives.

Les langages reconnus pas des automates MM ne sont pas fermés pour l'union, intersection ou les autres opérations booléennes usuelles.

Bibliographie

• Michael O. Rabin, « Probabilistic Automata », Information and Control, vol. 6, n^o 3,‎ septembre 1963, p. 230-245
• Alex Brodsky et Nicholas Pippenger, « Characterizations of 1-Way Quantum Finite Automata », SIAM Journal of Computing, vol. 31, n^o 5,‎ janvier 2002, p. 1456-1478 (DOI 10.1137/s0097539799353443, arXiv http://xxx.lanl.gov/abs/quant-ph/9903014).
• Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran et Natacha Portier, « Decidable and undecidable problems about quantum automata », SIAM Journal of Computing, vol. 34, n^o 6,‎ 2005, p. 1464-1473 (DOI 10.1137/S0097539703425861)
• Harm Derksen, Emmanuel Jeandel et Pascal Koiran, « Quantum automata and algebraic groups », Journal of Symbolic Computation, vol. 39, n^os 3-4,‎ mars 2005, p. 357-371 (DOI 10.1016/j.jsc.2004.11.008, lire en ligne).
• Alberto Bertoni, Christian Choffrut et Flavio d’Alessandro, « On the decidability of the intersection problem for quantum automata and context-free languages », International Journal on Foundations of Computer Science, vol. 25, n^o 8,‎ décembre 2014, p. 1065-1081 (DOI 10.1142/s0129054114400243, arXiv https://arxiv.org/pdf/1303.2967v1.pdf).
• A. Yakaryilmaz et A.C.C. Say, « Unbounded-error quantum computation with small space bounds », Information and Computation, vol. 209, n^o 6,‎ 2011, p. 873-892
• Cristopher Moore et James P. Crutchfield, « Quantum automata and quantum grammars », Theoretical Computer Science, vol. 237, n^os 1-2,‎ 2000, p. 275-306
• Attila Kondacs et John Watrous, « On the power of quantum finite state automata », FOCS’97: Proceedings of the 38th Annual Symposium on Foundations of Computer Science,‎ 1997, p. 66-75
• Andris Ambainis et Abuzer Yakaryilmaz, « Automata and Quantum Computing », sur arxiv, juin 2015
• Mika Hirvensalo, Quantum Computing, Springer-Verlag, 2004, 2^e éd.
• Mika Hirvensalo, « Quantum Automata Theory – A Review », dans Werner Kuich et George Rahonis, Algebraic Foundations in Computer Science : Bozapalidis Festschrift, Springer-Verlag, coll. « Lecture Notes in Computer Science 7020 », 2011 (ISBN 978-3-642-24896-2, DOI 10.1007/978-3-642-24897-9), p. 146–167.
• (en) Luigi Accardi, « Quantum stochastic processes », dans Michiel Hazewinkel, Encyclopædia of Mathematics, Springer, 2002 (ISBN 978-1556080104, lire en ligne)

Articles liés

• Informatique quantique
• Automate probabiliste
• Espace de Hilbert
• Matrice unitaire