Etude de la notion de virus dans le modéle de calcul des machines de Turing quantiques-1

Publié par

Ecole Normale Superieure de LyonRapport de stage L3Etude de la notion de virusdans le modele de calcul desmachines de TuringquantiquesAntoine TaveneauxMa^ tre de stage : Jean-Yves MarionJuin - Juillet 2008Table des matieres1 Les bases de mecaniques quantiques 21.1 Etat quantique . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 L’evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3 Systemes composes . . . . . . . . . . . . . . . . . . . . . . . . 31.4 Les mesures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Le modele de la machine de Turing quantique 43 Programmation d’une machine de Turing quantique 64 Notion de virus pour une machine de Turing quantique 84.1 Des resultats basiques . . . . . . . . . . . . . . . . . . . . . . 104.2 A propos de la copie d’un etat quantique . . . . . . . . . . . 114.3 Deux quines quantiques . . . . . . . . . . . . . . . . . . . . . 125 Detection virale 136 Protection virale 146.1 a posteriori . . . . . . . . . . . . . . . . . . . . . . 157 Conclusion et perspectives 16A Annexe sur le theoreme de recursion 18ResumeApres une rapide presentation des phenomenes de mecanique quantiqueutilises en informatique quantique, nous introduisons le modele de calculdes machines de Turing quantique. Ensuite nous proposons une de nitionde virus dans ce modele de calcul, de telle sorte que cette de nition generalisela de nition donnee par Fred Cohen pour ...
Publié le : samedi 24 septembre 2011
Lecture(s) : 51
Nombre de pages : 19
Voir plus Voir moins
´ EcoleNormaleSup´erieuredeLyon Rapport de stage L3
´ Etude de la notion de virus danslemod`eledecalculdes machines de Turing quantiques
Antoine Taveneaux
Maıˆtredestage:Jean-YvesMarion
Juin - Juillet 2008
Tabledesmatie`res 1Lesbasesdem´ecaniquesquantiques2 ´ 1.1 Etat quantique . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2L´evolution............................3 1.3Syste`mescompose´s........................3 1.4 Les mesures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2Lemode`ledelamachinedeTuringquantique4 3 Programmation d’une machine de Turing quantique 6 4 Notion de virus pour une machine de Turing quantique 8 4.1Desr´esultatsbasiques......................10 ´ 4.2Aproposdelacopiedun´etatquantique...........11 4.3 Deux quines quantiques . . . . . . . . . . . . . . . . . . . . . 12 5De´tectionvirale13 6 Protection virale 14 6.1 Protection a posteriori . . . . . . . . . . . . . . . . . . . . . . 15 7 Conclusion et perspectives 16 AAnnexesurlethe´or`emeder´ecursion18 R´esume´ Apr`esunerapidepre´sentationdesphe´nome`nesdeme´caniquequantique utilise´seninformatiquequantique,nousintroduisonslemod`eledecalcul desmachinesdeTuringquantique.Ensuitenousproposonsunede´nition devirusdanscemod`eledecalcul,detellesortequecetted´enitionge´ne´ralise lade´nitiondonn´eeparFredCohenpourlesmachinesdeTuringclassiques. Nouspre´sentonsdesexemplesdetellesvirusdansdi´erentscadres.Enn, nouse´tudionscertainespropri´et´esdecesvirusetenparticulierleurde´tection etnouse´tudionsunepisteder´eexion`aproposdunepolitiquedes´ecurite´. Remerciements Jetiens`aremercierJean-YvesMarion,monencadrant,poursagentil-lesseetsonsoutien.Merciaussi`aEmmanuelHainry,RomainP´echouxet MatthieuKaczmarekainsiqua`touslesdoctorantsdele´quipeCARTEdu LORIApourleuraccueiletleuraide.Mercienna`NatachaPortierpour son aide dans les recherches bibliographiques. 1
Duouiaunon,combiendepeut-eˆtre? [JulioCorta´zar]
Introduction Lame´caniquequantiqueestuneth´eoriephysiquequisechargedelade-scriptiondelinnimentpetit.Cetteth´eoriepre´ditdesphe´nome`nesquecer-tainsphysiciensetinformaticiensontimagin´epouvoirutiliserpourre´aliser descalculs.Cettepossibilite´estaujourdhuipresqueuniquementspe´culative maisdes´etudesth´eoriquestententdecernercequapporteraitcenouveau typedecalcul.Cetravailsinscritdanscetted´emarche´etudiantlid´eede programmeviralpourcemod`eledecalcul. Dansunpremiertempsnousallonspr´esenter,demanie`resynth´etique, lesideesphysiquesutilise´eseninformatiquequantique.Ensuitenousintro-´ duironslemod`eledesmachinesdeTuringquantiquesquiapourobjectifde pre´senterunmod`eledecalculpuisnousintroduironsquelquesre´sultatsqui faciliteront la ”programmation” effective de telles machines. Nouspre´senterons,enn,lesre´sultatsobtenuslorsdecestage.Nous proposeronsunede´nitiondevirusquantique(etduneclasseplussp´ecique devirus:lesvirusforts)ge´n´eralisantcelledeFredCohensurlesmachinesde Turingclassiques.Ensuite,nouse´tudieronsquelquesproprietes´el´ementaires ´ ´ des ensembles viraux et nous donnerons deux exemples de quines quantiques. Ennnousmontreronsunr´esultatsurprenantpuisquelade´tectionparfaite des virus quantiques connus est impossible (dans le cadre des machines de Turingquantiques),maisilestpossibledesenprote´ger.Noustoucherons ainsi l’aspect fondamental du calcul quantique. Enfin nous ouvrirons une r´eexionplusinformellesurunepolitiquedes´ecurit´epourdesmachinesde Turing quantiques.
1Lesbasesd´ecaniquesquantiques e m ´ 1.1 Etat quantique Contrairementa`unsyste`meclassique,unsyst`emequantiquepeutˆetre dansdeuxe´tatssimultane´ment:enunesuperpositiond´etats.Plusformelle-ment:`atoutsyste`mephysiqueisole´onpeutassocierunespacevectoriel munidunproduitscalaire(quelonnommeraespacedese´tatsdusysteme) ` etlesyst`emeestenti`erementde´critparsonvecteurde´tat.Cevecteurest denorme1danslespacede´tatsassoci´ es es. Parexemple:pouruneparticule,lespinpeuteˆtre1ou0(upou down).Enm´ecaniquequantiquelaparticulepeutalorseˆtreensuperpo-sitiond´etats:unecombinaisonlinaire(unitaire)del´etat0etle´tat1.Par exemple:l´etatsuperpos´e 12 ( | 0 i + | 1 i )estun´etatpossible;o`u | 0 i et | 1 i sont
2
lesvecteursorthonormauxd´esignantles´etats0et1.Untelsyst`emeavec deux´etatssuperposables( | 0 i et | 1 i ) sera ce que l’on appelle dans la suite unqubit.L´etatdunqubitpeutdoncse´crire α | 0 i + β | 1 i avec α 2 + β 2 = 1. Danslasuitenousverronscommenttravailleravecplusieursqubitsenmˆeme temps. 1.2Le´volution Lessyst`emesquantiquesferme´se´voluentseulementselondestransforma-tions admissibles. Ces transformations admissibles sont les transformations unitairesdelespacevectorieldese´tats. Cest`adirequesi | ϕ i estle´tatdusyst`emea`uninstant t 1 ,alors,a`un instant t 2 sone´tatsera | ϕ 0 i tel qu’il existe une transformation unitaire U pour laquelle | ϕ 0 i = U | ϕ i et comme U est unitaire on a U .U = I . Onremarquealorsquetouteslestransformationsdessyste`mesferm´es (sanseectuerdemesure)sontr´eversibles.Ceciseraunfaitimportantdans lemode`ledesmachinesdesTuringquantiques. Un exemple de transformation d’un qubit est : H = 12 11 11 H transforme donc | 0 i en 12 ( | 0 i + | 1 i ) et | 1 i en 12 ( | 0 i − | 1 i ). Cette trans-formationintroduitdoncunesuperpositiond´etatsa`partirduneentre´e classique. 1.3St`emescomp´ ys oses Lespacevectorieldese´tatsdunsyste`mephysiquecompose´desous syst`emesestleproduittensorieldesespacesdese´tatsdessoussyste`mes. Ainsilespacedese´tatsdedeuxsyst`emesdontlespacedes´etatsest A et B aurapourespacedes´etats A ⊗ B . Habituellement on note | a 1 i ⊗ | a 2 i ⊗ ... ⊗ | a k i = | a 1 a 2 ...a k i . Ainsiparexemple,unsyste`meconstitu´ededeuxqubitsaurapourespace lespacege´n´ere´parlesvecteurs | 0 i⊗| 0 i = | 00 i , | 0 i⊗| 1 i = | 01 i , | 1 i⊗| 0 i = | 10 i et | 1 i ⊗ | 1 i = | 11 i . Un espace de n qubits sera donc de dimension 2 n . C’est ce point qui permet de mieux comprendre la puissance du calcul quantique car en quelque sortelapuissancedecalculdoubleavecchaquequbitsupple´mentaire. 1.4 Les mesures Unsyste`meensuperpositionpeutsubirunemesurequivar´eve´leral´eatoirement unetunseuldes´etatsavecuneprobabilit´ed´enieparle´tatdesuperpo-sition,etensuitele´tatdusyst`emeseraexactementceluiquia´ete´mesur´e. Ainsilamesurefaite´voluerlesyste`medemanie`reirre´versible. 3
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.