De computatione quantica

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Multi-Prover and parallel repetition in non-classical interactive games

Depuis l’introduction de la mécanique quantique, plusieurs mystères de la nature ont trouvé leurs explications. De plus en plus, les concepts de la mécanique quantique se sont entremêlés avec d’autres de la théorie de la complexité du calcul. De nouvelles idées et solutions ont été découvertes et élaborées dans le but de résoudre ces problèmes informatiques. En particulier, la mécanique quantique a secoué plusieurs preuves de sécurité de protocoles classiques. Dans ce m´emoire, nous faisons un étalage de résultats récents de l’implication de la mécanique quantique sur la complexité du calcul, et cela plus précisément dans le cas de classes avec interaction. Nous présentons ces travaux de recherches avec la nomenclature des jeux à information imparfaite avec coopération. Nous exposons les différences entre les théories classiques, quantiques et non-signalantes et les démontrons par l’exemple du jeu à cycle impair. Nous centralisons notre attention autour de deux grands thèmes : l’effet sur un jeu de l’ajout de joueurs et de la répétition parallèle. Nous observons que l’effet de ces modifications a des conséquences très différentes en fonction de la théorie physique considérée.

Complexité raffinée du problème d'intersection d'automates

Le problème d'intersection d'automates consiste à vérifier si plusieurs automates finis déterministes acceptent un mot en commun. Celui-ci est connu PSPACE-complet (resp. NL-complet) lorsque le nombre d'automates n'est pas borné (resp. borné par une constante). Dans ce mémoire, nous étudions la complexité du problème d'intersection d'automates pour plusieurs types de langages et d'automates tels les langages unaires, les automates à groupe (abélien), les langages commutatifs et les langages finis. Nous considérons plus particulièrement le cas où chacun des automates possède au plus un ou deux états finaux. Ces restrictions permettent d'établir des liens avec certains problèmes algébriques et d'obtenir une classification intéressante de problèmes d'intersection d'automates à l'intérieur de la classe P. Nous terminons notre étude en considérant brièvement le cas où le nombre d'automates est fixé.

La représentation numérique à l'épreuve de la complexité du projet de territoire

Le projet de territoire n’aura jamais suscité autant de débats et de passions. Son devenir mobilise à bien des égards la construction collective d’un dessein se matérialisant par des formes qui informent des forces tout autant que par des forces qui investissent des formes lesquelles traduisent les valeurs du moment. Par conséquent, cette projection dans un avenir partagé amène des exigences sociales en matière d’édification du projet de territoire mettant à l’ordre du jour la complexité d’une telle entreprise. L’enchevêtrement d’actions et de logiques qui s’y opèrent et qui s’y expriment pour en élaborer, dans la plus grande incertitude, les contours d’un futur souhaité nous presse de s’y prononcer : la construction complexe d’un dessein territorial s’exhibant nous interpelle quant à son évaluation voire quant à sa reformulation. Parmi les modalités d’expression qui permettent une telle délibération, il y a l’énoncé visuel. Médiation discursive privilégiée, elle autorise l’élaboration et la mise en scène collective d’un devenir territorial possible. Or depuis quelques années, au couple projet / représentation, vient se superposer une autre médiation, celle du numérique. Portée par le développement des technologies de l’information, celle-ci s’invite dans le champ de l’édification du projet de territoire. En s’alliant avec la puissance de l’image, elle recompose les représentations d’un dessein territorial collectivement formulé, ouvrant un nouvel espace d’actions à l’occasion d’une démarche de planification. Démarche de plus en plus complexe. De surcroit, la présente recherche tient cette complexité non comme un mot «fourre-tout» ou une tare dont il faudrait se débarrasser, mais se résout à l’affronter en s’inscrivant dans un paradigme en pleine gestation, celui de la «pensée complexe». La fécondité autant conceptuelle qu’opératoire d’une telle inscription permettra de jeter un regard renouvelé sur une pratique à travers une de ses modalités discursives à la fois la plus manifeste et la moins questionnée, à savoir l’énoncé visuel. En fin de compte, les représentations notamment celles construites et véhiculées par le numérique sauront-elles rendre compte et relever le défi de l’édification collective d’un projet de territoire qui se pose dans toute sa complexité ? Telle est en substance le questionnement dont cette recherche s’attellera à apporter des éléments de réponse et à esquisser de nouvelles perspectives.

Approximation du calcul de la taille échantillonnale pour les tests à hypothèses multiples lorsque r parmis m hypothèses doivent être significatives

Généralement, dans les situations d’hypothèses multiples on cherche à rejeter toutes les hypothèses ou bien une seule d’entre d’elles. Depuis quelques temps on voit apparaître le besoin de répondre à la question : « Peut-on rejeter au moins r hypothèses ? ». Toutefois, les outils statisques pour répondre à cette question sont rares dans la littérature. Nous avons donc entrepris de développer les formules générales de puissance pour les procédures les plus utilisées, soit celles de Bonferroni, de Hochberg et de Holm. Nous avons développé un package R pour le calcul de la taille échantilonnalle pour les tests à hypothèses multiples (multiple endpoints), où l’on désire qu’au moins r des m hypothèses soient significatives. Nous nous limitons au cas où toutes les variables sont continues et nous présentons quatre situations différentes qui dépendent de la structure de la matrice de variance-covariance des données.

Will Kymlicka et les angles morts du libéralisme - Vers une théorie non-libérale du droit des minorités?

Will Kymlicka a formulé une théorie libérale du droit des minorités en arguant que l'on doit protéger les cultures minoritaires des influences extérieures, car, selon lui, ces cultures fournissent aux individus un contexte de choix significatif qui permet la prise de décision autonome. Il limite donc la portée de sa théorie aux minorités « culturelles », c'est-à-dire les minorités nationales et immigrantes, qui peuvent fournir ce contexte de choix significatif aux individus. Évidemment, les injustices vécues par ces deux types de minorités, aussi sévères soient-elles, n'épuisent pas les expériences d'injustices vécues par les membres de groupes minoritaires et minorisés (i.e. minorités sexuelles, femmes, Afro-Américains, etc.). On pourrait donc être tenté d'élargir la portée de la théorie du droit des minorités pour rendre compte de toutes les injustices vécues en tant que minorité. Toutefois, je défends la thèse selon laquelle cette extension est impossible dans le cadre d'une théorie libérale, car une de ses méthodes typiques, la « théorie idéale », limite la portée critique des thèses de Kymlicka et parce que l'autonomie individuelle a un caractère si fondamental pour les libéraux, qu'ils ne peuvent rendre compte du fait que certaines décisions individuelles autonomes peuvent contribuer à perpétuer des systèmes et des normes injustes.

A survey of graph and subgraph isomorphism problems

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Activation cérébrale en fonction de l'âge et de la complexité du traitement sémantique des mots par imagerie par résonance magnétique fonctionnelle

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Algorithmique et complexité des systèmes à compteurs

Réalisé en cotutelle avec l'École normale supérieure de Cachan – Université Paris-Saclay

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.

Key Agreement Against Quantum Adversaries

Key agreement is a cryptographic scenario between two legitimate parties, who need to establish a common secret key over a public authenticated channel, and an eavesdropper who intercepts all their messages in order to learn the secret. We consider query complexity in which we count only the number of evaluations (queries) of a given black-box function, and classical communication channels. Ralph Merkle provided the first unclassified scheme for secure communications over insecure channels. When legitimate parties are willing to ask O(N) queries for some parameter N, any classical eavesdropper needs Omega(N^2) queries before being able to learn their secret, which is is optimal. However, a quantum eavesdropper can break this scheme in O(N) queries. Furthermore, it was conjectured that any scheme, in which legitimate parties are classical, could be broken in O(N) quantum queries. In this thesis, we introduce protocols à la Merkle that fall into two categories. When legitimate parties are restricted to use classical computers, we offer the first secure classical scheme. It requires Omega(N^{13/12}) queries of a quantum eavesdropper to learn the secret. We give another protocol having security of Omega(N^{7/6}) queries. Furthermore, for any k>= 2, we introduce a classical protocol in which legitimate parties establish a secret in O(N) queries while the optimal quantum eavesdropping strategy requires Theta(N^{1/2+k/{k+1}}) queries, approaching Theta(N^{3/2}) when k increases. When legitimate parties are provided with quantum computers, we present two quantum protocols improving on the best known scheme before this work. Furthermore, for any k>= 2, we give a quantum protocol in which legitimate parties establish a secret in O(N) queries while the optimal quantum eavesdropping strategy requires Theta(N^{1+{k}/{k+1}})} queries, approaching Theta(N^{2}) when k increases.

Étude de dispositifs électroniques moléculaires à l'aide de modèles simples

Cette thèse en électronique moléculaire porte essentiellement sur le développement d’une méthode pour le calcul de la transmission de dispositifs électroniques moléculaires (DEMs), c’est-à-dire des molécules branchées à des contacts qui forment un dispositif électronique de taille moléculaire. D’une part, la méthode développée vise à apporter un point de vue différent de celui provenant des méthodes déjà existantes pour ce type de calculs. D’autre part, elle permet d’intégrer de manière rigoureuse des outils théoriques déjà développés dans le but d’augmenter la qualité des calculs. Les exemples simples présentés dans ce travail permettent de mettre en lumière certains phénomènes, tel que l’interférence destructive dans les dispositifs électroniques moléculaires. Les chapitres proviennent d’articles publiés dans la littérature. Au chapitre 2, nous étudions à l’aide d’un modèle fini avec la méthode de la théorie de la fonctionnelle de la densité de Kohn-Sham un point quantique moléculaire. De plus, nous calculons la conductance du point quantique moléculaire avec une implémentation de la formule de Landauer. Nous trouvons que la structure électronique et la conductance moléculaire dépendent fortement de la fonctionnelle d’échange et de corrélation employée. Au chapitre 3, nous discutons de l’effet de l’ajout d’une chaîne ramifiée à des molécules conductrices sur la probabilité de transmission de dispositifs électroniques moléculaires. Nous trouvons que des interférences destructives apparaissent aux valeurs propres de l’énergie des chaînes ramifiées isolées, si ces valeurs ne correspondent pas à des états localisés éloignés du conducteur moléculaire. Au chapitre 4, nous montrons que les dispositifs électroniques moléculaires contenant une molécule aromatique présentent généralement des courants circulaires qui sont associés aux phénomènes d’interférence destructive dans ces systèmes. Au chapitre 5, nous employons l’approche « source-sink potential » (SSP) pour étudier la transmission de dispositifs électroniques moléculaires. Au lieu de considérer les potentiels de sources et de drains exactement, nous utilisons la théorie des perturbations pour trouver une expression de la probabilité de transmission, T(E) = 1 − |r(E)|2, où r(E) est le coefficient de réflexion qui dépend de l’énergie. Cette expression dépend des propriétés de la molécule isolée, en effet nous montrons que c’est la densité orbitalaire sur les atomes de la molécule qui sont connectés aux contacts qui détermine principalement la transmission du dispositif à une énergie de l’électron incident donnée. Au chapitre 6, nous présentons une extension de l’approche SSP à un canal pour des dispositifs électroniques moléculaires à plusieurs canaux. La méthode à multiples canaux proposée repose sur une description des canaux propres des états conducteurs du dispositif électronique moléculaire (DEM) qui sont obtenus par un algorithme auto-cohérent. Finalement, nous utilisons le modèle développé afin d’étudier la transmission du 1-phényl-1,3-butadiène branché à deux rangées d’atomes couplées agissant comme contacts à gauche et à la droite.

Arbitrage en ligne et les litiges du commerce électronique

"Mémoire présenté à la Faculté des études supérieures en vue de l'obtention du grade de Maîtrise en droit (LLM)"

Preuves interactives quantiques

Cette thèse est consacrée à la complexité basée sur le paradigme des preuves interactives. Les classes ainsi définies ont toutes en commun qu’un ou plusieurs prouveurs, infiniment puissants, tentent de convaincre un vérificateur, de puissance bornée, de l’appartenance d’un mot à un langage. Nous abordons ici le modèle classique, où les participants sont des machines de Turing, et le modèle quantique, où ceux-ci sont des circuits quantiques. La revue de littérature que comprend cette thèse s’adresse à un lecteur déjà familier avec la complexité et l’informatique quantique. Cette thèse présente comme résultat la caractérisation de la classe NP par une classe de preuves interactives quantiques de taille logarithmique. Les différentes classes sont présentées dans un ordre permettant d’aborder aussi facilement que possible les classes interactives. Le premier chapitre est consacré aux classes de base de la complexité ; celles-ci seront utiles pour situer les classes subséquemment présentées. Les chapitres deux et trois présentent respectivement les classes à un et à plusieurs prouveurs. La présentation du résultat ci-haut mentionné est l’objet du chapitre quatre.