Show item record

dc.contributor.advisorBrassard, Gilles
dc.contributor.advisorTapp, Alain
dc.contributor.authorLamontagne, Philippe
dc.date.accessioned2013-09-18T15:45:29Z
dc.date.availableNO_RESTRICTIONfr
dc.date.available2013-09-18T15:45:29Z
dc.date.issued2013-06-03
dc.date.submitted2013-01
dc.identifier.urihttp://hdl.handle.net/1866/9827
dc.subjectAmplification de l'amplitudefr
dc.subjectTest de propriétéfr
dc.subjectTest de linéaritéfr
dc.subjectTest d'homomorphismefr
dc.subjectTest de symétriefr
dc.subjectTest de quasi-symétriefr
dc.subjectVariancefr
dc.subjectComplexité en requêtesfr
dc.subjectQuantum amplitude amplificationfr
dc.subjectProperty testingfr
dc.subjectLinearity testingfr
dc.subjectHomomorphism testingfr
dc.subjectSymmetry testingfr
dc.subjectQuasi-symmetry testingfr
dc.subjectQuery complexityfr
dc.subject.otherApplied Sciences - Computer Science / Sciences appliqués et technologie - Informatique (UMI : 0984)fr
dc.titleAmplification de l'amplitude : analyse et applicationsfr
dc.typeThèse ou mémoire / Thesis or Dissertation
etd.degree.disciplineInformatiquefr
etd.degree.grantorUniversité de Montréalfr
etd.degree.levelMaîtrise / Master'sfr
etd.degree.nameM. Sc.fr
dcterms.abstractCe mémoire étudie l'algorithme d'amplification de l'amplitude et ses applications dans le domaine de test de propriété. On utilise l'amplification de l'amplitude pour proposer le plus efficace algorithme quantique à ce jour qui teste la linéarité de fonctions booléennes et on généralise notre nouvel algorithme pour tester si une fonction entre deux groupes abéliens finis est un homomorphisme. Le meilleur algorithme quantique connu qui teste la symétrie de fonctions booléennes est aussi amélioré et l'on utilise ce nouvel algorithme pour tester la quasi-symétrie de fonctions booléennes. Par la suite, on approfondit l'étude du nombre de requêtes à la boîte noire que fait l'algorithme d'amplification de l'amplitude pour amplitude initiale inconnue. Une description rigoureuse de la variable aléatoire représentant ce nombre est présentée, suivie du résultat précédemment connue de la borne supérieure sur l'espérance. Suivent de nouveaux résultats sur la variance de cette variable. Il est notamment montré que, dans le cas général, la variance est infinie, mais nous montrons aussi que, pour un choix approprié de paramètres, elle devient bornée supérieurement.fr
dcterms.abstractThis thesis studies the quantum amplitude amplification algorithm and some of its applications in the field of property testing. We make use of the amplitude amplification algorithm to design an algorithm testing the linearity of Boolean functions which is more efficient than the previously best known quantum algorithm. We then generalize this new algorithm to test if a function between two finite abelian groups is a homomorphism. We improve on the previously best known algorithm for testing the symmetry of Boolean functions and use this new algorithm to test the quasi-symmetry of Boolean functions. Next, we further the study of the query complexity of the amplitude amplification algorithm for unknown initial amplitude. We give a rigorous description of the random variable representing the number of queries made by the algorithm and present the previously known result on its expected value upper bound. We then provide new results on the variance of this random variable. It is shown that, in the general case, the variance cannot be bounded above. We show, however, that it can be bounded for an appropriate choice of parameters.fr
dcterms.languagefrafr


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show item record