Show simple item record

dc.contributor.advisorZémor, Gilles
dc.contributor.advisorGavoille, Cyril
dc.contributor.authorKACHIGAR, Ghazal
dc.contributor.otherGavoille, Cyril
dc.contributor.otherMagniez, Frédéric
dc.contributor.otherPerdrix, Simon
dc.contributor.otherNechita, Ion
dc.date2019-12-10
dc.identifier.urihttp://www.theses.fr/2019BORD0339/abes
dc.identifier.uri
dc.identifier.urihttps://tel.archives-ouvertes.fr/tel-02462588
dc.identifier.nnt2019BORD0339
dc.description.abstractCette 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.
dc.description.abstractEnThis thesis is divided in two parts. Its starting point is the concept of resistance to localisation, an important concept in distributed quantum computing.In the first, theoretical part of this thesis, we go over the history of certain concepts and results in quantum information theory and distributed computing, such as the phenomenon of entanglement and the non-signalling condition in the first domain, and the LOCAL model and the colouring problem in the second domain. We then focus on the φ-LOCAL model, whose goal is to study the possibility of quantum distributed algorithms, and which was developedin 2009 by adapting the non-signalling condition to the LOCAL model. We introduce the concepts of global and local consistency in order to emphasise some shortcomings of this model. Finally, we present a more adequate version ofthe φ-LOCAL model.The second part of this thesis contains our major technical results in probability theory. We define the concept of k-localisability which is a probabilistic translation of the φ-LOCAL model. We show that this concept is close to but weaker than the concept of k-dependence which is well-studied in the probabilistic literature. We mention recent results concerning 1-dependent colouring of the path graph and the conclusion they allow us to reach with regards to 1-localisable colouring of the path graph : that it is possible with four or more colours. The rest of this part is dedicated to answering the question of the possibility of 1-localisable colouring of the path graph using three colours which we will show to be impossible. In answering this question we have made use of methods in linear programming and combinatorics. In particular, we prove a theorem on the explicit solution of a linear programming problem having a certain form, and a formula for the Catalan numbers.
dc.language.isofr
dc.subjectThéorie des probabilités
dc.subjectCombinatoire
dc.subjectInformation quantique
dc.subject.enProbability theory
dc.subject.enQuantum information theory
dc.subject.enCombinatorics
dc.titleQuestions de localisabilité pour le calcul distribué
dc.title.enOn localisability with applications to distributed computing
dc.typeThèses de doctorat
dc.contributor.jurypresidentMarckert, Jean-François
bordeaux.hal.laboratoriesInstitut de mathématiques de Bordeaux
bordeaux.hal.laboratoriesLaboratoire bordelais de recherche en informatique
bordeaux.type.institutionBordeaux
bordeaux.thesis.disciplineMathématiques Pures
bordeaux.ecole.doctoraleÉcole doctorale de mathématiques et informatique (Talence, Gironde ; 1991-....)
star.origin.linkhttps://www.theses.fr/2019BORD0339
dc.contributor.rapporteurMagniez, Frédéric
dc.contributor.rapporteurPerdrix, Simon
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.title=Questions%20de%20localisabilit%C3%A9%20pour%20le%20calcul%20distribu%C3%A9&rft.atitle=Questions%20de%20localisabilit%C3%A9%20pour%20le%20calcul%20distribu%C3%A9&rft.au=KACHIGAR,%20Ghazal&rft.genre=unknown


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record