CHAPITRE 4
MODÈLES DE CALCUL QUANTIQUE
32
Dans cette partie nous allons présenter la machine de
Turing quantique comme modèle réversible et nous allons introduit
un model avec une plus grande expressivité qui est le q-calcul
présenté par Simon PERDRIX dans [Perdrix, 2006] et introduire une
algèbre q-CCS des processus quantiques purs.
4.1 La machine de Turing quantique
La machine de Turing quantique est définie par D. Deutsch
[Deutsch, 1985] en 1985 et par la suite plusieurs études sur le
modèle original ont entrepris généralement
présenté dans les travaux de Bernstein et Vazirani [Bernstein et
Vazirani, 1997] et Simmon Predrix [Perdrix, 2006]. Pour être complet, la
définition des machines de Turing déterministe est donnée
par la définition suivante :
Définition 6. (déterministic
Turing machine (DTM)). Une machine de Turing détermi-
niste [law Adam MISZCZAK, 2011] est défini par un
triplet (Q, E, 8) où :
E Est un alphabet fini avec un symbole identifié flan
#,
Q Est un ensemble fini d'états avec un état
initial qo identifié et l'état final qf =6
qo
et 8, la fonction de transition déterministe, est une
fonction :
8 : Q x E -+ Q x
Ex{-1,0,1}
Définition 7. (pre Quantum Turing
machine (pQTM)). Une machine de Turing pré-
quantique est défini par un triplet (Q, E, 8)
où :
E est un alphabet fini avec un symbole identifié flan
#,
Q est un ensemble fini d'états avec un état
initial qo identifié et l'état final qf =6 q0,
Et 8, la fonction de transition quantique, est une fonction
:
33
chapitre4 : Modèles de calcul quantique
8 : Q × ? CQx>
x{-1,0,1}
(p, F) 7-?
q?Q,ó?>,d?{-1,0,1}
áp,,q,ó,d |u, q,
di
Pour plus de commodité, l'expression 8 (p, F, q, u,
d) est utilisée pour distinguer
áp,,q,ó,d ? C
c'est-à-dire l'amplitude 8 (p, F) de |u, q, di.
L'évolution d'un pQTM M est donnée par l'opérateur
linéaire UM définie sur
CQx>* xZ (appelé
l'espace d'état de configurations) :
8(p, Tx, q, u, d)|q, T x
ó , x + dihp, T, x|
UM =
p,q?Q,ó?>,d?{-1,0,1},T?Z*
Où : T x ó?
Z* est T où le symbole dans la
position x est remplacé par u. [law Adam MISZCZAK,
2011]
Définition 8. (la condition `'bien
formée») Une machine de Turing pré-quantique est bien
formée si et seulement si UM est une isométrie
i.e.
U†MUM =
Id
Une machine de Turing quantique (QTM) est une machine de
Turing pré-quantique bien formée.
Une machine de Turing quantique est un triplet(Q, , 8)
où :
: Ensemble fini d'alphabet et le symbole ]
Q : Ensemble fini d'états avec q0
=6 qf
8 : Fonction de transition définie par:
8 : Q × ? Q ×
×{?,-,?} {?, -, ?} parfois
notés {-1, 0, 1}
Le scalaire hq,F,d|8 (p,u)i est l'amplitude de
|q,F,di est noté 8 (p,u,q,F,d). une configuration est
un vecteur normé de HQx>* xZ
T ? * : état de base du ruban
de M et x ? Z : la position de la tête et
Tx ? : le symbole
de bas pointé par la
tête.
MTQ : calcul de transformation unitaire : Une
MTQ efficace met en oeuvre une transformation unitaire donné, se
rapprochant par un produit de transformations unitaires simples. La
«super-puissance» du calcul quantique : la
réversibilité, le parallélisme quantique, et les
interférences de chemins de calcul. Il est possible de définir
une MTQ Universel.
Observation de QTM : Quand une MTQ M en
superposition ö = i áiCi est
observé ou mesuré, une configuration Ci est
observée avec une probabilité ái. De plus, la
superposition de M est mis à jour à ö'
= Ci. Il est également possible d'effectuer une mesure
partielle, par exemple, supposons que nous voulons observer la première
cellule (qui contient 0 ou 1). Supposons que la
34
chapitre4 Modèles de calcul quantique
superposition est ç = Pi
á0iC0i + ç = Pi
á1iC1i si 0 est observée, Pr [0]
= ç = Pi |á0i|2 et
la nouvelle superposition est donnée par1vpr[0]ö
= Pi á0iC0i
En général, la sortie d'une MTQ est un
échantillon provenant d'une distribution de probabilité [law Adam
MISZCZAK, 2011].
Machine de Turing quantique : entrée / sortie
Conventions
Définition 9. Une configuration
finale est toute configuration dans une MTQ M en état finale qf. On dit
qu'une MTQ M s'arrête en cours d'exécution avec un temps T sur
l'entrée x Si, lorsque M est exécuté avec l'entrée
x, au temps T la superposition ne contient que des configurations finales, et
en tout temps Ti ? T la superposition ne contient pas de
configurations finales. Bernstein et Vazirani [Bernstein et Vazirani, 1997]
donnent également des définitions approfondies sur la sortie de
MTQ.
Définition 10. (Stationnarité et
forme normale) Une MTQ M est appelé bien
comportés si elle s'arrête sur toutes les chaînes
d'entrée dans une superposition finale où chaque configuration a
la tête de ruban dans la même cellule.
Si cette cellule est toujours la cellule de départ,
nous appelons M stationnaire. Nous disons que M est en forme normale si elle
est bien formée et qf mène toujours à q0.
Définition 11. unidirectionnelle
Une MTQ est appelée unidirectionnelle si chaque
état peut être saisi que d'une seule direction.
Résiliation de MTQ
Comment pouvons-nous vérifier que les MTQ M
s'arrêtent efficacement? Bernstein et Vazirani dans [Bernstein et
Vazirani, 1997] écrit : «Cela peut être accompli en
effectuant une mesure de vérifier si la machine est en état final
qf. Faire de cette mesure partielle n'a pas d'autre effet sur le
calcul ". Cela peut être "mis en oeuvre" avec une cellule d'observation
dans lequel on peut effectuer une mesure partielle.
MTQ et Familles de Circuits quantiques
Le total des modèles de calcul quantique les plus
pertinentes, à savoir MTQ et Familles de Circuits quantiques sont
équivalentes. Dans [Y, 1993], Yao propose un codage intéressant
du MTQ en termes de familles de circuits quantique.
35
chapitre4 : Modèles de calcul quantique
| 
