Échantillonnage des distributions continues non uniformes en précision arbitraire et protocole pour l'échantillonnage exact distribué des distributions discrètes quantiques

Abstract

La thèse est divisée principalement en deux parties. La première partie regroupe les chapitres 2 et 3. La deuxième partie regroupe les chapitres 4 et 5. La première partie concerne l'échantillonnage de distributions continues non uniformes garantissant un niveau fixe de précision. Knuth et Yao démontrèrent en 1976 comment échantillonner exactement n'importe quelle distribution discrète en n'ayant recours qu'à une source de bits non biaisés indépendants et identiquement distribués. La première partie de cette thèse généralise en quelque sorte la théorie de Knuth et Yao aux distributions continues non uniformes, une fois la précision fixée. Une borne inférieure ainsi que des bornes supérieures pour des algorithmes génériques comme l'inversion et la discrétisation figurent parmi les résultats de cette première partie. De plus, une nouvelle preuve simple du résultat principal de l'article original de Knuth et Yao figure parmi les résultats de cette thèse. La deuxième partie concerne la résolution d'un problème en théorie de la complexité de la communication, un problème qui naquit avec l'avènement de l'informatique quantique. Étant donné une distribution discrète paramétrée par un vecteur réel de dimension N et un réseau de N ordinateurs ayant accès à une source de bits non biaisés indépendants et identiquement distribués où chaque ordinateur possède un et un seul des N paramètres, un protocole distribué est établi afin d'échantillonner exactement ladite distribution.

The thesis is divided mainly into two parts. Chapters 2 and 3 contain the first part. Chapters 4 and 5 contain the second part. The first part is about sampling non uniform continuous distributions with a given level of precision. Knuth and Yao showed in 1976 how to sample exactly any discrete distribution using a source of unbiased identically and independently distributed bits. The first part of this thesis extends the theory of Knuth and Yao to non uniform continuous distributions once the precision is fixed. A lower bound and upper bounds for generic algorithms based on discretization or inversion are given as well. In addition, a new simple proof of the original result of Knuth and Yao is given here. The second part is about the solution of a problem in communication complexity that originally appeared within the field of quantum information science. Given a network of N computers with a server capable of generating random unbiased bits and a parametric discrete distribution with a vector of N real parameters where each computer owns one and only one parameter, a protocol to sample exactly the distribution in a distributed manner is given here.