Amplification de l'amplitude : analyse et applications

Abstract

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

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