4.2 q-calcul
4.2.1 Introduction
Le q-calcul [Perdrix, 2006] est un ensemble de règles
agissant sur les q-termes. Ces règles préservent tout ou partie
de la hiérarchie sémantique. De plus, les règles du
q-calcul forment un système de réécriture terminant et
confluent.
Dans le q-calcul, sont autorisées : les transformations
unitaires, les mesures sur un qubit, mais aussi les transformations admissibles
en général.
Dans ce chapitre, nous introduisons le q-calcul. Une
sémantique dénotationnelle pure fondée sur les domaines
probabilistes est également introduite, associant à chaque terme
du q-calcul une fonction probabiliste.
4.2.2 Termes du q-calcul
Définition 12. Le formalisme
utilisé pour la syntaxe des termes du q-calcul s'inspire des
algèbres de processus, ainsi la brique de base est l'action. Une action
a de H dans H' est de la forme :
a := M|M,a
où H et H' sont des espaces de Hilbert et M
E L (H, H').
Définition 13. (Terme du
q-calcul) Un terme P est un quadruplet (K, I, F, R), où
K est un ensemble fini de processus, I, F c K sont respectivement les
états initiaux et finaux, et R est un ensemble fini de
définitions de processus de la forme :
q = [a].q(+[a].q)*
où chaque q E K/F apparaît une fois
et une seule dans la partie gauche des définitions, de plus, tous les
processus apparaissants dans R sont des éléments de K. Enfin, il
existe un ensemble d'espaces de Hilbert Hq, q E K tel que
pour toute définition de processus q = > i[ai].qi de R, chaque ai est
une action de Hq dans Hqi . De plus, une condition de
complétude >i a i = IdHq doit également
être vérifiée, où a est défini par:
M = M†M
(M, a) = M + a
Exemple 1 : Pour toute transformation
unitaire U E L(K, L), soit PU = (j, f, j, f, R),
avec Hi = K, Hf = L et
R : j = [U].f
36
chapitre4 : Modèles de calcul quantique
La condition de complétude est vérifiée,
PU est donc un terme du q-calcul. Exemple 2 : Soit
P = (i, q, f, i, f, R), avec Hi = Hq
= Hf = H0,1 et R :
i = [|0ih0|].f + [|1ih1|].q
q =
[|+ih+|, |-ih-|].i
avec: |+i= v2 1 (|0i+ |1i)et
|-i=v2 1(|0i- |1i)
Les conditions de complétude sont
vérifiées : |0ih0| + |1ih1| = IdH{0,1}
et |+ih+| + |-ih-| = IdH{0,1}
4.2.3 Représentation graphique
Un q-terme peut être représenté
graphiquement par un automate d'états fini.En effet à tout
q-terme, on peut associer un automate d'états fini dont les états
sont les processus du q-terme, les états initiaux (finaux) sont les
processus initiaux (finaux), les transitions de q vers p sont
étiquetées par les actions ai telles que q =
... + [ai].p + ... est une
définition apparaissant dans le q-terme. La représentation
graphique du q-terme de l'exemple 2 est donné en figure 4.1.
FIGURE 4.1 - Représentation graphique du q-terme de
l'exemple 2.
Cette représentation à base d'automate peut se
substituer aux règles de définitions des processus, en revanche
elle ne permet pas de décrire quels sont les espaces de Hilbert
associés à chaque processus.
| 
