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