Complexité de la communication sur un canal avec délai

Nous introduisons un nouveau modèle de la communication à deux parties dans lequel nous nous intéressons au temps que prennent deux participants à effectuer une tâche à travers un canal avec délai d. Nous établissons quelques bornes supérieures et inférieures et comparons ce nouveau modèle aux modèles de communication classiques et quantiques étudiés dans la littérature. Nous montrons que la complexité de la communication d’une fonction sur un canal avec délai est bornée supérieurement par sa complexité de la communication modulo un facteur multiplicatif d/ lg d. Nous présentons ensuite quelques exemples de fonctions pour lesquelles une stratégie astucieuse se servant du temps mort confère un avantage sur une implémentation naïve d’un protocole de communication optimal en terme de complexité de la communication. Finalement, nous montrons qu’un canal avec délai permet de réaliser un échange de bit cryptographique, mais que, par lui-même, est insuffisant pour réaliser la primitive cryptographique de transfert équivoque.

From Classical to Quantum Secret Sharing

Dans ce mémoire, nous nous pencherons tout particulièrement sur une primitive cryptographique connue sous le nom de partage de secret. Nous explorerons autant le domaine classique que le domaine quantique de ces primitives, couronnant notre étude par la présentation d’un nouveau protocole de partage de secret quantique nécessitant un nombre minimal de parts quantiques c.-à-d. une seule part quantique par participant. L’ouverture de notre étude se fera par la présentation dans le chapitre préliminaire d’un survol des notions mathématiques sous-jacentes à la théorie de l’information quantique ayant pour but primaire d’établir la notation utilisée dans ce manuscrit, ainsi que la présentation d’un précis des propriétés mathématique de l’état de Greenberger-Horne-Zeilinger (GHZ) fréquemment utilisé dans les domaines quantiques de la cryptographie et des jeux de la communication. Mais, comme nous l’avons mentionné plus haut, c’est le domaine cryptographique qui restera le point focal de cette étude. Dans le second chapitre, nous nous intéresserons à la théorie des codes correcteurs d’erreurs classiques et quantiques qui seront à leur tour d’extrême importances lors de l’introduction de la théorie quantique du partage de secret dans le chapitre suivant. Dans la première partie du troisième chapitre, nous nous concentrerons sur le domaine classique du partage de secret en présentant un cadre théorique général portant sur la construction de ces primitives illustrant tout au long les concepts introduits par des exemples présentés pour leurs intérêts autant historiques que pédagogiques. Ceci préparera le chemin pour notre exposé sur la théorie quantique du partage de secret qui sera le focus de la seconde partie de ce même chapitre. Nous présenterons alors les théorèmes et définitions les plus généraux connus à date portant sur la construction de ces primitives en portant un intérêt particulier au partage quantique à seuil. Nous montrerons le lien étroit entre la théorie quantique des codes correcteurs d’erreurs et celle du partage de secret. Ce lien est si étroit que l’on considère les codes correcteurs d’erreurs quantiques étaient de plus proches analogues aux partages de secrets quantiques que ne leur étaient les codes de partage de secrets classiques. Finalement, nous présenterons un de nos trois résultats parus dans A. Broadbent, P.-R. Chouha, A. Tapp (2009); un protocole sécuritaire et minimal de partage de secret quantique a seuil (les deux autres résultats dont nous traiterons pas ici portent sur la complexité de la communication et sur la simulation classique de l’état de GHZ).

La transformation des enquêtes policières due à l’influence des technologies : perspective d’une unité policière spécialisée en analyse judiciaire informatique

La popularité des technologies de l’information et des communications entraîne l’augmentation de la preuve retrouvée sous forme numérique lors d’enquêtes policières. Les organisations policières doivent innover afin d’analyser, gérer et tirer profit de cette preuve numérique. En réponse, elles ont constitué des unités spécialisées en criminalité technologique et en analyse judiciaire informatique. La présente étude utilise les théories de l’innovation afin de déterminer comment l’évolution des technologies et des tendances en matière de criminalité technologique influencent les enquêtes et les organisations policières. Cette recherche vise à augmenter les connaissances sur ces unités spécialisées en quantifiant et en qualifiant leur travail quotidien. Avec la collaboration d’une unité policière canadienne spécialisée en analyse judiciaire informatique, une analyse détaillée des demandes d’expertise adressées à leur service a été effectuée. Les résultats indiquent une augmentation de la preuve numérique avec la prévalence de certaines formes de criminalité et de certains appareils électroniques. Les facteurs influençant le délai de traitement sont soulignés ainsi que les stratégies mises de l’avant afin de gérer efficacement l’accroissement des demandes de service. Finalement, des entrevues ont été menées avec certains membres de l’équipe afin de mettre en lumière les défis et les enjeux relatifs à l’implantation et au fonctionnement d’une telle unité. Les principaux enjeux soulevés concernent les environnements technologiques et juridiques, la formation du personnel, la gestion des ressources et les priorités organisationnelles.

La programmation informatique dans la recherche et la formation en mathématiques au niveau universitaire

Une étude récente auprès de 302 mathématiciens canadiens révèle un écart intriguant : tandis que 43% des sondés utilisent la programmation informatique dans leur recherche, seulement 18% indiquent qu'ils emploient cette technologie dans leur enseignement (Buteau et coll., 2014). La première donnée reflète le potentiel énorme qu'a la programmation pour faire et apprendre des mathématiques. La deuxième donnée a inspiré ce mémoire : pourquoi existe-t-il un tel écart ? Pour répondre à cette question, nous avons mené une étude exploratoire qui cherche à mieux comprendre la place de la programmation dans la recherche et la formation en mathématiques au niveau universitaire. Des entrevues semi-dirigées ont été conduites avec 14 mathématiciens travaillant dans des domaines variés et à différentes universités à travers le pays. Notre analyse qualitative nous permet de décrire les façons dont ces mathématiciens construisent des programmes informatiques afin d'accomplir plusieurs tâches (p.e., simuler des phénomènes réels, faire des mathématiques « expérimentales », développer de nouveaux outils puissants). Elle nous permet également d'identifier des moments où les mathématiciens exposent leurs étudiants à certains éléments de ces pratiques en recherche. Nous notons toutefois que les étudiants sont rarement invités à concevoir et à écrire leurs propres programmes. Enfin, nos participants évoquent plusieurs contraintes institutionnelles : le curriculum, la culture départementale, les ressources humaines, les traditions en mathématiques, etc. Quelques-unes de ces contraintes, qui semblent limiter l'expérience mathématique des étudiants de premier cycle, pourraient être revues.

Interactive quantum information theory

La théorie de l'information quantique s'est développée à une vitesse fulgurante au cours des vingt dernières années, avec des analogues et extensions des théorèmes de codage de source et de codage sur canal bruité pour la communication unidirectionnelle. Pour la communication interactive, un analogue quantique de la complexité de la communication a été développé, pour lequel les protocoles quantiques peuvent performer exponentiellement mieux que les meilleurs protocoles classiques pour certaines tâches classiques. Cependant, l'information quantique est beaucoup plus sensible au bruit que l'information classique. Il est donc impératif d'utiliser les ressources quantiques à leur plein potentiel. Dans cette thèse, nous étudions les protocoles quantiques interactifs du point de vue de la théorie de l'information et étudions les analogues du codage de source et du codage sur canal bruité. Le cadre considéré est celui de la complexité de la communication: Alice et Bob veulent faire un calcul quantique biparti tout en minimisant la quantité de communication échangée, sans égard au coût des calculs locaux. Nos résultats sont séparés en trois chapitres distincts, qui sont organisés de sorte à ce que chacun puisse être lu indépendamment. Étant donné le rôle central qu'elle occupe dans le contexte de la compression interactive, un chapitre est dédié à l'étude de la tâche de la redistribution d'état quantique. Nous prouvons des bornes inférieures sur les coûts de communication nécessaires dans un contexte interactif. Nous prouvons également des bornes atteignables avec un seul message, dans un contexte d'usage unique. Dans un chapitre subséquent, nous définissons une nouvelle notion de complexité de l'information quantique. Celle-ci caractérise la quantité d'information, plutôt que de communication, qu'Alice et Bob doivent échanger pour calculer une tâche bipartie. Nous prouvons beaucoup de propriétés structurelles pour cette quantité, et nous lui donnons une interprétation opérationnelle en tant que complexité de la communication quantique amortie. Dans le cas particulier d'entrées classiques, nous donnons une autre caractérisation permettant de quantifier le coût encouru par un protocole quantique qui oublie de l'information classique. Deux applications sont présentées: le premier résultat général de somme directe pour la complexité de la communication quantique à plus d'une ronde, ainsi qu'une borne optimale, à un terme polylogarithmique près, pour la complexité de la communication quantique avec un nombre de rondes limité pour la fonction « ensembles disjoints ». Dans un chapitre final, nous initions l'étude de la capacité interactive quantique pour les canaux bruités. Étant donné que les techniques pour distribuer de l'intrication sont bien étudiées, nous nous concentrons sur un modèle avec intrication préalable parfaite et communication classique bruitée. Nous démontrons que dans le cadre plus ardu des erreurs adversarielles, nous pouvons tolérer un taux d'erreur maximal de une demie moins epsilon, avec epsilon plus grand que zéro arbitrairement petit, et ce avec un taux de communication positif. Il s'ensuit que les canaux avec bruit aléatoire ayant une capacité positive pour la transmission unidirectionnelle ont une capacité positive pour la communication interactive quantique. Nous concluons avec une discussion de nos résultats et des directions futures pour ce programme de recherche sur une théorie de l'information quantique interactive.

Théorème de Pleijel pour l'oscillateur harmonique quantique

L'objectif de ce mémoire est de démontrer certaines propriétés géométriques des fonctions propres de l'oscillateur harmonique quantique. Nous étudierons les domaines nodaux, c'est-à-dire les composantes connexes du complément de l'ensemble nodal. Supposons que les valeurs propres ont été ordonnées en ordre croissant. Selon un théorème fondamental dû à Courant, une fonction propre associée à la $n$-ième valeur propre ne peut avoir plus de $n$ domaines nodaux. Ce résultat a été prouvé initialement pour le laplacien de Dirichlet sur un domaine borné mais il est aussi vrai pour l'oscillateur harmonique quantique isotrope. Le théorème a été amélioré par Pleijel en 1956 pour le laplacien de Dirichlet. En effet, on peut donner un résultat asymptotique plus fort pour le nombre de domaines nodaux lorsque les valeurs propres tendent vers l'infini. Dans ce mémoire, nous prouvons un résultat du même type pour l'oscillateur harmonique quantique isotrope. Pour ce faire, nous utiliserons une combinaison d'outils classiques de la géométrie spectrale (dont certains ont été utilisés dans la preuve originale de Pleijel) et de plusieurs nouvelles idées, notamment l'application de certaines techniques tirées de la géométrie algébrique et l'étude des domaines nodaux non-bornés.

Développement d’une méthode bio-informatique permettant de relier les gènes aux métabolites

L’objectif de ce projet était de faire le lien entre gènes et métabolites afin d’éventuellement proposer des métabolites à mesurer en lien avec la fonction de gènes. Plus particulièrement, nous nous sommes intéressés aux gènes codant pour des protéines ayant un impact sur le métabolisme, soit les enzymes qui catalysent les réactions faisant partie intégrante des voies métaboliques. Afin de quantifier ce lien, nous avons développé une méthode bio-informatique permettant de calculer la distance qui est définie comme le nombre de réactions entre l’enzyme encodée par le gène et le métabolite dans la carte globale du métabolisme de la base de données Kyoto Encyclopedia of Genes and Genomes (KEGG). Notre hypothèse était que les métabolites d’intérêt sont des substrats/produits se trouvant à proximité des réactions catalysées par l’enzyme encodée par le gène. Afin de tester cette hypothèse et de valider la méthode, nous avons utilisé les études d’association pangénomique combinées à la métabolomique (mGWAS) car elles rapportent des associations entre variants génétiques, annotés en gènes, et métabolites mesurés. Plus précisément, la méthode a été appliquée à l’étude mGWAS par Shin et al. Bien que la couverture des associations de Shin et al. était limitée (24/299), nous avons pu valider de façon significative la proximité entre gènes et métabolites associés (P<0,01). En somme, cette méthode et ses développements futurs permettront d’interpréter de façon quantitative les associations mGWAS, de prédire quels métabolites mesurer en lien avec la fonction d’un gène et, plus généralement, de permettre une meilleure compréhension du contrôle génétique sur le métabolisme.

Processus causal et intrication quantique

La notion de causalité repose sur une grande prétention : rendre intelligibles l’origine, la constitution et le devenir du monde. On lui attribue donc une portée universelle : tout événement a une cause. La majeure partie des débats philosophiques sur la causalité a concerné nos jugements intuitifs selon deux types de conceptions causales, soit la conception probabiliste et la conception processuelle. Chacune d’elles fait face à d’importants obstacles conceptuels dont les principaux sont la préemption, l’inaboutissement (fizzling), la déconnexion et la méconnexion. Or, afin de rendre compte de certains phénomènes physiques et d’éviter le problème classique des régularités fallacieuses – comme quoi, par exemple, la chute du baromètre ne saurait être la cause de la tempête – l’approche processuelle est généralement privilégiée. Max Kistler (1998 ; 2006), entre autres, offre ainsi une théorie causale processuelle basée sur la notion de transfert d’énergie. Cependant, les cas paradigmatiques d’intrication quantique imposent de sérieuses contraintes aux approches processuelles, dont celle de Kistler.