Algorithmes et complexité quantiques et probabilistes – QRAC

Notre projet consiste à réunir les forces des experts des deux communautés du calcul probabiliste et quantique. Notre objectif principal consister à contribuer significativement dans les domaines du calcul probabiliste et quantique, mais aussi, en réunissant nos compétences, à assurer un transfert de techniques du calcul probabiliste au calcul quantique, et vice-versa. Pour le calcul probabiliste, nous nous concentrons essentiellement sur des modèles de masses de données dont l'accès est restreint, et pour lesquels les techniques probabilistes et parfois d'approximation sont des outils fondamentaux. Nous couverons les domaines du test approché de propriétés (Property Testing), des algorithmes de flots (Streaming Algorithms), des algorithmes en ligne (Online Algorithms), et de la théorie algorithmique des jeux (Algorithmic Game Theory). Pour le calcul quantique, nous continuerons de développer des algorithmes, en particulier pour le problème du sous-groupe caché, les problèmes de vecteurs dans les réseaux, mais aussi sur des algorithmes élaborés à partir des marches quantiques. Nous étudierons aussi les bornes inférieures pour la complexité en requêtes quantiques, la théorie de l'information quantique et la communication quantique. A l'intersection des modèles de calcul quantique et probabiliste, notre objectif est d'approfondir l'étude des codes localement décodables, la complexité de la communication, et les méthodes de bornes inférieures pour la taille des circuits.