Cette these s'inscrit dans le contexte du calcul distribue sur les reseaux, et, plus particulierement, sur les aspects de localite qui apparaissent dans ce cadre. Par l'etude systematique des problemes de decision, nous introduisons les classes de com¬plexite ULD et UNLD pour la decision et la verification locale, et presentons des resultats de separation decrivant une hierarchie impliquant d'autres classes relatives a la litterature de la decision locale. Ces resultats sont accompagnes de la classifica¬tion de plusieurs problemes distribues selon la hierarchie introduite. Nous examinons et discutons dans ce cadre deux ingredients ayant un role cle dans la decision et la verification locale : la fonction d'interpretation des sorties, et l'identification des noeuds du reseau. Nous isolons egalement dans cette these l'aspect de la localite en l'etudiant sous le prisme du modele non-signalling, qui bien que n'etant pas un modele realiste, offre des possibilites theoriques interessantes, notamment sur la derivation de bornes inferieures pour le calcul distribue quantique, sans avoir a manipuler les objets de cette theorie. Finalement, en nous placant a la limite extreme des contraintes de localite, nous considerons la classe particuliere de jeux a deux joueurs en l'absence de communication, et examinons les limites du calcul distribue quantique pour cette classe de jeux.
Cette these s'inscrit dans le contexte du calcul distribue sur les reseaux, et, plus particulierement, sur les aspects de localite qui apparaissent dans ce cadre. Par l'etude systematique des problemes de decision, nous introduisons les classes de com¬plexite ULD et UNLD pour la decision et la verification locale, et presentons des resultats de separation decrivant une hierarchie impliquant d'autres classes relatives a la litterature de la decision locale. Ces resultats sont accompagnes de la classifica¬tion de plusieurs problemes distribues selon la hierarchie introduite. Nous examinons et discutons dans ce cadre deux ingredients ayant un role cle dans la decision et la verification locale : la fonction d'interpretation des sorties, et l'identification des noeuds du reseau. Nous isolons egalement dans cette these l'aspect de la localite en l'etudiant sous le prisme du modele non-signalling, qui bien que n'etant pas un modele realiste, offre des possibilites theoriques interessantes, notamment sur la derivation de bornes inferieures pour le calcul distribue quantique, sans avoir a manipuler les objets de cette theorie. Finalement, en nous placant a la limite extreme des contraintes de localite, nous considerons la classe particuliere de jeux a deux joueurs en l'absence de communication, et examinons les limites du calcul distribue quantique pour cette classe de jeux.
Cette thèse suit un plan à deux parties. Le point de départ en est la notion de résistance à la localisation, qui est importante en calcul distribué quantique.Dans la première partie, qui est plutôt théorique, nous retraçons l’historique de certaines notions et résultats en information quantique et en calcul distribué, plus précisément le phénomène d’intrication et la condition non-signalling en information quantique et le modèle LOCAL et le problème de coloration en calcul distribué. Ensuite, nous évoquons le modèle φ-LOCAL, développé en 2009 comme adaptation de la condition non-signalling au modèle LOCAL dans le but d’étudier l’existence d’algorithmes distribués quantiques. Finalement, nous soulignons quelques limites du modèle φ-LOCAL à l’aide des notions de consistance globale et de consistance locale, et nous présentons une version plus adéquate de ce modèle.La deuxième partie comporte les principaux résultats techniques obtenus au cours de cette thèse dans le domaine de la théorie des probabilités. Nous introduisons la notion de k-localisabilité qui est une traduction probabiliste du modèle φ-LOCAL. Nous montrons en quoi cette notion est proche, mais plus faible, que la notion de k-dépendance, largement étudiée dans la littérature probabiliste. Nous évoquons des résultats récents autour de la coloration 1-dépendante du chemin qui permettent de conclure au sujet de la coloration 1-localisable du chemin : elle est possible dès qu’il y a plus de quatre couleurs. Dans la suite, nous traitons la question de la possibilité de la coloration 1-localisable du chemin à l’aide de trois couleurs : nous verrons qu’elle n’est pas possible. Pour répondre à cette question, nous avons eu recours à la programmation linéaire et à la combinatoire : en particulier, nous démontrons un théorème qui donne la solution explicite d’un programme linéaire ayant une forme particulière, ainsi qu’une formule pour les nombres de Catalan.
Cette thèse suit un plan à deux parties. Le point de départ en est la notion de résistance à la localisation, qui est importante en calcul distribué quantique.Dans la première partie, qui est plutôt théorique, nous retraçons l’historique de certaines notions et résultats en information quantique et en calcul distribué, plus précisément le phénomène d’intrication et la condition non-signalling en information quantique et le modèle LOCAL et le problème de coloration en calcul distribué. Ensuite, nous évoquons le modèle φ-LOCAL, développé en 2009 comme adaptation de la condition non-signalling au modèle LOCAL dans le but d’étudier l’existence d’algorithmes distribués quantiques. Finalement, nous soulignons quelques limites du modèle φ-LOCAL à l’aide des notions de consistance globale et de consistance locale, et nous présentons une version plus adéquate de ce modèle.La deuxième partie comporte les principaux résultats techniques obtenus au cours de cette thèse dans le domaine de la théorie des probabilités. Nous introduisons la notion de k-localisabilité qui est une traduction probabiliste du modèle φ-LOCAL. Nous montrons en quoi cette notion est proche, mais plus faible, que la notion de k-dépendance, largement étudiée dans la littérature probabiliste. Nous évoquons des résultats récents autour de la coloration 1-dépendante du chemin qui permettent de conclure au sujet de la coloration 1-localisable du chemin : elle est possible dès qu’il y a plus de quatre couleurs. Dans la suite, nous traitons la question de la possibilité de la coloration 1-localisable du chemin à l’aide de trois couleurs : nous verrons qu’elle n’est pas possible. Pour répondre à cette question, nous avons eu recours à la programmation linéaire et à la combinatoire : en particulier, nous démontrons un théorème qui donne la solution explicite d’un programme linéaire ayant une forme particulière, ainsi qu’une formule pour les nombres de Catalan.
La théorie de la complexité de communication étudie le coût minimum de communication nécessaire pour évaluer une fonction lorsque les entrées sont distribuées parmi plusieurs entités. Deux modèles qui sont bien étudiés sont les modèles d'erreur bornée et d'erreur non-bornée, où les entités peuvent profiter de l'aléatoire pour faciliter leurs calculs. Les premiers résultats dans ce domaine montrèrent que la fonction Égalité peut être calculée avec un coût minimal dans des deux modèles aléatoires, tandis qu'elle atteint le coût maximal dans le modèle déterministe. Ceci démontre le pouvoir de l'aléatoire dans la communication, par opposition à des autres modèles de computation, tels que les arbres de décision.Le fait que l'Égalité présente la séparation maximale entre les efficacités de communication aléatoire et déterministe incite la recherche d'un modèle hybride de communication : un modèle déterministe avec accès à un oracle d'Égalité, où l'on remplace la sélection au hasard avec un pouvoir omniscient qui calcule l'Égalité de manière efficace. Un résultat clé concernant ce modèle d'oracle démontre que le pouvoir de la sélection aléatoire n'est pas entièrement reflété par la capacité de calculer l'Égalité efficacement, ce qui fait ce modèle intéressant à étudier.Un sujet fondamental dans la théorie de la complexité est la comparaison des puissances relatives des différents modèles. Les résultats sur les puissances peuvent être classifiés en trois catégories principales : séparation — quand un modèle est plus fort qu'un autre, inclusion — quand le critère d'efficacité d'un modèle est contenu dans celui d'un autre, et structure — quand les fonctions que l'on peut calculer dans un modèle possèdent certaines propriétés qui correspondent à la simplicité de calcul.Malgré de la recherche extensive dans le domaine, plusieurs questions fondamentales à propos de ces trois modèles ne sont toujours pas résolues. Le manque d'exemples explicites limite sévèrement notre compréhension des résultats structurels. De plus, beaucoup des techniques actuellement connues pour établir des bornes inférieures sont trop faibles pour caractériser structurellement les fonctions avec complexité uniformément bornée.Cette thèse présente de nouveaux résultats de séparation et structurels dans la complexité de communication, ce qui représente un avancement vers la résolution de ces problèmes ouverts reliés aux régimes de coût constant. On démontre que nos résultats de séparation fournissent des nouvelles séparations au-delà de la théorie de la complexité de communication : ils impliquent des séparations dans les domaines de la théorie d'apprentissage et la théorie de la complexité des requêtes
Le développement de machines quantiques de tailles modestes accessibles en ligne permet aujourd'hui de réaliser des expériences sur des calculateurs à distance. L'avantage de l'informatique quantique repose sur des phénomènes strictement non classiques, tels que la superposition et l'intrication, qui sont des ressources maintenant bien connues. Le phénomène non-classique de la contextualité est peut-être moins bien établi bien qu'il ouvre aussi des perspectives très intéressntes à travers de nombreuses applications telles que la cryptographie quantique, les codes d'accès aléatoires, les codes correcteurs d'erreurs et l'avantage du coût de la mémoire pour la simulation des mesures quantiques. L'objectif de cette thèse est triple : développer de nouveaux tests résistants au bruit pour démontrer la contextualité avec des ordinateurs quantiques bruités d'échelle intermédiaire ; concevoir des algorithmes quantiques pour calculer les limites classiques de ces tests, avec une meilleure complexité par rapport aux algorithmes existants ; interpreter les invariants algébriques, utilisés pour distinguer les classes d'intrication, en termes d'observables à base d'opérateurs de Pauli. À ces fins, l'utilisation de configurations géométriques telles que les espaces polaires symplectiques et leurs sous-géométries est largement exploitée, permettant d'établir un lien solide entre le domaine, relativement ancien des géométries finies, et les concepts plus récents de la théorie de l'information quantique. Pour le premier objectif, nous utilisons l'apport de la géométrie pour fournir des tests de contextualité qui violent largement les limites classiques sur tous les ordinateurs quantiques IBM. Ces tests démontrent empiriquement l'absence de modèles à variables cachées non contextuelles décrivant le système sous-jacent. C'est un résultat d'intérêt ontologique. Plus précisément, il s'agit de la première violation connue du jeu de pseudotélépathie de Mermin sur de telles machines, et des plus grandes violations du test de Rio Negro. Concernant le deuxième objectif, nous nous appuyons sur les symétries de nos géométries pour construire un algorithme quantique basé sur l'algorithme de recherche de Grover. Cet algorithme identifie une affectation optimale de variables cachées classiques avec une complexité comparable à l'algorithme de Grover. Un tel avantage algorithmique est intéressant dans une grande famille de problèmes, connus sous le nom de Max Lin 2, où plusieurs contraintes sur un ensemble de données ne peuvent pas être satisfaites simultanément. Ainsi, l'étude de la contextualité - qui peut être vue comme une limitation de la satisfaction logique pour décrire les systèmes physiques - peut apporter de nouvelles perspectives à des problèmes où la satisfaction d'instruction logique simultanée n'est pas viable. Enfin, pour le troisième objectif, nous proposons de nombreuses connexions entre les géométries finies et les invariants algébriques, en commençant par des liens entre les quadrangles généralisés et les invariants cubiques de Cartan, puis en montrant comment les géométries maximalement mixtes permettent de reconstruire les polynômes de Mermin, et finalement en décrivant les sous-ensembles minimaux d'opérateurs de Pauli qui permettent de calculer les hyperdéterminants. On peut ainsi, grâce à ces invariants, identifier la classe d'intrication de systèmes de qubits N=2,3,4 par des mesures sans avoir besoin d'une tomographie complète du système. En résumé dans cette thèse, nous abordons une grande variété de questions à l'intersection de la géométrie finie et de l'informatique quantique - de la conception de tests de contextualité à l'étude de la non-localité à travers des invariants algébriques en passant par le calcul quantique de bornes classiques. Les idées proposées dans ce travail pourront être utiles à la fois pour l'étude des fondements de la mécanique quantique et pour son application à l'informatique quantique.
Les théories physiques classiques peuvent être interpretées comme représentant le monde en termes d'intéractions causales à la fois locales et déterministiques entre des systèmes characterisés par des propriétés bien définies. Il est bien connu que la mécanique quantique orthodoxe, qui se trouve être une de nos théories les mieux confirmées, ne peut pas être interprétée dans les termes du cadre décrit ci-dessus. Au début des années soixante, John Bell a démontré que toute théorie représentant son domaine dans les termes du cadre classique ci-dessus satisfait une série d'inégalités, les inégalités de Bell. Certains physiciens ont développé des théories alternatives à la théorie quantique orthodoxe, théories dont les interprétations associées abandonnent au moins une des charactéristiques du cadre classique. Les philosophes s'efforcent d'interpreter ce resultat de la physique contemporaine, i.e. s'efforcent de comprendre à quoi peut ressembler le monde s'il est vrai que les interactions entre les systèmes physiques sont soit non-locales, soit non-déterministiques, ou bien que ces systèmes physiques ne possèdent pas de propriétés définies. Cette ligne de pensée a atteint son apogée avec la "métaphysique expérimentale" qui s'est développée après que la violation des inégalités de Bell par l'expérience a été observée. L'interprétation orthodoxe est que les expériences de type Bell nous forcent à accepter certaines formes d'interactions non-locales, et peut- être non causales, au niveau fondamental. Dans cette thèse, j'évalue dans quelle mesure l'investigation philosophique de nos meilleures théories scientifiques peut nous aider à décider de ce que peut être le monde au niveau fondamental. J'étudie cette question en considérant le domaine quantique, et en particulier les phénomènes de type Bell. Mes conclusions pointent dans la direction d'une vue plus modeste du rôle possible de la philosophie de la physique que celle que les programmes de métaphysique expérimentale suggèrent. Dans une première partie, j'étudie le rôle que la philosophie de la physique peut légitimement jouer dans le développement et l'évaluation des différentes theories quantiques. Je soutiens que le rôle de la philosophie de la physique ne consiste pas à imposer des critères d'acceptabilité pour les théories physiques en plus des critères usuels de cohérence interne et d'adéquation empirique. Un rôle à la fois important et légitime que peut jouer la philosophie de la physique consiste à distinguer clairement, pour nos théories et leurs interprétations, ce qui est imposé par les phénomènes et les théories de ce que relèvent de nos choix et préférences. Je soutiens enfin qu'un tel travail d'analyse peut se faire sur la base de l'analyse structurelle de nos théories et de nos modèles de données. Dans la seconde partie de la thèse, j'étudie spécifiquement le cas de l'interprétation des théorèmes de Bell et des expériences associées. J'évalue systématiquement l'interprétation orthodoxe selon laquelle les résultats de ces expériences nous force à accepter une forme "bénigne" de non-localité, bénigne" parce que de type non-causal. Je montre que l'interprétation orthodoxe comprends trois thèses différentes, la première portant sur la question de la localité, la seconde portant sur la question de la causalité et la troisième concernant le holisme. Je fournis des cadres théoriques rigoureux afin d'évaluer ces trois thèses. Le résultat de mon analyse concernant la question de la localité est que l'interprétation orthodoxe peut être défendue. En revanche, concernant les questions de causalité, aucun des cadres théoriques existant ne permet de soutenir l'interprétation orthodoxe, si cette dernière est comprise dans sa version forte de métaphysique expérimentale. Dans les deux cas cependant, une version faible peut être défendue. En particulier, un résultat important de ma thèse est que l'interprétation orthodoxe peut être défendue rigoureusement au niveau empirique.
Cette these traite du probleme de la minimisation d'une fonction pseudo-booleenne quadratique (f. P. B. Q. ) sous des contraintes lineaires et de son application au probleme de placement de taches sur les systemes distribues ainsi qu'au probleme de partition de graphes. Nous proposons le calcul de plusieurs bornes inferieures. Dans le cas de contraintes lineaires de transport, nous proposons une reduction de la fonction objectif et le calcul d'une borne inferieure par implications logiques. Nous utilisons cette borne inferieure pour la resolution d'un probleme de placement de taches avec contraintes de ressources. Nous resolvons des problemes de l'ordre de 20 taches et 3 processeurs. Dans le cas de contraintes lineaires quelconques, nous calculons une borne inferieure par une decomposition optimale, sous certaines hypotheses, de la fonction objectif. Nous appliquons le calcul de cette borne au probleme de placement de taches sans contraintes de ressources. Une etude experimentale montre la bonne qualite de cette borne: nous obtenons des ecarts relatifs, avec la valeur exacte du probleme, inferieurs a 2% pour des problemes comportant 60 taches et 15 processeurs. Nous proposons aussi le calcul d'une borne inferieure pour un probleme de partition de graphes. Cette borne est obtenue par un algorithme de coupes polyedriques. Une etude experimentale montre la bonne qualite de cette borne pour certaines classes de problemes. Dans le cadre de la minimisation d'une f. P. B. Q. Sous une contrainte lineaire, nous proposons le calcul d'une borne inferieure par un programme lineaire continu. Nous prouvons que cette borne est la meilleure valeur que l'on puisse obtenir sous certaines hypotheses. Ce resultat se situe dans le prolongement des travaux de Hammer, Hansen et Simeone, dans le cas sans contraintes, sur le toit dual. Nous terminons par une etude theorique comparative de ces differentes bornes