WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

Modèles formels pour l'informatique quantique

( Télécharger le fichier original )
par Sami Ben Ahmed
Université Abess Laghrour KHENCHELA - Master 2 en Informatique 2013
  

sommaire suivant

Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy

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 2n 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.

sommaire suivant











Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy

9Impact, le film from Onalukusu Luambo on Vimeo.