Une méthode pour étudier certains problèmes d'interaction

Saleem Mohammed Ridha Taha

Mehdi Mhalla

Nous presentons dans ce travail plusieurs resultats dans differents domaines de l'information quantique. Apres une premiere partie ou nous proposons une introduction au domaine, nous proposons des caracterisations simples et efficaces du phenomene de l'intrication des etats purs. Les deux formes de separabilite etudiees sont la separabilite totale et la p-q separabilite. Ces caracterisations nous ont permis de donner des algorithmes optimaux de detection de la separabilite ayant un gain quadratrique par rapport aux methodes connues. La troisieme partie s'interesse aux jeux quantiques. Nous presentons tout d'abord une analyse fine des jeux octaux classiques et donnons une strategie optimale pour le jeu des dominos. Nous proposons ensuite une quantisation de certains jeux combinatoires, definissant ainsi la famille des jeux octaux quantiques. Nous presentons ainsi un modele formel permettant de parler des jeux quantiques a information totale et proposons une approche qui utilise des pieges pour des jeux quantiques tres etudies, appeles jeux de des a distance. La derniere partie etudie des problemes d'optimisation, en developpant pour cela des outils optimaux de recherche de minima. Ces outils nous ont permis d'analyser la complexite en requetes de certains problemes de graphes. Nous avons ainsi trouve des algorithmes quantiques pour les problemes de connectivite, forte connectivite, arbre couvrant de poids minimal et plus courts chemins a une source donnee. Puis, nous avons prouve leur optimalite en utilisant des techniques de bornes inferieures, determinant ainsi les limites du facteur de gain qu'offre l'informatique quantique pour resoudre ce probleme.

Anthony Piermattéo

Marc Kaplan

La complexité de la communication a été introduite en 1979 par Andrew Chi-Chi Yao. Elle est depuis devenue l'un des modèles de calcul les plus étudiés. L'objectif de celle-ci est d'étudier des problèmes dont les entrées sont distribuées entre plusieurs joueurs, en quantifiant la communication que ceux-ci doivent échanger. Nous utilisons d'abord la complexité de Kolmogorov, une caractérisation algorithmique de l'aléatoire, pour prouver des bornes inférieures sur la complexité de la communication. Notre méthode constitue une généralisation de la méthode d'incompressibilité. L'avantage de cette approche est de mettre en valeur la nature combinatoire des preuves. Nous étudions ensuite la simulation des distributions de probabilité causales avec de la communication. Ce modèle généralise la complexité de la communication traditionnelle et comprend en particulier les distributions quantiques. Nous montrons pour ce problème des bornes inférieures et supérieures. Dans le cas des fonctions booléennes, la borne inférieure que nous proposons est équivalente aux normes de factorisation, une puissante méthode introduite par Linial et Shraibman en 2006. Enfin, nous étudions la complexité en boîte non-locale. Cette ressource a été introduite par Popescu et Rohrlich pour étudier la non-localité. Le problème est de quantifier le nombre de boîtes nécessaire et suffisant pour calculer une fonction ou simuler une distributions. Nous donnons encore des bornes inférieures et supérieures pour ces problèmes, ainsi que des applications à l'évaluation sécurisée, un problème cryptographique très important.

Manuel Endres

Nikolaj A. Veniaminov, KLOPP, Frédéric

On étudie la limite thermodynamique pour un système de particules quantiques en interaction dans un milieu aléatoire dans le formalisme de l'ensemble microcanonique. L'existence de la limite est démontrée pour l'énergie interne ainsi que pour l'entropie sous des conditions assez générales sur le modèle à une particule. Ensuite, la limite thermodynamique est étudiée pour le modèle des pièces à une dimension dans le cas de fermions et pour une densité de particules faible. On donne une caractérisation de l'état fondamental dans les termes des espaces fonctionnels; on démontre sa non dégénérescence presque sûre et on décrit sa fonction d'autocorrélation. Ces résultats permettent d'obtenir une estimée de l'énergie fondamentale par particule comme une fonction de la densité de particules dans la limite thermodynamique. Enfin, on fait une remarque sur l'énergie libre dans l'ensemble grand canonique et on considère certains marginales (comme la densité à une particule) de l'état fondamental.