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

Description

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

Informations

• Publié par: Orga
• Nombre de lectures: 51
• Langue: Français

Extrait

´ 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.2Aproposdelacopied’un´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´finition devirusdanscemod`eledecalcul,detellesortequecetted´efinitionge´ne´ralise lade´finitiondonn´eeparFredCohenpourlesmachinesdeTuringclassiques. Nouspre´sentonsdesexemplesdetellesvirusdansdiff´erentscadres.Enfin, nouse´tudionscertainespropri´et´esdecesvirusetenparticulierleurde´tection etnouse´tudionsunepisteder´eflexion`aproposd’unepolitiquedes´ecurite´. Remerciements Jetiens`aremercierJean-YvesMarion,monencadrant,poursagentil- lesseetsonsoutien.Merciaussi`aEmmanuelHainry,RomainP´echouxet MatthieuKaczmarekainsiqu’a`touslesdoctorantsdel’e´quipeCARTEdu LORIApourleuraccueiletleuraide.Mercienfina`NatachaPortierpour son aide dans les recherches bibliographiques. 1

Duouiaunon,combiendepeut-eˆtre? [JulioCorta´zar]

Introduction Lame´caniquequantiqueestuneth´eoriephysiquequisechargedelade- scriptiondel’infinimentpetit.Cetteth´eoriepre´ditdesphe´nome`nesquecer- tainsphysiciensetinformaticiensontimagin´epouvoirutiliserpourre´aliser descalculs.Cettepossibilite´estaujourd’huipresqueuniquementspe´culative maisdes´etudesth´eoriquestententdecernercequ’apporteraitcenouveau typedecalcul.Cetravails’inscritdanscetted´emarche´etudiantl’id´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,enfin,lesre´sultatsobtenuslorsdecestage.Nous proposeronsunede´finitiondevirusquantique(etd’uneclasseplussp´ecifique devirus:lesvirusforts)ge´n´eralisantcelledeFredCohensurlesmachinesde Turingclassiques.Ensuite,nouse´tudieronsquelquesproprietes´el´ementaires ´ ´ des ensembles viraux et nous donnerons deux exemples de quines quantiques. Enfinnousmontreronsunr´esultatsurprenantpuisquelade´tectionparfaite des virus quantiques connus est impossible (dans le cadre des machines de Turingquantiques),maisilestpossibledes’enprote´ger.Noustoucherons ainsi l’aspect fondamental du calcul quantique. Enfin nous ouvrirons une r´eflexionplusinformellesurunepolitiquedes´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 munid’unproduitscalaire(quel’onnommera”espacedese´tatsdusysteme”) ` etlesyst`emeestenti`erementde´critparsonvecteurd’e´tat.Cevecteurest denorme1dansl’espacede´tatsassoci´ es es. Parexemple:pouruneparticule,lespinpeuteˆtre1ou0(upou down).Enm´ecaniquequantiquelaparticulepeutalorseˆtreensuperpo- sitiond’´etats:unecombinaisonlinaire(unitaire)del’´etat0etl’e´tat1.Par exemple:l’´etatsuperpos´e √ 1 2 ( | 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’´etatd’unqubitpeutdoncs’e´crire α | 0 i + β | 1 i avec α 2 + β 2 = 1. Danslasuitenousverronscommenttravailleravecplusieursqubitsenmˆeme temps. 1.2L’e´volution Lessyst`emesquantiquesferme´se´voluentseulementselondestransforma- tions admissibles. Ces transformations admissibles sont les transformations unitairesdel’espacevectorieldese´tats. C’est`adirequesi | ϕ i estl’e´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 (sanseffectuerdemesure)sontr´eversibles.Ceciseraunfaitimportantdans lemode`ledesmachinesdesTuringquantiques. Un exemple de transformation d’un qubit est : H = √ 1 2  1 1 − 1 1  H transforme donc | 0 i en √ 1 2 ( | 0 i + | 1 i ) et | 1 i en √ 1 2 ( | 0 i − | 1 i ). Cette trans- formationintroduitdoncunesuperpositiond’´etatsa`partird’uneentre´e classique. 1.3St`emescomp´ ys oses L’espacevectorieldese´tatsd’unsyste`mephysiquecompose´desous syst`emesestleproduittensorieldesespacesdese´tatsdessoussyste`mes. Ainsil’espacedese´tatsdedeuxsyst`emesdontl’espacedes´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 l’espacege´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´efinieparl’e´tatdesuperpo- sition,etensuitel’e´tatdusyst`emeseraexactementceluiquia´ete´mesur´e. Ainsilamesurefaite´voluerlesyste`medemanie`reirre´versible. 3