La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Partagez cette publication

´ 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