Modèles formels pour l'informatique quantique

Promotion 2012 - 2013

République Algérienne Démocratique et Populaire
Ministère de l'Enseignement Supérieur et de la Recherche Scientifique
Université Abess Laghrour KHENCHELA
Institut des Sciences et Technologies
Département d'Informatique et Mathématiques

Mémoire

En vue de l'obtention du diplôme de Master 2 en Informatique
Spécialité : informatique fondamentale et Appliquée

Thème:

Modèls formels pour l'informatique

quantique

Présenté par : Benahamed Sami

Rapporteur: M.Khiar Abdelouahabe

i

Table des matières

Table des matières ii

Remerciement 1

Résumé 2

Introduction générale 3

1 Préliminaires 5

1.1 Notions mathématiques et physiques 5

1.1.1 Notations mathématique 5

1.1.2 L'aspect physique (mécanique quantique) [Perdrix, 2006] 6

1.1.2.1 Postulat 1 : vecteur d'état et notation de Dirac : 6

1.1.2.2 Postulat 2 : Système composé 7

1.1.2.3 Postulat 3 : Evolution quantique : 9

2 Information, donnée quantique 10

2.1 Les nombres quantiques : 10

2.2 Les circuits quantiques : 11

2.2.1 Qubit 11

2.2.2 Sphère de Bloch 12

2.2.3 Mesure d'un qubit 13

2.2.4 Registre quantique 13

2.2.5 Porte quantique »L'évolution après mesure» 13

2.2.5.1 portes à un qubit (opérations unitaires sur un seul qubit) . . . 14

2.2.5.2 Portes logiques à deux qubits) 14

2.2.5.3 Portes à plus de deux qubits) 15

2.3 Complexité d'un algorithme quantique : 18

3 Les algorithmes quantiques 19

3.1 introduction : 19

3.2 Les problèmes posés sous forme d'une boite noire : 19

3.2.1 Exemples d'oracles classiquement difficiles 20

3.3 L'Algorithme quantique de Deutsch-Josza : 21

3.4 Algorithme de recherche quantique (Grover) : 23

3.5 L'Algorithme de Simon [Haroche, 2002] 24

3.6 Algorithme quantique de Shor [Jorrand, 2012] 26

ii

Table des matières

4 Modèles de calcul quantique 32

4.1 La machine de Turing quantique 32

4.2 q-calcul 35

4.2.1 Introduction 35

4.2.2 Termes du q-calcul 35

4.2.3 Représentation graphique 36

4.3 Sémantiques dénotationnelles 36

4.3.1 Sémantique pure :[|.|] 37

4.4 qCCS 37

4.4.1 Introduction 37

4.4.2 Syntaxe et Sémantique Opérationnelle [YING et al., 2003] 38

4.4.2.1 La syntaxe 38

4.4.2.2 Sémantique Opérationnelle 40

5 Langages de programmation quantiques 43

5.1 Comment définir la programmation quantique? 43

5.2 Les langages impératifs 43

5.2.1 Quantum Computing Language (QCL) 44

5.2.1.1 Syntaxe de QCL [Omer, 2000] [Omer, 2009] 44

5.3 Langages Fonctionnels et Lambda-Calcul 46

5.3.1 QML : langage de programmation fonctionnel quantique 48

5.3.1.1 La conception de QML 48

5.3.1.2 La syntaxe de QML 49

5.3.2 Quipper : langage de programmation quantique scalable 50

6 Q-LOTOS 53

6.1 Introduction 53

6.2 Basic LOTOS 53

6.2.1 Syntaxe de Basic LOTOS : 53

6.2.2 Sémantique opérationnelle de Basic LOTOS 55

6.3 Q-LOTOS 55

6.3.1 Syntaxe de Q-LOTOS 55

6.3.2 Sémantique Opérationnelle 56

6.4 Conclusion 57

Conclusion générale 58

Bibliographie 61

iii

Table des figures

2.1 Nombers quantique 10

2.2 rotation d'électron sur lui-même 11

2.3 Sphère de Bloch 12

2.4 Decomposition de la porte quantique CNOT 16

3.1 représentation par oracle. 20

3.2 L'oracle de Deutsch-Josza 21

3.3 Algorithme de recherche quantique (Grover) 23

3.4 Exemple de recherche quantique 24

3.5 L'Algorithme de Simon 25

3.6 Rôle de l'intrication et de la mesure dans l'algorithme de Simon 26

3.7 Superposition des 2ⁿ valeurs dans n qubit 27

3.8 L'intrication 28

3.9 Utilisation de la période r 28

3.10 Comment trouver r? 29

3.11 Transformée de Fourier Quantique 30

4.1 Représentation graphique du q-terme de l'exemple 2. 36

iv

Liste des tableaux

2.1 Table de vérité de porte logique universelle réversible de Toffoli. 16

2.2 Table de vérité de porte logique universelle réversible de CNOT 17

1

Remerciement

Je témoigne toute ma gratitude à M. Toufik Maerouk d'avoir présidé mon jury. Je remercie M. Nabil Mesaoudi d'avoir accepté de participer à ce jury.

Je remercie également mon encadreur KHIAR Abdelouahab de m'avoir fait découvrir le monde de l'informatique quantique et de me fait part de son expérience pendant ces mois.

Mes remerciements s'adressent, aussi à M. KHERGAG Mohamed pour son soutien continu, sa disponibilité exceptionnelle et ses conseils avisés.

Je veux remercier mes parents pour tout ce qu'ils ont fait pour moi, pour leur amour et leurs encouragements.

2

Résumé

Dans ce travaille nous avons mis en claire le fondement théoriques de l'informatique quantique, nous avons exploré les modèles de calcul quantique, et nous allons choisit un analogue a ð - calcul qui est le q - calcul, pour l'approche compositionnelle, et qCCS comme algèbre de processus, la machine de Turing quantique comme modèle universel de calcul quantique. Après avoir donné les principes de base de l'informatique quantique, finalement nous allons explorer les langages de programmation quantique pour chaque paradigme. Ces explorations sont données à titre exhaustives et proposer une extension du langage LOTOS nommée Q-LOTOS.

Abstract

In this work we set clearly the theoretical basis of quantum computing, we explored the models of quantum computation, and we chose an analogue ð - calculus which is the q - calculus for the compositional approach, and qCCS as process algebra, the quantum Turing machine as a universal model of quantum computation. After giving the basic principles of quantum computing, we finally explore the quantum programming languages for each paradigm. These explorations are given as exhaustive and proposed an extension of the LOTOS langauge named Q-LOTOS.

Introduction générale

La rencontre entre la physique quantique et les sciences de l'information débute en 1982 quand Richard Feynman [Feynman, 1982] [Feynman, 1984], Prix Nobel de Physique, propose l'utilisation de la physique quantique au lieu de la physique classique comme support matériel de l'information et du calcul. Des problèmes hors de portée de l'informatique actuelle (dite classique) pourraient alors être traités efficacement.

Le calcul quantique est un domaine de recherche qui acquiert rapidement une place comme un sujet important dans l'informatique. Pour être sûr, il ya encore des problèmes conceptuels et technologiques à surmonter dans la construction d'ordinateurs quantiques fonctionnels. Néanmoins, il existe de nouveaux recherches fondamentales sur la calculabilité quantique [Deutsch, 1985], les algorithmes quantiques [Deutsch et Jozsa, 1992] [Grover, 1996] [Shor, 1997] , les protocoles de communication quantique [Bennett et Wiesner, 1992] et la nature de la mécanique quantique elle-même, en particulier avec l'émergence de la théorie de l'information quantique [Michael A, 2000]. Une grande partie du travail théorique vise à utiliser les nouveaux outils disponibles pour l'efficacité algorithmique. Ceux-ci sont donnés par des superpositions, qui se trouvent à la base du parallélisme quantique, l'intrication, qui permet d'atteindre tous les termes de superposition par des corrélations malgré l'effondrement de la mesure, et la linéarité des opérations quantiques. Cependant, le fait que les calculs quantiques sont décrits actuellement au niveau bas seulement - en comparaison avec l'informatique classique il ya 60 ans - c'est un aspect beaucoup moins explorée. Dans son état actuel, le calcul quantique peut à peine faire face à un nombre limité d'algorithmes isolés. Leurs auteurs se servent de leur connaissance intime des phénomènes quantiques susmentionnés pour faire une passerelle entre les niveaux d'abstraction physique et le monde conceptuel que nous sommes habitués au calcul classique. Les machines de Turing précèdent les ordinateurs classiques, l'analogue est vrai pour les ordinateurs quantiques. Les paradigmes de programmation classiques ont été développés quand la technologie informatique a été introduite. Notre objectif s'inscris dans le cadre d'anticiper la construction de dispositifs quantiques et de raisonner sur les concepts quantiques pour l'informatique.

3

Dans ce mémoire nous allons donner une synthèse des principes de base de l'informatique

4

Introduction générale

quantique, en mettant l'accent sur les fondements théoriques (modèles de calcul). Pour cette fin nous allons présenter dans une première section des préliminaires mathématiques et les postulats de la mécanique quantique ayant rapport avec le traitement de l'information (coté informatique), suivi par la représentation quantique de l'information en utilisant les principes suscitées. Dans la deuxième section nous allons présenter quelques algorithmes quantiques (les plus célèbres), puis quelques modèles de calcul quantique à savoir (la machine de Turing quantique, q-calcul et CCS quantique). Et dans la dernière section nous présentons les langages de programmation quantique à savoir (Quantum Computing Language, QML, Quipper).

Comme contribution nous allons proposer une extension du langage LOTOS basé sur ces concepts quantiques afin d'élargir l'utilisation du langage LOTOS aux processus quantiques. Finalement une conclusion générale et quelques perspectives.

CHAPITRE 1

PRÉLIMINAIRES

?

?????

?????

5

Dans ce chapitre nous présentons des notions mahtématiques et physiques qui servent l'éle-ments de base du reste de mémoire; à savoire les espaces de Hilbert et les postulas de la mécanique quantique.

1.1 Notions mathématiques et physiques 1.1.1 Notations mathématique

Espaces vectoriels

Définition 1. Un espace vectoriel est un triplet K = (E, +,
·) où :

- E ensemble de vecteurs.

- + : E × E -? E une loi d'addition qui est une application

-
· : K × E -? E une loi de multiplication par un scalaire

- (E, +) est un groupe abélien (associativité, commutativité, existence d'un élément neutre

et d'un opposé);

(ëu) u = (ëuu)

(ë + u)u = ëu + uu

.

ë(u + v) = ëu + ëv

1u = u

Définition 2. Une famille finie de vecteurs est une base de E si et seulement si :

- Elle est libre

- Elle engendre E

D'après cette définition, toute famille libre ? x1, ? x2,..., ? xkest une base du sous-espace vectoriel qu'elle engendre.

Définition 3. Un scalaire sur V est une application bilinéaire sur V , notée : (u, v)_V : V × V ? R et vérifiant les trois propriétés suivants :

6

chapitre1 : Préliminaires

1. Symétrique : V (u, v) E V, (u, v)_v = (v, u)_v

2. Positivité : Vu E V. (u, u)_v > 0

3. (u,u)_v = 0 <=> u = 0

pAvec (u, u)_v est une norme (norme induite). Espaces de Hilbert

Définition 4. un espace de Hilbert est un espace vectoriel muni d'un produit scalaire (donc normé), et complet pour la norme induite.

Complet i.e. toute suite de Cauchy est convergente.

Les espaces de Hilbert sont les espaces vectoriels de dimension finies les plus simples. Ils interviennent entre autres :

- dans l'étude des équations différentielles et aux dérivées partielles

- en mécanique classique (fréquences propres)

- en physique (équation de Schrodinger, mécanique quantique).

1.1.2 L'aspect physique (mécanique quantique) [Perdrix, 2006]

En va exploiter et illustrer les phénomènes de la mécanique quantique d'une vision d'un informaticien.

1.1.2.1 Postulat 1 : vecteur d'état et notation de Dirac :

`' Chaque système physique isolé est associé à un espace d'état (un espace de Hilbert séparable) `'

- H un espace de Hilbert.

- H est séparable si et seulement s'il admet une base dénombrable.

- H¹ la sphère unité de H / H¹ = {|0) E H/ Il|0)Il = 1} c.à.d. l'ensemble des états ou la norme de chacune est égale à 1.

- H=¹ la boule unité de H / H=¹ = {|0) E H/ Il|0)Il < 1} c.à.d. l'ensemble des états ou la norme de chacune est inférieur ou égale à 1.

7

chapitre1 : Préliminaires

Formalisme de Dirac

La notation bracket permet de représenter l'état du système par un vecteur normé |ø) prononcé

ket psi.

Les probabilités complexes d'amplitudes sont notées á et â , leur somme au carré vaut par

conséquent 1.

|ø) = á|0) + â|1).

(ø|ø⁰) le produit scalaire de |ø) et |ø⁰).

{|T),T E H} où B dénombrable - base orthonormée de H.

|ø) E H¹ on peut écrit :

>T?B áT.|T) avec _>T?B |áT|² = 1 (superposition, combinition linèiare).

Si |ø) = >T?B áT.|T) et |ø⁰) = >T?B âT.|T)

alors : (ø|ø⁰) = >T?B á^*_T
· âT où

á* représente le conjugué de á .

(ø| vecteur_' bra.

Si | '

/) = >T?B áT.|T) alors : (ø| = >T?B áT .(T |.

1.1.2.2 Postulat 2 : Système composé

"L'espace des états d'un système composé de sous-systèmes est le produit tensoriel des espaces des états des sous-systèmes".

Définition 5. Rolland, 2006] Soient E et F deux espaces vectoriels sur le même corps K. On note [E x F] l'espace vectoriel sur K des combinaisons linéaires formelles d'éléments du produit [E x F]. Plus précisément :

[E x F] = >( x, y) E Aë(x, y) (x, y) à partir de [E x F], ë(x, y) E K

On note G le sous-espace vectoriel de [E x F₍] engendré par les éléments de la forme : (x?A1 ^ëxx, _>y?A2 ^uyy)- >x,y?A1×A2 ëxuy (x, y).

Donc E ®K F = [E x F] /G

L'espace vectoriel E ®K F est appelé le produit tensoriel de E par F sur le corps K.

H¹_B1Espace d'état d'un système S1.

H¹_B2Espace d'état d'un système S2.

Donc l'espace d'états du S composé de S1 et S2 est :

H1B1 ® H1B2 ~= H1B1×B2.

Si |ø1) E H¹_B1 et |ø2) E H¹_B2 alors S est dons |ø1) ® |ø2) = |ø1) |ø2) = |ø1ø2) .

8

chapitre1 : Préliminaires

Il y a des cas ou un état d'un système composé de deux sous-systèmes ne peut pas être décomposé en un produit tensoriel de la forme |ø1i ? |ø2i tel que |ø1i est l'état du premier sous-système et |ø2i est l'état du second.

Etats non séparable : états intriquées.

L'intrication est l'essence de la physique quantique (Schrodinger,1935)

L'intrication quantique est un phénomène fondamental de la mécanique quantique mis en évidence par Einstein et Schrodinger dans les années 30. Deux systèmes physiques, comme deux particules, se retrouvent alors dans un état quantique dans lequel ils ne forment plus qu'un seul système dans un certain sens subtil.

Toute mesure sur l'un des systèmes affecte l'autre, et ce, quelle que soit la distance les sé-

parant. Avant l'intrication, deux systèmes physiques sans interactions sont dans des états quan-

tiques indépendants mais après l'intrication ces deux états sont en quelque sorte « emmêlés » et

il n'est plus possible de décrire ces deux systèmes de façon indépendante.

Par exemple : L'état |B0i = 1 _v2(|00i + |11i) ? H{0,1} ? H{0,1} est intriqué. En effet pour tout a,

b, c, d ? C :

|B0i = (a |0i + b |1i) ? (c |0i + d |1i) = ac |00i + ad |01i + bc |10i + bd |11i .

On en déduit que

ad = 0 or a =60 car ac = 1 et d =60 car bd = 1.

Donc |B0i est un état intriqué.

Cet état |B0i est appelé état EPR (paradoxe d'Einstein-Podolski-Rosen).

`'Le paradoxe EPR, ou paradoxe d'Einstein-Podolski-Rosen, était à l'origine une expérience de pensée proposée par Einstein et ses collaborateurs en 1935 pour violer les inégalités position-impulsion de Heisenberg et démontrer que l'interprétation probabiliste de la mécanique quantique ne pouvait être qu'effective.

L'emploi de probabilités devant être un expédient provisoire reflétant l'absence de connaissances complètes des valeurs de certains paramètres déterminant le comportement individuel des particules, tout comme en théorie cinétique des gaz avec la distribution de Maxwell. Repris sous une forme différente en liaison avec le spin des photons par David Bohm, cette expérience a pu être réalisée ultérieurement par Alain Aspect en 1982. Entre-temps, le théoricien Irlandais John Bell avait démontré ses célèbres inégalités permettant de savoir qui d'Einstein ou des fondateurs de la mécanique quantique avaient raison.

Les résultats de cet aspect, et d'autres, ont toujours confirmé l'interprétation standard de la mécanique quantique, montrant de plus que la notion de non-localité (qu'en 1964 John Bell a

9

chapitre1 : Préliminaires

montré que la seule conclusion possible de l'analyse d'Einstein, Podolski et Rosen est que le monde est non local.) est un élément central de la mécanique quantique».

1.1.2.3 Postulat 3 : Evolution quantique:

"Tout système quantique évolue selon une transformation admissible."

Une transformation admissible agissant de H dans K est une famille dénombrable (Mi)(iEA) d'opérateurs linéaires de H dans K, vérifiant la condition de complétude:

>-iEA M† i = IdH

où IdH est l'identité sur H.

Si une transformation admissible _(Mi)(iEA) est appliquée à |ø) ? H¹, alors avec une probabilité p(i) = hø|M† _i Mi|øi, le résultat classique i est observé et l'état du système après la transformation est :

v(ø|M^†

Mi|ø) i Mi|ø)

Les postulats sont une véritable pierre angulaire de la mécanique quantique. Ils sont également le fondement de l'informatique quantique. Leur présentation a permis de mettre en évidence de propriétés spécifiques telles que les phénomènes de superposition et d'intrication.

CHAPITRE 2

INFORMATION, DONNÉE QUANTIQUE

Dans cette section nous allons essayer de répondre à ces questions :

- Comment représenter l'information quantique ?

- Comment manipuler cette information ?

2.1 Les nombres quantiques :

Si tous les électrons d'un atome ont même masse et même charge, ils ne jouent pas tous le même rôle. Ils ne sont donc pas, de ce fait, rigoureusement identiques. Tout électron, dans un nuage électronique, est caractérisé par ses nombres quantiques. Tout électron est caractérisé par 4 nombres quantiques.

n : le niveau d'énergie de l'électron dans l'atome.

l : les sous-couches électroniques.

m : l'orientation de l'orbitale atomique.

s : le spin, la rotation de l'électron sur lui-même

FIGURE 2.1 - Nombers quantique

10

11

chapitre2 : Information, donnée quantique

FIGURE 2.2 - rotation d'électron sur lui-même

Physiquement, les états d'un spin d'un électron, les états de polarisation d'un photon ou encore les niveaux d'énergie d'un atome sont utilisés pour représenter les états d'un qubit.

2.2 Les circuits quantiques :

Les circuits quantiques, encore largement utilisés pour décrire les algorithmes quantiques malgré leur limitation en termes d'expressivité, sont une généralisation des circuits booléens. La brique de base de l'information est donc une généralisation quantique du bit, le qubit.

2.2.1 Qubit

On nomme qubit (quantum + bit ; prononcer kiou-bite) l'état quantique qui représente l'unité de stockage d'information quantique [Perdrix, 2006]. Il se compose d'une superposition de deux états de base, par convention notés|0) et |1). Un état qu-bit est constitué d'une superposition quantique linéaire de ces deux états. Une mémoire à qubits diffère significativement d'une mémoire classique par le fait qu'un bit ne peut prendre que les valeurs 0 et 1, et une seule à la fois. Un qubit n'a pas cette restriction.

Formellement, un qubit correspond à un vecteur d'état dans un espace d'Hilbert.

{|0) ,|1)} base de calcule (orthogonale).

|0) = á |0) + 0' |1) avec á, 0' E C tel que :

|á|² + |0'|² = 1

Qubit : se trouve dans une combinaison linéaire qui est : |0) = á |0) + 0' |1) donc le qubit se trouve soit dans l'état 0 soit dans l'état 1, soit dans une superposition mais le nombre des états

chapitre2 : Information, donnée quantique

superposées est infini.

2.2.2 Sphère de Bloch

La sphère de Bloch [Perdrix, 2006] est une représentation géométrique d'états d'un qubit

comme des points sur la surface d'une sphère unité. De nombreuses opérations sur les bits

quantiques simples qui sont couramment utilisés dans le traitement de l'information quantique

peuvent être décrites parfaitement dans la sphère de Bloch. [Glendinning, 2005]

á ² + â 2 = z ² + x + iy 2 = z² + x² + y² = 1 est une équation d'une sphère dans l'espace R³.

r = 1

Coordonnées cartésiennes en coordonnées sphériques :

x = sin è cos ö, y = sin è sin ö, z = cos è

ø) = z 0) + (x + iy) 1)

ø) = cosè 0) + (sinè cos ö + isinè sin ö) 1)

ø) = cos è 0) + sinè (cosèisin ö) = cos è 0) + sinè expiö 1)

è : La colatitude et ö : Longitude

0) : Le pole nord et 1) : Le pole sud

12

FIGURE 2.3 - Sphère de Bloch

13

chapitre2 : Information, donnée quantique

2.2.3 Mesure d'un qubit

" Déterminer la quantité d'information contenue dans un qubit»

Un qubit dans l'état |ø) = á |0) + â |1) est mesuré dans l'état 0 avec probabilité |á|² et dans l'état 1 avec probabilité |â|².

2.2.4 Registre quantique

Un registre quantique [Perdrix, 2006] est l'analogue de la mécanique quantique d'un registre du processeur classique. Une description mathématique d'un registre quantique est obtenu en utilisant le produit tensoriel de qubit bra et vecteur ket. Par exemple, un registre quantique de n qubit est décrit par l'élément.

|ø) = |ø1) ® |ø2) ® ... ® |ø_n) dans le produit tensoriel de l'espace de Hilbert.

L'état d'un registre de n qubits est un vecteur dans un espace à 2n dimensions dont une base est :

|00...0) c.à.d. |0) |00...1) c.à.d. |1)

|00...2) c.à.d. |2) ...

|11...1) c.à.d. |2ⁿ - 1)

Il s'écrit donc :

|ø) = á0 |0) + á1 |1) + á2 |2) + ... + á2n-1 |2ⁿ - 1)

avec |á1|² + |á2|² + ... + |á2n-1|² = 1

2.2.5 Porte quantique »L'évolution après mesure»

La porte quantique décrite le passage d'un état quantique à un autre De même que l'on peut formaliser le calcul classique à l'aide des portes logiques habituelles - par exemple NOT et AND, le calcul quantique peut être défini par des circuits, les opérations élémentaires consistant à appliquer une porte parmi un ensemble de base choisi à l'avance, au bon endroit et au bon moment.

14

chapitre2 : Information, donnée quantique

2.2.5.1 portes à un qubit (opérations unitaires sur un seul qubit)

0 1

PAHSE (è) =

Les portes quantiques à un qubit [Lacour, 2007] [Gradel, 0910]peuvent être représentées sur la sphère de Bloch par des rotations autour d'un vecteur de la sphère. Elles peuvent donc toutes être obtenues par la combinaison de deux familles de portes quantiques : les portes PAHSE effectuant des rotations autour de l'axe z, et les portes ROTATION effectuant des rotations autour de l'axe y. Les portes PAHSE modifient la phase relative du qubit. Elles s'écrivent dans la base {|0) ,|1)}.

_eöavec la matrice de Pouli o_x = 1 0 Les portes PAHSE ajoutent

0 0 -1

donc une phase 0 à l'état |1) du qubit, sans modifier l'état |0). Les portes ROTATION changent les poids de la superposition d'états du qubit. Elles s'écrivent dans la base {|0) ,|1)}

cos á - sin á PAHSE (á) = siná cos á

!avec la matrice de Pouli oy =

Ces deux familles de

0 -i !

i 0

portes quantiques, PHASE et ROTATION, permettent en les combinant d'obtenir toutes les

autres portes à un qubit. Parmi les autres portes à un qubit usuelles, citons la porte Hadamard, correspondant à la combinaison ROTATION(ir/4 #177; PAHSE (ir)), et s'écrivant dans la base

{|0) , |1)} :

!

1 1 1

H=v2 1 -1

Remarque :

H=¹_v2(o_x+o_z)etH²=1

o_x - If_ð ; Ifð/2 ^et _Ifð/4 sont également utiles ; o_y s'obtient en combinant o_x et o_z (o_y = io_xo_z)

2.2.5.2 Portes logiques à deux qubits)

Ces portes réalisent l'opération logique élémentaire « si A est vrai, alors faire B .... ».

15

chapitre2 : Information, donnée quantique

Porte générale «control-U» : U appliqué au qubit cible si le qubit source vaut 1 et cible non changée si la source vaut 0. Source toujours invariante. Cas particulier important : U = o_x Porte C-NOT (bascule conditionnelle)

On peut aussi conditionner l'évolution de la cible à la valeur 0 de la source:

La cible n'évolue que si la source vaut initialement 0 (effet de la première porte o_x). La source revient finalement dans l'état initial (deuxième porte o_x)

Remarque :

- La porte C-NOT peut être réalisée avec une porte de phase-ð et deux Hadamard: - Toute porte «control-U» peut se décomposer en portes C-NOT et portes à un qubit.

- La porte à deux qubits est nécessaire afin de créer de l'intrication.

2.2.5.3 Portes à plus de deux qubits)

Porte unitaire à n qubits peut être engendrée par le produit tensoriel et la composition de certains sous-ensembles de portes à 1 et à 2 qubits.

chapitre2 : Information, donnée quantique

16

FIGURE 2.4 - Decomposition de la porte quantique CNOT

- Porte de Toffoli

Tout d'abord, il serait satisfaisant qu'un ordinateur quantique ait une puissance de calcul au moins aussi importante qu'un ordinateur classique. Pour cela, une porte quantique particulière, appelée porte de Toffoli [Monerau, 2008], qui permet d'obtenir une version quantique du NAND et de la bifurcation dans un circuit. Ainsi, on aura récupéré au moins la puissance de calcul d'un ordinateur classique. La porte de Toffoli s'applique à 3 qubits en entrée (a, b, c) et produit 3 qubits en sortie (a', b', c'). Son action est simple :

Si les deux premiers qubits sont dans l'état 1), elle remplace la valeur du troisième qubit par son complémentaire. Pour fixer les idées, donnons sa table de vérité dans la base de calcul (les 0 et 1 représentent les états 0) et 1) pour plus de clarté) :

Entrées

Sorties

a	b	c	a'	b'		c'	0
0	0	0	0	0		0
0	1	0	0	1		0
1	1	0	1	1		0
1	0	0	1	0		1
0	0	1	0	0		1
0	1	1	0	1		1
1	1	1	1	0		1
1	0	1	1	1

TABLE 2.1 - Table de vérité de porte logique universelle réversible de Toffoli.

Cette table donne la valeur de la porte appliquée aux vecteurs de base de (C²)^®3, et elle caractérise donc bien l'opérateur unitaire sous-jacent. à partir de cette porte quantique, on voit qu'on obtient les opérations «génératrices» du calcul logique classique : NAND et la bifurcation. En effet, si on fixe c = 1), alors c' = NAND(a, b)). De même, si on fixe a = 1) et c = 0), alors b' = c' = b, et on a donc dupliqué b. Mais si un ordinateur quantique peut bien simuler

17

chapitre2 : Information, donnée quantique

un ordinateur classique, il présente bien sûr une puissance de calcul beaucoup plus importante. Tout est dans les états dits «d'intrication» des n-qubits. En effet, comme les n-qubits peuvent être des combinaisons linéaires d'éléments de la base, on peut y stocker plus d'information que si on pouvait simplement se placer sur des vecteurs de la base (comme on le ferait si l'ordinateur était classique).

Malheureusement, les mesures ne renvoient qu'un vecteur de la base, ce qui exclut de mesurer exactement un état intriqué et d'en obtenir les différentes composantes sur chaque vecteur de la base de calcul.

Cependant, comme on va le voir dans les algorithmes quantiques qui suivent, on peut tout de même utiliser cette latitude de calcul pour accélérer des algorithmes classiques.

- Porte CNOT

La porte de Toffoli nous a permis de simuler de manière quantique la logique de NAND. Maintenant, nous allons imiter son caractère «générateur». En effet, on dispose d'une porte de base qui a un rôle analogue à NAND, dans le cas classique dans le sens où elle est universelle parmi les opérateurs unitaires. Elle prend en entrée 2 qubits. Le premier est dit de contrôle, le second est la cible. Son action peut être décrite simplement : si le qubit de contrôle vaut 0), le qubit cible reste tel quel; mais si le qubit de contrôle vaut 1), alors le qubit cible est changé en son complémentaire. Sa table de vérité est donc :

Entrées

Sorties

a	b	a'		b'	0
0	0	0		0
1	0	1		1
0	1	1		1
1	1	0

TABLE 2.2 - Table de vérité de porte logique universelle réversible de CNOT.

Et on nomme cette porte CNOT (Controlled-NOT). CNOT [Monerau, 2008] présente une propriété algébrique intéressante :

Proposition (Universalité de CNOT et des portes sur 1-qubit)

à partir de CNOT et des portes quantiques agissant sur un 1-qubit, on peut créer par composition n'importe quelle porte quantique agissant sur un n-qubit (c'est-à-dire obtenir n'importe quel opérateur unitaire de (C²)^?n).

18

chapitre2 : Information, donnée quantique

2.3 Complexité d'un algorithme quantique:

On parle «d'accélérer des algorithmes classiques», mais encore faut-il se donner un moyen de mesurer effectivement la complexité d'un algorithme quantique. Rappelons que dans le cas d'un algorithme classique, la complexité mesure en temps : on estime le temps mis par l'algorithme sur une entrée de taille n, asymptotiquement. Cela revient à compter le nombre d'opérations «atomiques» réalisées au cours d'une exécution. Les algorithmes polynômiaux en n sont considérés comme étant utilisables en pratique, alors que les exponentiels mettraient beaucoup trop de temps sur des entrées, même petites, pour être utiles.

Sur un ordinateur quantique, on mesure de même le temps d'exécution. On va utiliser le résultat de de la proposition d'universalité : on considère que l'application de CNOT ou d'un opérateur agissant sur un 1-qubit se fait en temps constant. Une mesure prend également un temps constant. Ainsi, lorsqu'on dispose d'un circuit quantique, on établit sa complexité en décomposant chaque opérateur en CNOT et en opérations de 1-qubit, puis on compte. Dans toute la suite, les opérateurs agissant sur les n-qubits se décomposent en un nombre polynômial en n de portes de base. Ainsi, compter un nombre polynômial de ces portes quantiques ou des portes de base est équivalent. On ne se souciera donc plus de ce détail de définition, et on comptera directement les opérateurs agissant sur des n-qubits. L'aspect pratique des algorithmes polynômiaux à opposer aux exponentiels reste évidemment le même : un algorithme polynômial serait assez rapide si un ordinateur quantique l'exécutait, alors qu'un exponentiel serait trop long sur des entrées de taille usuelle.

Conclusion

Dans ce chapitre nous avons vu la représentation des données quantique et comment on les manipule avec les portes quantiques en fin on a vu la complexité des algorithmes quantiques.

CHAPITRE 3

LES ALGORITHMES QUANTIQUES

19

3.1 introduction :

Depuis le milieu des années 90 jusqu'à présent l'effort principal a été porté à trouver des algorithmes quantiques avec une performance meilleure que celle des algorithmes classiques. L'algorithme quantique le plus important est l'algorithme de Shor. L'importance de cet algorithme est qu'il indique que la machine quantique peut être plus fondamentale que la machine classique. Cet algorithme permet de résoudre en un temps polynomial un problème que la machine classique n'a encore pu résoudre qu'avec un temps exponentiel. D'autres raisons qui ont contribué à faire de cet algorithme un algorithme très connu est d'une part que le problème mathématique est simple à comprendre, le problème de factorisation, et d'autre part que la solution de ce problème a des implications importantes dans d'autres domaines comme la cryptographie. Un autre algorithme important est celui de Grover, ou algorithme de tri, nous allons présenter cet algorithme plus en détail dans ce chapitre. L'algorithme classique décrivant le même problème cependant n'est que quadratiquement supérieur en temps que l'algorithme de Grover. Les applications de cet algorithme, comme par exemple l'algorithme d'estimation d'amplitude auront le même type de gain en temps par rapport à l'algorithme classique 'équivalent. Finalement, dans les dernières années quelques algorithmes utilisant comme base les marches quantiques ont 'été construits.

3.2 Les problèmes posés sous forme d'une boite noire :

Les problèmes logiques lesquelles considérer ici [Haroche, 2002] sont posés sous forme d ' «oracle». On suppose qu'une machine programmée selon des règles inconnues (décrite comme une «boîte noire» ou oracle), calcule une fonction dont nous ne connaissons que certaines caractéristiques. Le problème consiste à déterminer une propriété inconnue de la fonction, sans «ouvrir» la boite. Nous pouvons interroger l'oracle en entrant des données dans la boite et en manipulant sa sortie, sans l'ouvrir pour en analyser le contenu. La figure suivante illustre cette notion.Le problème sera «facile» si sa résolution demande un nombre total d'opérations croissant

chapitre3 : Les algorithmes quantiques

de façon polynomiale avec le nombre de bits, «difficile» s'il croit de façon exponentielle avec ce nombre.

A ce point, le passage du calcul classique au calcul quantique transforme certains oracles classiques difficiles en oracles quantiques faciles. Dans d'autres cas, le problème quantique reste difficile, mais moins que le problème classique (croissance toujours exponentielle du nombre d'opérations, mais avec un exposant plus petit que classiquement).

20

FIGURE 3.1 - représentation par oracle.

3.2.1 Exemples d'oracles classiquement difficiles

- L'oracle de Deutsch-Josza

f(x) est une fonction booléenne de [0, 2^7-1] dans [0, 1]. On sait qu'elle est soit constante, soit balancée. Est-elle l'un ou l'autre?

Classiquement, il faut interroger l'oracle 2^7-1 + 1 fois pour répondre à la question à coup sûr (il faut introduire 2^7-1 + 1 valeurs différentes de x et calculer f(x) à chaque fois). Croissance exponentielle avec n du nombre d'opérations est problème classique difficile.

- L'oracle de Grover

f(x) est une fonction booléenne de [0, 2^7-1] dans [0, 1] qui n'est non nulle que pour x = x0. Trouver x0.

chapitre3 : Les algorithmes quantiques

Equivaut à la recherche inversée d'un abonné dans un annuaire à partir de son numéro connu a. Les x sont les abonnés, f(x) vaut 1 si a est le numéro de x, 0 sinon.

Classiquement, il faut calculer f(x) (consulter l'annuaire) N = 2^n_1 fois pour trouver à coup sûr. Problème classique difficile.

- L'oracle de Simon

f(x) est une fonction de [0, 2^n_1] dans [0, 2^n_1] telle que :

f(x') = f(x) ssi x = x s où s est une suite inconnue à n termes de 0 et 1 et représente l'addition bit à bit (s : période de f). Déterminer s.

Classiquement, il faut calculer f(x) pour des valeurs aléatoires de xjusqu'à trouver deux x et x' tels que f(x) = f(x').

Alors x s = x' et x x' = x x s = s (car x x = 0). Il faut 2^n_1 + 1 opérations pour trouver la réponse à coup sûr. Problème classique difficile.

3.3 L'Algorithme quantique de Deutsch-Josza:

FIGURE 3.2 - L'oracle de Deutsch-Josza

21

22

chapitre3 : Les algorithmes quantiques

Le registre d'entrée A (n qubits) est préparé (par application de la transformation de Hadamard H sur chaque qubit) dans la superposition symétrique des 2ⁿ états |xi possibles.

Le registre de sortie B (1 qubit) est inversé par N, puis préparé par H dans ^1v2 (|0i - |1i) Action d'oracle : [Gradel, 0910] |xi |0i ? |xi |f(x)i et |xi |1i ? |xi |1 ? f(x)i

Si f(x) = 0 : |xi (|0i - |1i) ? |xi (|0i - |1i)
Si f(x) = 1 : |xi (|0i - |1i) ? - |xi (|0i - |1i)

donc : (-1)^f(x) |xi (|0i - |1i)

Et par superposition :

1
n+1

2 2

Ex |xi ₍|0i - |1i) ? 2 21 Ex ₍-1)^f(x) |xi ₍|0i - |1i)

Les registres restent non intriqués après l'oracle. Déphasage des amplitudes dans le registre A en (-1)^f(x). Pour résoudre le problème, il s'agit de décider entre deux possibilités :

- Si f(x) est constante :

f(x) = 0?x ou f(x) = 1?x donc 2n Ex (-1)^f(x) |xi = #177;22 ^Ex |xi alors registre A inchangé (au signe prés).

- Si f(x) est balancé :

Autant de f(x) = 0 que de f(x) = 1 donc autant d'amplitude +1 que d'amplitude -1 dans la superposition finale du registre A

? Ex (-1)^f(x) |xi orthogonal à ^Ex |xi.

Résoudre l'oracle revient à distinguer deux états orthogonaux de l'état final du registre A : On applique à nouveau H à tous les qubits. Comme H² = 1, on retrouve l'état initial {|0i} si f(x) est constante, un état orthogonal si f(x) est balancée donc au moins un des qubits doit alors être 1. On le vérifie en mesurant les qubits finals de A.

La réponse nécessite au plus 3n + 2 opérations à un qubit 2n + 1 opérations H, une opération de bascule N et au plus mesure de n qubits (on peut arrêter dès qu'on trouve un 1) donc problème quantiquement facile.

23

chapitre3 : Les algorithmes quantiques

- Comparaison avec la procédure classique

L'avantage de l'algorithme quantique n'existe que si on cherche une réponse certaine. Si on s'autorise une probabilité finie c d'erreur, aussi petite soit-elle, l'algorithme classique (calcul successif de f(x) pour des valeurs de x tirées au hasard) donne un résultat acceptable au bout de k ^_' -log2(c) opérations (nombre indépendant de n). Le problème classique devient donc facile dès qu'on accepte un taux fini d'erreur. Ceci diminue considérablement l'intérêt de l'algorithme quantique puisqu' il faut être sûr de pouvoir l'effectuer sans aucune décohérence pour qu'il soit avantageux par rapport à la version classique.

3.4 Algorithme de recherche quantique (Grover) :

Le problème [Jorrand, 2005] commence comme celui de Deutsch-Josza. La fonction Booléenne de [0, 2^n-h] dans [0, 1] est réalisée par un oracle agissant sur la superposition symétrique des N = 2ⁿ qubits de A et sur le qubit B préparé par les opérations N et H dans l'état ^v2h (|0) - |1)).

FIGURE 3.3 - Algorithme de recherche quantique (Grover)

Revient à inverser l'amplitude de l'élément x = x0 dans la superposition des états de la base {x} sans toucher aux autres. Comment détecter l'élément dont l'amplitude a été inversé? On applique au registre A, après l'opération de l'oracle O(x0), l'opérateur unitaire Us = 2|s)(s|- 1 où |s)(s| est le projecteur sur la superposition symétrique de tous les états de la base x de A |s)=(_v^h_N)E_x|x).

L'action de Us sur une superposition quelconque |0) = Ex á_x|x) revient à symétriser les amplitudes de |0) par rapport à leur moyenne. De la relation (s|0) = ( iN) Ex á_x = (á)./N où (á) est la moyenne des amplitudes de l'état |0), on déduit en effet :

Us|0) = 2|s)(s|0) - |0) = Ex 2((a) - á_x)|x) = Ex bx|x)

Avec : á.+b.

(a)

2 =

- Illustration de l'algorithme de recherche quantique dans le cas n = 4(N = 16)
On applique l'oracle O(x0) sur |s), puis Us , et on itère les deux opérations. L'effet de O(x0) est
d'abaisser à chaque fois la valeur moyenne (a) (ligne horizontale rouge). L'opération de symétrie

L'état final de A est donc : ( ¹n+1

2

%y [(-1 + ^{(-1)E.i(xi?s)yii} |y1, y2, ..., y_ni

2

24

chapitre3 : Les algorithmes quantiques

par rapport à cette moyenne (Us) réduit le fond et fait ressortir la valeur marquée par l'oracle. Au bout de trois itérations, le fond devient très petit.

On mesure alors le registre A (4 qubits) et on trouve avec une probabilité de 0.96 la valeur x0 = 5 choisie par l'oracle. Il faut savoir quand arrêter la procédure (si on va trop loin, le fond augmente en valeur absolue en devenant négatif). L'itération demande un nombre d'opérations

v

croissant comme N [Gradel, 0910].

FIGURE 3.4 - Exemple de recherche quantique

3.5 L'Algorithme de Simon [Haroche, 2002]

On réalise la suite d'opérations schématisée ci-dessus : calcul parallèle de toutes les valeurs de la fonction suivie d'une mesure du registre B projetant A dans une superposition de deux états qui diffèrent bit à bit de la quantité inconnue s. On applique alors à nouveau les transformations de Hadamard aux n qubits de A : elles font évoluer chaque qubit suivant la loi :

|0i ? ¹_v2 (|0i +|1i) et |1i ? ¹_v2 (|0i-|1i) .Un état |xi (produit de n états |xii avec xi = 0 ou xi = 1) devient une superposition de produits d'états |yii avec yi = 0 ou yi = 1. Les coefficients de cette_e superposition valent + 1 ou - 1 suivant la parité de la somme %i xiyi :

{|xi_I = |x1, x2, ...x_ni ?2 21) %y (-1)E.i ^xiyi |y1, y2, ..., y_ni

25

chapitre3 : Les algorithmes quantiques

( ₁ ) P

= 2 n+' y

2

FIGURE 3.5 - L'Algorithme de Simon

> >

i xiyi h i xisiyii

(-1) 1 + (-1) |y1, y2, ...,y_ni

Une mesure répétée n fois de A va alors nous permettre de déterminer s. - Détermination de la période inconnue s

) P > >

( ₁ i xiyi _{h i}

|ø(final)i_A = y (-1) 1 + (-1) i xisiyi |y1, y2, ..., y_ni

2 n+'

L'amplitude (-1) non nulle ssi P

2

i siyi = 0 (modulo 2)

Une mesure des qubits individuels donne une suite y1a, y2a, . . . _yna de valeurs 0 et 1 qui satisfait la condition: Pi siyi = 0(modulo 2)

On recommence n fois l'opération et on obtient ainsi, en général, n relations indépendantes (si par hasard deux mesures donnent le même vecteur, on recommence une fois de plus) :

_P

i siyia = 0

_P

i siyib = 0

.

..

_P

i siyin = 0

La résolution de ce système d'équations donne s. Le processus requiert 4n² opérations. Le problème est donc quantiquement facile. De plus, il tolère des erreurs puisqu'on peut toujours vérifier le résultat en comparant f(x) et f(x ? s) une fois s obtenu.

- Rôle de l'intrication et de la mesure dans l'algorithme de Simon

Dans l'algorithme de Simon [Haroche, 2002], l'intrication et la mesure projective jouent un rôle plus essentiel que dans ceux de Deutsch et Grover. L'oracle intrique les registres A et B, puis la mesure de B projette A dans une superposition de deux états seulement. Après mélange par la lame séparatrice, la signature du signal d'interférence final nous renseigne sur la séparation de ces deux états, donc sur la période cherchée. Quoique mathématiquement plus compliqué, l'algorithme de Shor, basé sur la recherche de la période d'une fonction, ressemble beaucoup dans son principe à celui de Simon.

26

chapitre3 : Les algorithmes quantiques

FIGURE 3.6 - Rôle de l'intrication et de la mesure dans l'algorithme de Simon

Remarque : il n'est même pas besoin de lire la mesure du registre B. Il suffit d'avoir intriqué B à son appareil de mesure, ce qui réduit A à un mélange statistique de superpositions |x) + x s) Leur recombinaison finale par H1, H2, . . . , H_n ne conduit, quel que soit x, à une interférence constructive que pour les états y1, y2, ..., y_n) satisfaisant les équations linéaires de la page précédente (on peut réduire le nombre d'opérations à 3m²).

3.6 Algorithme quantique de Shor [Jorrand, 2012]

- La factorisation des entiers

Le nombre d'opérations nécessaires au meilleur algorithme classique actuellement connu pour factoriser un entier est exponentiel en la taille (nombre de chiffres) du nombre à factoriser : de l'ordre de e1551/3 pour RSA-155.

Le nombre d'opérations nécessaires à l'algorithme quantique de Peter Shor (1994) pour factoriser un entier est polynomial en la taille du nombre à factoriser : de l'ordre de1553 pour RSA-155. picture

chapitre3 : Les algorithmes quantiques

- Algorithme de Shor pour factoriser P E N

Début

Choisir a au hasard, 1 < a < P

Si PGCD(a, P) = 1, continuer. Sinon, le problème est résolu!

Trouver la période r de f_a(k) = a^k mod P.

On a alors : a^r = 1 mod P.

Si r est pair, alors (ar/2 + 1) (ar/2 - 1) = 0 mod P.

Si r est aussi tel que a^r/² =6 1 mod P, alors :

PGCD (ar/2 + 1, P) et PGCD (ar/2 - 1, P) sont des facteurs de P : stop!

Sinon, retourner au pas 1.

Fin

- P=15, Pour voir fonctionner cet algorithme

On choisit a au hasard, 1 < a < P : a = 7

PGCD(a, P) = PGCD(7, 15) = 1 : on continue.

f_a(k) = 7^k mod 15 :

« !On voit !» que r = 4 est pair et a^r/² = 72 = 49 = 4 mod 15 =6 1 mod P

PGCD (ar 2 + 1, P) = PGCD(50, 15) = 5

PGCD (ar 2 - 1, P) = PGCD(48, 15) = 3

Stop!

k	0	1	2	3	4	5	6	7	8	9	10	11	12	13	...
fá(k)	1	7	4	13	1	7	4	13	1	7	4	13	1	7	...

- Rappel : superposer 2ⁿ valeurs dans n qubit Etat initial : un registre de n qubits dans l'état 00...0)

27

FIGURE 3.7 - Superposition des 2ⁿ valeurs dans n qubit

chapitre3 : Les algorithmes quantiques

Rsultat :2 valeurs, uniformément superposées dans le même registre de n qubits, obtenues avec seulement n opérations.

- Tirer parti de l'intrication

FIGURE 3.8 - L'intrication

Si la mesure du deuxième registre retourne la valeur y0, alors le premier registre contient tous les x E f^-1 (y0)

- Si f est une fonction périodique, de période r

Soit y0 la valeur de f(x) pour un certain x, soit x0 le plus petit des x pour lesquels f(x) = y0, alors : f^-1 (y0) = {x0, x0 + r, x0 + 2r, ..., x0 + kr, ...}

FIGURE 3.9 - Utilisation de la période r

- Trouver la période r d'une fonction f : ZN -+ ZP

Pour trouver r : par calcul classique, N = 2 calculs de f. par calcul quantique, combien de calculs de f ?

Premier calcul de f -+ 1^er registre après mesure du 2^me registre :

37.png

Deuxieme calcul de f -+ 1^er registre après mesure du 2^me registre :

28

29

chapitre3 : Les algorithmes quantiques

38.png

- Solution : Transformée de Fourier Discrète

- Combien de calcul de f pour trouver r ?

FIGURE 3.10 - Comment trouver r?

- Espérance de logN = n itérations pour trouver r

- Mais ... DFTN est exponentielle : N² = 2²ⁿ multiplications à chaque itération!

chapitre3 : Les algorithmes quantiques

- DFTN est un produit tensoriel de n termes

- Vers une Transformée de Fourier Quantique

FIGURE 3.11 - Transformée de Fourier Quantique

30

31

chapitre3 : Les algorithmes quantiques

- Complexité de l'algorithme de Shor

- O(m) itérations pour trouver r

- O(m²) opérations pour calculer QFTN

- L'algorithme de Shor est en O(m³).[PHJ3 06]

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 q_o identifié et l'état final qf =6 q_o

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 q_o 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, T_x, 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 T_x ? : 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|² 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

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 H_q, q E K tel que pour toute définition de processus q = > i[ai].qi de R, chaque ai est une action de H_q dans _Hqi . De plus, une condition de complétude ^>i a i = IdH_q 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 = H_q = Hf = H0,1 et R :

i = [|0ih0|].f + [|1ih1|].q
q = [|+ih+|, |-ih-|].i

avec: |+i= v2 1 (|0i+ |1i)et |-i=_v2 ¹(|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.

4.3 Sémantiques dénotationnelles

PERDRIX dans [Perdrix, 2006] présente trois sémantique dénotationnelle qui sont Sémantique observable, Sémantique admissible et une Sémantique pure. On va voire la sémantique pure.

37

chapitre4 : Modèles de calcul quantique

4.3.1 Sémantique pure :[|.|]

Associée a chaque q-terme une fonction agissant sur des distributions probabiliste.

V (x) : L'ensemble des évolutions discrètes V sur l'ensemble X V =¹(x) : L'ensemble des évolutions vérifiant V (x) = 1.

Soit P un q-terme P = (K, I, F, R) et R :

?q de H dans H^', [|a|] : H ? V =1(H')

est [|M|] = ë|ö)(ö|M†M|ö).ç M|öi

vhö|M M|öi

[|M|] Est définie même pour |ö) tant que (ö|M†M|ö) = 0 par [|M|](|ö)) = 0 ?q E F, [|q|] : H1 q ? V =¹(SF) Est [|q|] = ë|öi.ç(q,|öi)

?q E F, [|q|] Fonction continue.

4.4 qCCS

4.4.1 Introduction

Une algèbre q-CCS [YING et al., 2003] des processus quantiques purs dans laquelle les communications en déplaçant physiquement états quantiques sont autorisées et les calculs sont modélisés par des super-opérateurs, mais aucune donnée classique est explicitement concernée. Une sémantique opérationnelle de q-CCS est présentée en termes de systèmes de transitions étiquetées (non probabiliste). La bisimulation forte entre les processus modélisés dans q-CCS est définie, et de ses propriétés fondamentales algébriques sont établis, y compris unicité des solutions d'équa-tions récursives. Pour modéliser calcul séquentiel dans q-CCS, un rapport de réduction entre les processus est défini. En combinant ce qui concerne la réduction et la bisimulation forte, nous introduisons la notion de réduction-bisimulation forte, qui est un dispositif d'observation de l'interaction de calcul et de communication dans les systèmes quantiques. Enfin, la notion de bisimulation forte approximative et son homologue de réduction sont introduits. Il est prouvé que les deux similarité approximatives et la réduction-bisimilarité approximative sont conservées par les divers constructeurs du calcul quantiques. Cela nous donne un outil formel pour observer la robustesse des processus quantiques contre inexactitude dans la mise en oeuvre de ses portes élémentaires.

Préliminaires

On a vu déjà les espaces de Hilbert et les opérateurs unitaires, le produit tensoriel et la mesure quantique mais que ce qu'un super-opérateur

Super-opérateurs :

La dynamique des systèmes quantiques ne peut pas être décrite par des opérateurs unitaires, et

38

chapitre4 : Modèles de calcul quantique

l'un de ses formalismes mathématiques est la notion de super-opérateur. Un super-opérateur sur un espace de Hilbert H est un opérateur linéaire à partir de l'espace d'opérateurs linéaires sur H dans lui-même qui satisfait aux deux conditions suivantes:

- tr [ (p)] tr (p) pour chaque p E D (H).

- Positivité complète : pour tout espace de Hilbert supplémentaire HR , ('R ® ) (A) est positif fourni.

A est un opérateur positif sur HR ® H, où 'R est l'opération d'identité sur les HR.

Si la première condition est renforcée à tr [ (p)] = tr (p) pour chaque p E D (H), alors est dit être tracepreserving.

4.4.2 Syntaxe et Sémantique Opérationnelle [YING et al., 2003]

Soit Chan l'ensemble des noms de canaux quantiques, et soit Var soit l'ensemble des variables quantiques. On suppose que Var est un ensemble infini dénombrable. Nous allons utiliser méta variables c, d, ... pour aller sur Chan et x, y, z, ... pour aller sur Var. Soit ô le nom de l'action silencieuse.

Pour chaque variable quantique x E Var, Imaginez que nous avons un système quantique nommé par x. Soit HX un espace de Hilbert complexe de dimension finie, qui est l'espace d'état du système de x. Pour tout x, y E Var, si HX = HY , alors on dit que x et y ont le même Type. Imaginez encore qu'il existe un système quantique grand composé de tous les x -systèmes, x E Var, dans lequel l'ensemble de nos processus quantiques demeurent. Nous appelons ce système composé l'environnement de notre calcul. Supposons HX _®x?X H_x

Pour tout X c Var. Alors H = HV _ar est l'espace d'état de l'environnement. Notez que H est un espace de Hilbert de dimension infinie dénombrable.

Nous supposons un ensemble de régimes constants du processus, variait en charge par méta variables A, B ... Pour chaque processus constant A, une arité non négatif ar (A) est attribué. Soit x = x1, x2, . . . , _xar(A) un triplet de variables quantiques distincts. Puis A (x) est appelé un processus constant. Nous écrivons P pour l'ensemble des processus quantiques, et nous écrivons fv (P) pour l'ensemble des variables quantiques libre en P pour chaque processus quantique p E P . Maintenant, nous sommes prêts à présenter la syntaxe de q-CCS.

4.4.2.1 La syntaxe

Définition 14. Les processus quantiques sont définis inductivement par les règles de formation suivantes :

(1) chaque processus constant A (x) est dans P et fv (A (x)) = {x}

39

chapitre4 : Modèles de calcul quantique

(2) nil ? P et fv (nil ) = ç

(3) si p ? P, alors ô.p ? P et fv (ô.p) = fv (p)

(4) sip ? P, X est une partie finie de Var, et est un super-opérateur sur H_x, alors [X] .p ? P , et fv ( [X] .p) = fv (p) ? X

(5) si p ? P, alors c?x.p ? P et fv (c?x.p) = fv (p) - {x}

(6) si p ? P et x ?/ fv (p), alors c!x.p ? P et fv (c!x.p) = fv (p) ? {x}

(7) si p, q ? P, alors p + q ? P et fv (p + q) = fv (p) ? fv (q)

(8) si p,q ? P et fv (p) n fv (q) = ç, alors p||q ? P et fv (p||q) = fv (p) ? fv (q)

(9) si p ? P et L ? Chan, alors p L ? P et fv(p L) = fv(p)

En utilisant la grammaire BNF standard la syntaxe de qCCS peut être résumée comme suit: P := A (x) |nil|ô.p| [X] .p|c?x.p|c!x.p|p + p|p||p|P L

Il est semblable à la syntaxe de CCS classiques, et les seules différences entre eux sont :

- La clause 4 de la définition ci-dessus nous permet d'effectuer des opérations quantiques sur certains systèmes sous-jacent.

- La condition x ?/ fv (p) dans la clause 6 et la condition fv (p) n fv (q) = ç dans la clause

8 sont nécessaires en raison du fait bien connu que l'information quantique inconnu ne peut être parfaitement clonée, (à la différence des bits classiques qui peuvent être copies et multiplies autant de fois que l'on veut, un qubit ne peut pas être dupliqué. Ce résultat essentiel est connu sous le nom de théorème de non-clonage. Il est à la base de la sécurité des processus de cryptographie quantique).

Il est à noter que ces conditions nous obligent à affecter un ensemble de variables quantiques libres pour chaque constante à l'avance processus. Les opérations quantiques peuvent être considérées comme des constructions pour le calcul quantique séquentiel. Il y a également des constructions pour le calcul séquentiel dans CCS passing value, mais ne sont pas explicitement donnés. Ici de telles constructions sont implicitement pris en charge dans les valeur des expressions, de sorte que l'on peut concentrer l'attention sur l'examen des comportements de communications entre les processus. Cependant, nous présentons explicitement les constructions pour le calcul quantique séquentiel dans la syntaxe de q-CCS, et c'est l'un des principaux objectifs d'observer l'interaction entre le calcul quantique séquentiel et de la communication de l'information quantique.

L Fait la liaison de tous les noms de canal par L, et l'entrée préfixe c?x lie la variable x quantique. Le symbole=_á sera utilisé pour désigner á convertibilité des processus définis en remplaçant les variables quantiques liés dans la manière standard.

Pour chaque régime constant de procédé A, une équation de définition de la forme :

40

chapitre4 : Modèles de calcul quantique

A (x) =^def P

est supposée, où P est un processus avec fv (P) Ç {x}. La définition récursive dans q-CCS est différente de celle de CCS classiques d'une certaine façon complexe. Par exemple, dans q-CCS

A (x) =^def c!x.A (x)

n'est pas autorisé à être l'équation définissant de schéma constant des processus A. En fait, si x E fv (A (x)), alors c!x.A (x) n'est pas un processus, et si x E/ fv (A (x)), alors fv (c!x.A (x)) fv (A (x)). Cependant,

A (y) =^def c?x.c!xA (y)

Est une équation légitime définissant A.

4.4.2.2 Sémantique Opérationnelle

La sémantique opérationnelle de q-CCS sera donnée par transitions entre les configurations, étiquetés par actions. Une configuration est définie comme une paire (P, p) où p E P est un processus et p E D(H) indique l'état actuel de l'environnement.

Intuitivement, p est une instanciation (ou valorisation) des variables quantiques. Instanciations de variables classiques peuvent être effectuées indépendamment les unes des autres, mais les systèmes quantiques représentées par des variables différentes peuvent être mises en corrélation, car p est admis à être un état intriqué. L'ensemble des configurations est écrit Con. Soit

Act = {ô} U _Actop ^U Actcom

Pour l'ensemble de mesures, le cas

Actop = { [X]} où :X est une partie finie de Var et est un super-operateur dans HX est l'ensemble des opérations quantiques, et Actcom = {c?x, c!x : c E Chan et x E Var est l'en-semble des actions de communication, y compris les entrées et sorties. L'ensemble Act sera varié au cours de méta variables á, â, .... Nous avons besoin des notations suivantes pour les actions :

- Pour chaque á E Act, on utilise cn (á) pour représenter le nom du canal dans l'action á c'est-à-dire cn (c?x) = cn (c!x) = c, et cn (ô) et cn ( [X]) sont indéfinis.

- Nous écrivons fv (á) pour l'ensemble des variables libres dans á, c'est-à-dire fv (c!x) = {x} , fv ( [X]) = X, fv (ô) = fv (c?x) = ö.

41

chapitre4 : Modèles de calcul quantique

bv (á) est définis d'être la variable liée à á, c'est- à-dire bv (c?x) = X , et bv (ô), bv (î [X]) et bv (c!x) sont indéfinis.

Pour présenter la sémantique opérationnelle de q-CCS, nous avons besoin d'une notation plus auxiliaire. Pour tout X ? Var et super-opérateur î sur HX, l'extension cylindrique de î sur H est défini :

îX =^def î ? IHvar-X

où _IHvar-X est l'opérateur identité sur HV _ar-X. Dans ce qui suit, nous supposons toujours que X est un ensemble fini de Var et î est un super-opérateur sur HX quand îX est rencontré. Ensuite, la sémantique opérationnelle de q-CCS est donnée comme un système de transition (Con, Act, ?), où la relation de transition ? est définie par les règles suivantes :

1. Tau : hô.P,pi4hP,pi 2. Oper : e[X] hî[X].P,pi? hP,îX(p)i 3. Input : y ?/ fv (c?x.P) hc?x.P,pi^c ?hPy/x,Pi 4. Output : hc!x.P,pi^c!x?hP,pi 5. Choise : hP,Qi4hP',Q'i hP+Q,pi4hP',Q'i hP,pi^c?x ?hP ',p'i 6. Intl1 : (PkQ,pi^c?x?hP'kQ,p'ix(Q) 7. Intl2 : hP,piá?hP',p'i n'est pas une entrée hPkQ,pi$hP'kQ,p'iá hP,P)^c? hP^',pihQ,pi^c!x?hQ^',pi 8. Comm : hPkQ,pi4hPkQ',pi 9. Res : hP,pi4hP',p'i cn (á)?/L hP/L,pi4hP'/L,p'i 10. Def : hP{y/ X},pi?hP ',p'i A (x) =^def P hA(x),pi4hP',p'i L'operateur îX (.) dans la règle Oper a été défini par îX (.) =def IH(V ar_X).

Lors de passage de

sortie hc!x.P, pi ?^c!x hP, pi, le x-système est envoyé par le canal c. Notez que l'état actuel du x-système est spécifié dans p. Mais p n'est pas nécessaire d'être un état séparé, et il est possible que le x-système est empêtré avec le y-système depuis un certain y ? Var - {x}.

Par ailleurs, l'intrication entre le x-système et des y-systèmes (y ?/ Var - {x}) est conservée après l'action c!x. La transition d'entrée hc?x.P, pi ?^c?y hPy/x, Pi signifie que le y-système est reçu par le canal c, puis il est mis dans les occurrences (gratuit) de x dans P (Il peut y avoir plus d'un occurrences libres d'une seule variable x dans P, car il n'est pas nécessaire que fv (P) n fv (Q) = ö en somme P + Q). Il convient de noter que dans c?x.P la variable x est

42

chapitre4 : Modèles de calcul quantique

lié et elle ne représente pas concrètement le x-système. Au contraire, il s'agit simplement d'une référence à l'endroit où le système reçu.

Ainsi, c?x.P peut exécuté l'action c?yavec y =6 x. La condition de côté y ?/ fv (c?x.p) pour le passage d'entrée est évidemment afin d'éviter les conflits nom de variable, et elle rend également que P {y/x} est bien définie. Au cours de l'exécution à la fois l'entrée et mesures de sortie, l'état de l'environnement n'est pas modifié. Passant systèmes quantiques qui se passe dans une communication décrit par la règle Comm, mais il est réalisé dans un système de «call-by-name" et ne modifie pas l'état de l'environnement.

CHAPITRE 5

LANGAGES DE PROGRAMMATION

QUANTIQUES

43

5.1 Comment définir la programmation quantique ?

La programmation quantique est un regroupement de langage de programmation permettant une expression d'algorithmes quantiques en utilisant des structures de haut niveau.

Le but des langages quantiques n'est pas tant de fournir un outil pour les programmeurs, mais surtout de proposer des outils pour les chercheurs afin de mieux comprendre comment les ordinateurs quantiques fonctionnent et comment raisonner formellement sur les problèmes quantiques. Dans cette section nous allons présenter un ensemble de langages de programmation quantiques qui permettent l'implémentation d'algorithmes quantiques. En utilisant des qubits, et fonctionnant sur des ordinateurs quantiques, (exécuter des opérations en manipulant des qubits).

5.2 Les langages impératifs

Omer [Omer, 2000], [Omer, 1998] a développé le langage QCL (Quantum Computing Language), le premier vrai langage de programmation quantique, avec une syntaxe inspirée principalement par C. Il a également mis en place un simulateur pour la langue. QCL contient un langage de programmation classique plein comme un sous-langage, et offre une gamme de fonctionnalités utiles de programmation quantique de haut niveau comme la gestion de la mémoire et de calcul automatique des versions conditionnelles des opérateurs.

Bettelli et al. (2003) définissent un langage de haut niveau basé sur C++ et une collection d'opé-rateurs primitives de bas niveau, les primitives de bas niveau sont basés sur le modèle QRAM (Quantum Random Access Machine Knill (1996)) mais sont destinés à être indépendants de l'architecture autant que possible. Ils donnent une certaine quantité de détails d'un système de compilation, et ont mis en oeuvre leur langage sous la forme d'une bibliothèque C++.

Sanders et Zuliani (2000) et Zuliani (2001) définissent le langage qGCL, qui est basé sur un langage contrôle-commande. QGCL hérite du monde contrôle-commande une sémantique en termes

44

chapitre5 : Langages de programmation quantiques

de deux transformateurs de prédicats, et un calcul de raffinement. Une partie de l'accent de ce travail est sur la dérivation des algorithmes quantiques. Zuliani (2004, 2005b) a étudié la programmation avec le non-déterminisme et les états mixtes dans le contexte de qGCL.

Tafliovich (2004) défini un langage de programmation quantique basé sur une programmation probabiliste prédicative. Le langage lui-même est impératif, et un aspect essentiel est une connexion étroite entre les programmes et les spécifications, avec un accent sur la mise en oeuvre de raffinement. Nous allons dans la suite de cette section présenter le langage QCL plus en détail.

5.2.1 Quantum Computing Language (QCL)

2.1. Quantum Computing Language (QCL) QCL est le langage quantique le plus connu, un des premiers, et sa syntaxe ressemble au langage C. Avec QCL [Omer, 1998] il est possible de combiner langage quantique et classique dans le même code source. Le type de donnée de base est : qureg (registre de qubits). Sur ces registres, les opérations élémentaires peuvent être effectuées : initialisation, transformations unitaires et mesures...

5.2.1.1 Syntaxe de QCL [Omer, 2000] [Omer, 2009] - Expressions

45

chapitre5 : Langages de programmation quantiques

- Statements

- Définitions

Exemple

quregx1 [2]; // Registre quantique à 2 qubits

quregx2 [2]; // Registre quantique à 2 qubits

H (x1); // Opération d'Hadamard sur x1

H (x2 [1]); // Opération d'Hadamard sur le premier qubit de x2

- Avec une librairie qulib, on peut observer l'état : qcl > dump

: STATE : 4/32 qubits allocated , 28/32 qubits free

46

chapitre5 : Langages de programmation quantiques

0.35355|0) + 0.35355|1) + 0.35355|2)

+0.35355|3) + 0.35355|8) + 0.35355|9)

+0.35355|10) + 0.35355|11)

- Mais surtout, on peut définir des fonctions :

Operator diffuse (quregq) {

H (q) ; // Transformation d'Hadamard

Not (q) ; // L'inverse de q

CPhase (pi, q) ; //Rotation si q=111...

!Not (q) ; // Annuler l'inversion

!H (q) ; // Annuler Transformation d'Hadamard

5.3 Langages Fonctionnels et Lambda-Calcul

Maymin (1996) définit deux extensions du A - calcul avec appel par-valeur. Le premier, un A - calcul probabiliste (A' - calcul), intègre des distributions de termes, ce qui permet des fonctions pour retourner des résultats aléatoires. Le second, un A-calcul quantique (Aq -calcul),qui va plus loin en permettant aux termes d'être représentés négativement dans les distributions, donc il ya la possibilité d'une interférence destructive lorsque les distributions sont combinés. Dans les deux cas, il est possible d'associer des coefficients numériques avec les termes dans une distribution, mais il est possible que les termes soient répétés. Dans le Aq - calcul, cela signifie qu'il est impossible d'exprimer des phases relatives d'autres que 180 degrés. Cela ressemble à une limitation significative, bien que Maymin montre que Aq - calcul est capable de résoudre efficacement les problèmes NP - complet, et dans un autre document (1997) soutient que Aq - calcul permet de simuler efficacement les automates cellulaires unidimensionnels partitionnés quantique, qui sont équivalentes à une machines de Turing quantique. Il semble que Aq - calcul peut être strictement plus expressive que le calcul quantique physiquement réalisable.

Van Tonder (2004) définit un A - calcul quantique, Aq, avec une sémantique opérationnelle et une théorie équationnelle. C'est un langage pour le calcul quantique pur : la mesure n'est pas envisagée. Il analyse la non-reproductibilité de l'état quantique en termes de logique linéaire et donne une définition inductive des termes Aq bien formés qui est, essentiellement, une forme simplifiée d'un système de type linéaire.

Valiron (2004) et Selinger et Valiron (2005, 2006) définissent un langage de programmation fonctionnelle d'ordre supérieur basé sur l'idée de contrôle classique et données quantiques. Le langage est basée sur l'appel par valeur du A-calcul, et comprend à la fois des données classiques

47

chapitre5 : Langages de programmation quantiques

et quantiques. La sémantique est opérationnel, bien que l'extension de Selinger (2004) donne une sémantique dénotationnelle, l'ordre supérieur est un objectif, et il ya un système de type basé sur la logique linéaire pour le contrôle de l'état quantique. Ils démontrent la préservation de type et les propriétés de sécurité de type, comme prévu pour les langages fonctionnels typés, et présentent un algorithme d'inférence de type.

Toujours dans l'extension du travail de Valiron (2004), Perdrix (2005) définit un système de type qui reflète l'intrication des parties de l'état quantique. L'idée est d'enrichir le type de l'environnement avec une relation d'équivalence sur les variables quantiques, ce qui représente une approximation de la relation d'intrication.

Arrighi et Dowek (2004, 2005) définissent un À - calcul linéaire algébrique dans lequel toutes les fonctions sont des opérateurs linéaires sur les espaces vectoriels. Bien que la modélisation de calcul quantique est un objectif majeur de leur travail, ils développent leurs théorie quelque peu indépendamment des spécificités de la mécanique quantique afin d'obtenir une vue plus générale de la signification de la linéarité. Une caractéristique notable de ce travail est l'identification d'une correspondance entre la notation pattern-matching familière de la programmation fonctionnelle et la notation algébrique linéaire définissant les opérateurs linéaires par leur effet sur les vecteurs de base.

Altenkirch et Grattage (2005a; 2005b) définissent un langage du premier ordre de la programmation fonctionnelle, QML, dont le contrôle, ainsi que les données peuvent être quantique. La sémantique de QML est exprimée en termes de théorie des catégories, ce qui fournit une base pour une sémantique dénotationnelle en termes de super opérateurs et une traduction dans les circuits quantiques. Le système de type de QML est basé sur la logique linéaire, mais se concentre sur l'élimination de l'affaiblissement (rejets l'état quantique) plutôt que de la contraction (duplication de l'état quantique), en effet, la contraction est autorisé mais elle est interprété comme le partage plutôt que la copie. Un autre objectif du système de type est de contrôler la décohérence, et cela est pris en charge par l'introduction d'un jugement et règles dérivation d'orthogonalité des états d'espaces. Dans la poursuite des travaux avec Vizzotto et Sabry (. Altenkirch et al 2006), les auteurs développent une théorie équationnelle complet pour le fragment pur de QML; cela donne aussi un algorithme de normalisation pour QML.

Danos et al. (2004) étudient le modèle unidirectionnel de calcul quantique, et développent une notation pour les composants clés de ce modèle : l'intrication, la mesure et correction local. Cette notation est basée sur les modèles. La principale contribution de cet article est de définir un calcul d'équations avec plus de modèles, ce qui conduit à un algorithme par lequel n'importe

48

chapitre5 : Langages de programmation quantiques

quel modèle peut être transformé en une forme standard comprenant intrication suivie par mesure suivie par une correction. Danos et Kashefi (2005) décrivent des conditions suffisantes pour les modèles de mesure à 'exécuter de façon déterministe. Danos et al. (2005) développent un calcul similaire de mesures à deux qubits, ce qui est pertinent d'utiliser la téléportation comme une primitive pour le calcul quantique.

(2004) Le travail de M. Selinger a été très influent dans le développement des langages fonctionnels pour le calcul quantique. Il définit un langage fonctionnel de premier ordre avec un système de type statique, en prenant l'approche des données quantiques et le contrôle classique. L'aspect le plus important de ce travail est la sémantique dénotationnelle. Celui-ci utilise le mécanisme standard d'ordres partiels complets et les fonctions continues [?], mais dans le cadre des espaces vectoriels et super opérateurs; une caractéristique essentielle est le traitement de partialité découlant de la non-récurrence de terminaison ou de boucles. Edalat (2004) a aussi étudié la sémantique des états partiels en informatique quantique. Dans la suite nous allons représenter à titre d'exemples les langages QML et Quipper.

5.3.1 QML : langage de programmation fonctionnel quantique

QML [Altenkirch et Grattage, 2005] est un langage fonctionnel pour les calculs quantiques sur des types finis. Le langage présente des données quantiques et les structures de contrôle quantique, et intègre le calcul quantique réversible et irréversible. QML est basé sur la logique linéaire stricte, pour maitre l'affaiblissement en évidence, les programmes stricts sont libre de décohérence.

La conception de QML est guidée par sa sémantique catégorique : les programmes QML sont interprétés comme des morphismes dans la catégorie FQC de Finite Quantum Computations. Ceci fournit une sémantique constructive de calculs quantiques irréversibles réalisables comme portes quantiques. Les relations entre la catégorie FQC et son homologue réversible classique, FCC (Finite Classical Computations), sont également explorées dans [Grattage, 2006a].

La sémantique opérationnelle des programmes QML est présentée en utilisant des circuits quantiques standards, tandis que la sémantique dénotationnelle est donnée en utilisant les super opérateurs.

5.3.1.1 La conception de QML

QML [Grattage, 2006b] possède à la fois des données quantique et le contrôle quantique, QML permet la contraction mais les contrôles affaiblissement et la mesure implicite. QML utilise

49

chapitre5 : Langages de programmation quantiques

une logique strictement linéaire avec un opérateur d'affaiblissement explicite, mais avec des contractions implicites. Cela se justifie par le fait que la signification d'un programme peut être affectée par le changement des affaiblissements, mais pas par les contractions déplacées. Deux opérateurs conditionnels sont également introduits : if, qui mesure un qubit, et if⁰, ce qui ne permet pas de mesurer, mais qui n'exige que les branches orthogonales. Cette exigence se traduit par l'introduction d'un jugement orthogonal à des conditions QML qui invoquent if⁰. La conception de QML est également motivée par la considération de la sémantique opérationnelle: la catégorie FQC. De la même manière que la catégorie FQC des calculs quantiques a été défini par analogie à la catégorie FCC de calculs classiques, le langage QML est conçu pour être aussi proche de formalismes classiques tant que possible. En effet, un sous-langage classique de QML pourrait être défini qui utilise FCC de sa sémantique opérationnelle, plutôt que FQC.

5.3.1.2 La syntaxe de QML

La syntaxe et les règles de typage de QML [Grattage, 2006b]sont basées sur la logique linéaire stricte : les contractions sont implicites, tandis que les affaiblissements sont une opération explicite qui correspondent à des mesures. Les types de QML sont de premier ordre et fini. Il n'y a pas de types récursifs, donc, par exemple, un type de nombres naturels quantique ne peut être définie. Le constructeur de type de QML est le produit tensoriel, ?, ce qui correspond à un type de produit. Qubits et superpositions de qubits simples sont des primitives. QML a deux constructions : if, qui mesure un qubit dans les données qu'il analyse (le classique-if), et if⁰, qui ne mesure pas, mais exige que les résultats soient toujours existés en sous-espaces orthogonaux (le quantum-if). Les preuves de l'orthogonalité peuvent être insérées automatiquement par le compilateur, et donc ne figurent pas dans la syntaxe des termes. Les symboles grecs u, r, p sont utilisés pour parcourir des types QML, qui sont donnés par la grammaire suivante :

u = ö1|ö2|u ? r

Un approvisionnement infini de noms de variables concrètes est supposé, et x, y, z sera utilisée pour parcourir sur les noms. Les contextes de typage (F, z) sont donnés par :

F =.|F,x : u

Où . représente le contexte vide, mais il sera omis si le contexte est non vide. Pour plus de simplicité, on suppose que chaque variable apparaît au plus une fois. Les contextes correspondent à des fonctions d'un ensemble fini de variables à des types.

Pour définir la syntaxe des expressions les constantes ê, é E C sont également utilisés, et variables

50

chapitre5 : Langages de programmation quantiques

de la fonction sont utilisés pour désigner les programmes QML préalablement définis. Les termes de QML consistent en celles d'un langage fonctionnel du premier ordre, à des données étendu quantique, une structure de commande quantique, et un opérateur de mesure. La grammaire des termes QML est définie comme suit :

(variables) x, y, .... E Vars

(prob,amplitudes) k, é, ... E C

? |qtrue y |0|k×t|t+u

(patterns) p, q ::= x|(x, y)

?

(termes) t, u ::= x|x^y |()|(t, u)| let p = t in u| if t then u else ^u0|if° t then uelseu'|qfalse

?

Ici, la notation vectorielle á est utilisée pour des séquences d'objets syntaxiques. Formellement,

elle correspond au méta notation suivante :

? á= å

|á ?á

Les données quantiques sont modélisées en utilisant les constructions kxt, t+u, avec la constante 0 formé des termes avec une amplitude de probabilité zéro. Le terme k x t, où k est un nombre complexe, associe l'amplitude k de probabilité avec le terme t. Le terme t + u décrit une superposition quantique de t et u. Les superpositions quantiques sont des valeurs de premier ordre, et peuvent être utilisés dans une condition pour donner un contrôle quantique. Par exemple, if⁰(qtrue + qfalse)then t else u

Evalue à la fois t et u tout en conservant les résultats dans une superposition quantique. Comme un exemple de superpositions formant, le terme ^v12 x qfalse + ^v12 x qtrue est une superposition de qfalse et qtrue. Les facteurs de Normalisation qui sont égaux sont parfois omises, et peuvent ensuite être déduites d'être égaux ; l'exemple précédent devenir simplement qfalse + qtrue.

5.3.2 Quipper : langage de programmation quantique scalable

Description

Quipper [Alexander S. Green et Valiron, 2012] [Alexander S. Green et Valiron, 2013]est un langage de programmation quantique fonctionnel et scalable, il a été testé par l'implémentation de sept algorithmes quantiques non-triviaux dans la littérature et qui sont :

- BWT (pour Binary Welded Tree). Pour trouver des noeuds dans un graphe.

- BF (Boolean Formula). Pour évaluer une formule NAND. La version de ces algorithmes implémentés dans Quipper calcule la stratégie de gain pour le jeu de Hex.

- CL (Class Number). Pour approximer la classe de groupe d'un nombre réel quadratique.

51

chapitre5 : Langages de programmation quantiques

- GSE (Ground State Estimation). Pour calculer le niveau d'énergie le plus faible d'état d'une particule moléculaire.

- QLS (Quantum Linear System). Pour résoudre un système d'équation linéaire.

- USV (Unique Shortest Vector). Pour choisir le vecteur court parmi une collection. - TF (Triangle Finding). Pour exhiber un triangle à l'intérieur d'un graph dense.

Ces algorithmes sont choisis pour représenter une portée étendue de la capacité de l'infor-matique quantique. Les algorithmes ont étés implémentés par une équipe de 11 Quipper programmeur distribués géographiquement. Quipper fournier entre autre : [Alexander S. Green et Valiron, 2013]

- - Langage de haut niveau pour la description de circuit, cela inclut la description porte à porte des fragments de circuit, ainsi que les opérateurs puissants pour l'assemblage et la manipulation de circuits.

- Une sémantique monadiques, permettant un mélange de styles de programmation procé-durale et déclarative.

- Les installations intégrées pour la synthèse automatique des circuits quantiques réversibles, notamment à partir du code classique.

- Prise en charge de circuits hiérarchiques. - Extensible types de données quantiques. - Circuits transformation programmables.

- Prise en charge de trois phases d'exécution : la compilation, le temps de génération de circuit, et le temps d'exécution de circuit. Une opération de levage dynamique pour permette le circuit de génération d'être paramétrique sur les valeurs générées lors de l'exécution du circuit.

- Bibliothèques étendues de fonctions quantiques, incluant : des bibliothèques pour les entiers quantiques, la transformée de Fourier quantique; une mise en oeuvre de QRAM efficace;

52

chapitre5 : Langages de programmation quantiques

bibliothèques pour la simulation de circuits pseudo-classiques, circuits stabilisant et circuits arbitraires, les bibliothèques pour la décomposition exacte et approximative de circuits en ensembles de grille spécifiques.

CHAPITRE 6

Q-LOTOS

53

6.1 Introduction

Les processus quantiques peuvent décrire des systèmes concurrent qui utilisent eux même des information quantiques, pour cette fin nous allons proposer une extension du langage LOTOS dans sa version Basic, nommée Q-LOTOS pour(Quantum LOTOS).cette extension est obtenue par l'élargissement de l'ensemble des informations traitées vers des informations quantiques exprimées par des qubits plutôt que par bits, et aussi par l'ajout d'un super opérateur exprimant les opération quantiques sur l'ensemble d'actions.

6.2 Basic LOTOS

LOTOS est une technique de description formelle normalisée à l'ISO [FDT/C, 1987]. Une spécification LOTOS est constituée de deux parties :

La partie données décrit les données comme étant des types abstraits algébriques.

La partie contrôle dérivé des algèbres de processus, principalement de CCS (Calculus of Communicating Systems [Milner, 1989]), mais aussi de CSP (Communicating Sequential Processus [Hoare, 1985]), et qui décrit le comportement de la spécification.LOTOS est un langage asynchrone, avec synchronisation par rendez-vous multiples. Les processus offrent des synchronisations à leur environnement au travers de portes de communication (ou actions). Dans le cadre de notre étude, le sous ensemble de LOTOS qui sera utilisé est appelé Basic LOTOS.

Basic LOTOS est le sous-ensemble de LOTOS où les processus interagissent entre eux par synchronisation pure, sans échange de valeurs. En Basic LOTOS, les actions sont identiques aux portes de synchronisation des processus.

6.2.1 Syntaxe de Basic LOTOS

:

Formellement Basic LOTOS se presente comme suit :

Soit P l'ensemble des variables de processus parcouru par X, Y, ... et soit G l'ensemble des noms

54

chapitre6 : Q-LOTOS

de portes définies par l'utilisateur (ensemble des actions observables) parcouru par g, h, .... Une porte observable particulière 8 E G est utilisée pour notifier la terminaison avec succés des processus. L dénote tout sous-ensemble de G, l'action interne est désignée par r.

B parcouru par E, F, ... dénote l'ensemble des expressions de comportement dont la syntaxe est : [Belala, 2005]

E :: = stop | exit | X[L] | g; E | r;E

| E[]E | E |[L]| E hide L in E | E > >E | E [>E .

Etant donné un processus dont le nom est P et dont le comportement est E, la définition de

P est exprimée par P := E. L'ensemble de toutes les actions est désigné par Act où :

Act = G U Ir, 8}.

- stop : Processus de base n'interagissant pas avec son environnement. "Inaction".

- exit : Processus qui se termine (action 8) et se transforme en stop. "Terminaison avec succés".

- g; E , r ; E : Processus qui réalise l'action r ou g, puis se transforme en P. "Préfixage par une action".

- E1[]E2 : Processus qui se transforme en E1 ou en E2 suivant l'environnement. "Choix non-déterministe".

- E1| [L] |E2 : E1 et E2 s'exécutent en paralléle et se synchronisent sur les portes g_z E L et 8. "Composition paralléle".

- hide L in E : Les actions L sont cachées à l'environnement de E et deviennent des actions internes. "Intériorisation".

- E1 > >E2 : E2 est activé dés que E1 se termine. "Composition séquentielle".

- E1 [>E2 : E2 peut interrompre E1 tant que E1 ne s'est pas terminé. "Préemption (interruption)".

55

chapitre6 : Q-LOTOS

6.2.2 Sémantique opérationnelle de Basic LOTOS

La sémantique opérationnelle du langage Basic LOTOS est donnée par l'ensemble des règles d'inférence suivantes :

1.

2.		exit-->.stop

3. (a) E4E'

E[]F4E'

E4E'

(b)- F[]E4E'

{8

4. (a)i.E|[L]|FE4E'aELU'|[L]}|F ii. E4E'a/ELU{8} F|[L]|E4F|[L]|E' -->.F'a/ELU{8} (b)Ea -->.E',F a E|[L]|F4E'|[L]|F'

5. (a) (b)

E4E'a/EL hideLinE4hideLinE' E4E'aEL hideLinE4hideLinE'

a6=8

6. (a) E4E'

(b)

E>>F-E'>>F E4E^'a6=8 E>>F4E'>>F E4E^'a

7. (a) 8
E[>F-E'[>F

_(b)E4E'a6=8 E[>F4E' (c)F4F'a 8

E[>F4F'

6.3 Q-LOTOS

on va introduire une technique Q-LOTOS pour (Quantum Language of Temporal Ordering Specification) de description formelle pour la spécification des intéractions quantiques

6.3.1 Syntaxe de Q-LOTOS

La syntaxe de Q-LOTOS est une extension de celle de Basic LOTOS avec l'introduction des actions quantique (actions sur desinformations quantiques). Soit :

- P l'ensemble de processus quantiques

56

chapitre6 : Q-LOTOS

- G l'ensemble d'actions classiques. Q est l'ensemble d'actions quantiques - 8 action particulière qui désignée la terminisation avec succés

- r action particulière qui désignée une action silencieuse

- L c G un sous-ensemble (pouvant être vide) quelconque de G

- M c Q un sous-ensemble quelconque de Q

avec l'ensemble de toutes les actions est désigné par Act où :

Act = G U Q U {r,8}.

Dans ce qui suit, nous supposons toujours que M est un ensemble fini de Q et est un super-opérateur sur HM quand [M] ou _M est rencontré.

VM c Q, M =def ® IH_Q- où IH_Q- est l'opérateur d'identité de HQ-M

La syntaxe formelle du Q-LOTOS est donnée par:

P : := stop exit X[L] [M];P á;P r;P P[]P P |[M]|P |

hide L in P P >> P P[> P

où á E Q U G et M c Q U G.

Il est semblable à la syntaxe de Basic LOTOS, et les seules différences entre eux sont :

- La clause [M]; P de la définition ci-dessus nous permet d'effectuer des opérations quantiques sur certains processus quantiques.

- La clause q; P : Processus qui réalise l'action quantique q, puis se transforme en P. "Pré-fixage par une action quantique".

- La clause E1 [M] E2 : E1 et E2 s'exécutent en paralléle et se synchronisent sur les portes quantiques qi E M et la porte 8. "Composition paralléle".

6.3.2 Sémantique Opérationnelle

La sémantique opérationnelle du langage Q-LOTOS est donnée par l'ensemble des règles d'inférence suivantes :

chapitre6 : Q-LOTOS

1.

2.

3.

exit ^ä +stop

á;E^á+E

î[M];E^î[M1

+ îM (E)

4. 57

(a) Eá+E'

E^á+E'

(b) F[]Eá+E'

E^á+E'a/ELU{ä}

5. (a)2. E|[L]|Fá+E'|[L]|F

ii . F|[L]|Eá+F|[L]|E'

b Eá+E',F$F'a/ELU{ä} () E|[L]|Fá+E'|[L]|F'

E^á+E'a/ELU{ä}

4. (a)i.

E^á+E'a/EMU{ä}

ii.

E|[M]|F^á+E'|[M]|F E^á+E'a/EMU{ä}

F|[M]|E^á+F|[M]|E'

+F'a/EMU{ä}

(b)Eá +E',F á

E|[M]|F^á+E'|[M]|F'

7. (a) Eá+E'a/EL
hideLinE^á+hideLinE' E^á+E'aEL

(b)

hideLinE+ô hideLinE'

E^ä+E^'

8. (a) E>>F+aE'>>F

E^á+E'ä

(9. (b) a E»F-+TE'»F
) Eá+E'a6=ä a) E[>Fá+E'[>F _(b)E^á+E'a6=ä

E[>F^á+E'

_(c)F^á+F'a6=ä E[>F^á+F'

6.4 Conclusion

Nous avons proposé une extension du langage LOTOS, nommée Q-LOTOS et nous avons donné sa syntaxe formelle et sa sémantique opérationnelle exprimée par un STE et qui peut être aussi exprimée par un STEP que nous n'avons pas exploré le long de ce mémoire pour des raisons liés au temps, et qui nous souhaitons être faite dans un future travail.

58

Conclusion générale

Ce travail s'inscrit dans le cadre de développement des systèmes formels pour l'informatique quantique, nous avons mis comme objectif de ce mémoire, l'élaboration d'une synthèse (vue globale non exhaustive) sur l'état de l'art de ce domaine, et la proposition d'une extension du langage LOTOS vers son analogue quantique q-LOTOS, tout en donnant sa syntaxe formelle et sa sémantique opérationnelle.

Nous avons devisé ce mémoire en trois parties :

1ér partie pour explorer les notions mathématiques et les notions de la physique ayant rapport avec l'informatique quantique, et qui servent d'éléments de base de ce dernier.

2éme partie pour explorer les fondements théoriques du sujet, nous avons mis en évidence, les principaux algorithmes, modèles de calcul et langages de programmations quantiques.

3éme partie est consacré a l'extension proposée nommée Q-LOTOS.

Perspectives

Ce sujet peut étendu dans plusieurs directions :

- Elaboration de modèles de bas niveau basés sur l'approche action plutôt que l'approche évènement, à des fins de caractérisation mathématique des sémantiques de vraie parallélisme (maximalité comme exemple), tout en profitant du parallélisme qu'offre l'aspect quantique.

- Une interprétation du modèle proposé q-LOTOS par la sémantique floue (FTS; Systèmes de Transition Floue) paraît intéressante est prometteuse.

59

Bibliographie

[Alexander S. Green et Valiron, 2012] ALEXANDER S. GREEN, Peter LeFanu Lumsdaine, N. J. R. P. S. et VALIRON, B. (11 avril 2012). Quipper : A scalable quantum programming language.

[Alexander S. Green et Valiron, 2013] ALEXANDER S. GREEN, Peter LeFanu Lumsdaine, N. J. R. P. S. et VALIRON, B. (19 Apr 2013). An introduction to quantum programming in quipper. Dalhousie University, Halifax, NS, Canada.Institute of Advanced Studies, Princeton, NJ, U.S.A.University of Pennsylvania, Philadelphia, PA, U.S.A, pages 1-15.

[Altenkirch et Grattage, 2005] ALTENKIRCH, T. et GRATTAGE, J. (2005). A functional quantum programming language. 20th Symposium on Logic in Computer Science (LICS).

[Belala, 2005] BELALA, N. (Juin 2005). Formalisation des systèmes temps-réel avec durées d'ac-tions. Masters thesis, Université Mentouri, 25000 Constantine, Algérie.

[Bennett et Wiesner, 1992] BENNETT, C. H. et WIESNER, S. J. (1992). Communication via one-and two-particle operators on einstein-podolsky-rosen states. Phys. Rev. Lett.

[Bernstein et Vazirani, 1997] BERNSTEIN et VAZIRANI (1997). Quantum complexity theory. SIAM J. Comput.

[Deutsch, 1985] DEUTSCH, D. (1985). Quantum theory, the church-turing principle and the universal quantum computer. Proc. R. Soc. Lond. A., page 400 :97-117.

[Deutsch et Jozsa, 1992] DEUTSCH, D. et JOZSA, R. (1992). Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. A, page 439-553.

[FDT/C, 1987] FDT/C, I.. (1987). Lotos,a formal description technique based on the temporal ordering. Technical Report DIS 8807,ISO.

[Feynman, 1982] FEYNMAN, R. P. (1982). Simulating physics with computers. International Journal of Theoretical Physics, page 467-488.

[Feynman, 1984] FEYNMAN, R. P. (1984). Quantum-mechanical computers. J. Opt. Soc. Am, page 464.

[Glendinning, 2005] GLENDINNING, I. (February 16, 2005). The bloch sphere. European Centre For Parallel Computing at Vienna VCPC.

60

[Gradel, 0910] GRADEL, P. D. E. (2009/10). Quantum computing. Mathematische Grundlagen der Informatik RWTH Aachen, pages 19-34.

[Grattage, 2006a] GRATTAGE, J. J. (2006a). A functional quantum programming language. Thèse de doctorat, The University of Nottingham for the degree of Doctor of Philosophy.

[Grattage, 2006b] GRATTAGE, J. J. (September 2006b). A functional quantum programming language. Thèse de doctorat, The University of Nottingham for the degree of Doctor of Philosophy.

[Grover, 1996] GROVER, L. K. (1996). A fast quantum mechanical algorithm for database search. In ACM Symposium on Theory of Computing, page 212-219.

[Haroche, 2002] HAROCHE, S. (26 Février 2002). algorithmes quantiques. Leçons du Collège de France Chaire de Physique quantique. 8ème leçon.

[Hoare, 1985] HOARE, C. A. R. (1985). Communicating sequential processes. Prentice Hall.

[Jorrand, 2012] JORRAND, P. (1er janvier 2012). Algorithme quantique de shor factorisation des entiers en temps polynomial.

[Jorrand, 2005] JORRAND, P. (2005). Algorithme quantique de grover accélération quadratique de la recherche dans une base de données. CNRS Laboratoire Leibniz, Grenoble, France.

[Lacour, 2007] LACOUR, X. (2007). Information Quantique par Passage Adiabatique Portes Quantiques et Décohérence. Thèse de doctorat, Docteur en Physique Université de Bourgogne.

[law Adam MISZCZAK, 2011] law ADAM MISZCZAK, J. (3 Dec 2011). Models of quantum computation and quantum programming languages. Institute of Theoretical and Applied Informatics, Polish Academy of Sciences, Ba ltycka, pages 44-100.

[Michael A, 2000] MICHAEL A, Nielsen Issac, L. C. (2000). Quantum computation and quantum information. University of CAMBRIDGE.

[Milner, 1989] MILNER, R. (1989). Communication and concurrency. Prentice Hall.

[Monerau, 2008] MONERAU, M. (Novembre 2008). Algorithmique quantique : de l'exponentiel au polynômial.

[Omer, 2000] OMER, B. (20th January 2000). Quantum programming in qcl. Institute of Information Systems Technical University of Vienna.

[Omer, 1998] OMER, B. (23th July 1998). A procedural formalism for quantum computing. Department of Theoretical Physics Technical University of Vienna.

[Omer, 2009] OMER, B. (2nd September 2009). Structured quantum programming. Institute for Theoretical Physics Vienna University of Technology, page 130.

[Perdrix, 2006] PERDRIX, S. (2006). Modèles formels du calcul quantique ressources, machines abstraites et calcul par mesure. Thèse de doctorat, National Polytechnique De Grenoble.

61

[Rolland, 2006] ROLLAND, R. (2006). Produit tensoriel d'espaces vectoriels. CNRS Laboratoire Leibniz, Grenoble, France.

[Shor, 1997] SHOR, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Computing.

[Y, 1993] Y, Y. (1993). Quantum circuit complexity. Proc of the 34th Annual Symposium on Foundations of CS.

[YING et al., 2003] YING, M., FENG, Y., DUAN, R. et JI, Z. (September 2003). An algebra of quantum processes. Tsinghua University and University of Technology, Sydney,Institute of Software, Chinese Academy of Sciences, page 33.