Quantum nonlocality, cryptography and complexity

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

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.

Optimisation et approximation adiabatique

L'approximation adiabatique en mécanique quantique stipule que si un système quantique évolue assez lentement, alors il demeurera dans le même état propre. Récemment, une faille dans l'application de l'approximation adiabatique a été découverte. Les limites du théorème seront expliquées lors de sa dérivation. Ce mémoire à pour but d'optimiser la probabilité de se maintenir dans le même état propre connaissant le système initial, final et le temps d'évolution total. Cette contrainte sur le temps empêche le système d'être assez lent pour être adiabatique. Pour solutionner ce problème, une méthode variationnelle est utilisée. Cette méthode suppose connaître l'évolution optimale et y ajoute une petite variation. Par après, nous insérons cette variation dans l'équation de la probabilité d'être adiabatique et développons en série. Puisque la série est développée autour d'un optimum, le terme d'ordre un doit nécessairement être nul. Ceci devrait nous donner un critère sur l'évolution la plus adiabatique possible et permettre de la déterminer. Les systèmes quantiques dépendants du temps sont très complexes. Ainsi, nous commencerons par les systèmes ayant des énergies propres indépendantes du temps. Puis, les systèmes sans contrainte et avec des fonctions d'onde initiale et finale libres seront étudiés.

Comportement des systèmes de référence quantiques pour le moment cinétique

Le domaine des systèmes de référence quantiques, dont les dernière avancées sont brièvement présentées au chapitre 1, est extrêmement pertinent à la compréhension de la dégradation des états quantiques et de l’évolution d’instruments de mesures quantiques. Toutefois, pour arriver à comprendre formellement ces avancées et à apporter une contribution originale au domaine, il faut s’approprier un certain nombre de concepts physiques et mathématiques, in- troduits au chapitre 2. La dégradation des états quantiques est très présente dans le contrôle d’états utiles à l’informatique quantique. Étant donné que ce dernier tente de contrôler des sys- tèmes à deux états, le plus souvent des moments cinétiques, l’analyse des systèmes de référence quantiques qui les mesurent s’avère opportune. Puisque, parmi les plus petits moments ciné- tiques, le plus connu est de s = 1 et que son état le plus simple est l’état non polarisé, l’étude 2 du comportement d’un système de référence mesurant successivement ce type de moments ci- nétiques constitue le premier pas à franchir. C’est dans le chapitre 3 qu’est fait ce premier pas et il aborde les questions les plus intéressantes, soit celles concernant l’efficacité du système de référence, sa longévité et leur maximum. La prochaine étape est de considérer des états de moments cinétiques polarisés et généraux, étape qui est abordée dans le chapitre 4. Cette fois, l’analyse de la dégradation du système de référence est un peu plus complexe et nous pouvons l’inspecter approximativement par l’évolution de certains paramètres pour une certaine classe d’états de système de référence. De plus, il existe une interaction entre le système de référence et le moment cinétique qui peut avoir un effet sur le système de référence tout à fait comparable à l’effet de la mesure. C’est cette même interaction qui est étudiée dans le chapitre 5, mais, cette fois, pour des moments cinétiques de s = 1. Après une comparaison avec la mesure, il devient manifeste que les ressemblances entre les deux processus sont beaucoup moins apparentes, voire inexistantes. Ainsi, cette ressemblance ne semble pas générale et semble accidentelle lorsqu’elle apparaît.

The decoupling approach to quantum information theory

La théorie de l'information quantique étudie les limites fondamentales qu'imposent les lois de la physique sur les tâches de traitement de données comme la compression et la transmission de données sur un canal bruité. Cette thèse présente des techniques générales permettant de résoudre plusieurs problèmes fondamentaux de la théorie de l'information quantique dans un seul et même cadre. Le théorème central de cette thèse énonce l'existence d'un protocole permettant de transmettre des données quantiques que le receveur connaît déjà partiellement à l'aide d'une seule utilisation d'un canal quantique bruité. Ce théorème a de plus comme corollaires immédiats plusieurs théorèmes centraux de la théorie de l'information quantique. Les chapitres suivants utilisent ce théorème pour prouver l'existence de nouveaux protocoles pour deux autres types de canaux quantiques, soit les canaux de diffusion quantiques et les canaux quantiques avec information supplémentaire fournie au transmetteur. Ces protocoles traitent aussi de la transmission de données quantiques partiellement connues du receveur à l'aide d'une seule utilisation du canal, et ont comme corollaires des versions asymptotiques avec et sans intrication auxiliaire. Les versions asymptotiques avec intrication auxiliaire peuvent, dans les deux cas, être considérées comme des versions quantiques des meilleurs théorèmes de codage connus pour les versions classiques de ces problèmes. Le dernier chapitre traite d'un phénomène purement quantique appelé verrouillage: il est possible d'encoder un message classique dans un état quantique de sorte qu'en lui enlevant un sous-système de taille logarithmique par rapport à sa taille totale, on puisse s'assurer qu'aucune mesure ne puisse avoir de corrélation significative avec le message. Le message se trouve donc «verrouillé» par une clé de taille logarithmique. Cette thèse présente le premier protocole de verrouillage dont le critère de succès est que la distance trace entre la distribution jointe du message et du résultat de la mesure et le produit de leur marginales soit suffisamment petite.

Study of the diffusion in polymer solutions and hydrogels by NMR spectroscopy and NMR imaging

Afin d'étudier la diffusion et la libération de molécules de tailles inférieures dans un gel polymère, les coefficients d'auto-diffusion d'une série de polymères en étoile avec un noyau d'acide cholique et quatre branches de poly(éthylène glycol) (PEG) ont été déterminés par spectroscopie RMN à gradient de champ pulsé dans des solutions aqueuses et des gels de poly(alcool vinylique). Les coefficients de diffusion obtenus ont été comparés avec ceux des PEGs linéaires et dendritiques pour étudier l'effet de l'architecture des polymères. Les polymères en étoile amphiphiles ont des profils de diffusion en fonction de la concentration similaires à leurs homologues linéaires dans le régime dilué. Ils diffusent plus lentement dans le régime semi-dilué en raison de leur noyau hydrophobe. Leurs conformations en solution ont été étudiées par des mesures de temps de relaxation spin-réseau T1 du noyau et des branches. L'imagerie RMN a été utilisée pour étudier le gonflement des comprimés polymères et la diffusion dans la matrice polymère. Les comprimés étaient constitués d'amidon à haute teneur en amylose et chargés avec de l'acétaminophène (de 10 à 40% en poids). Le gonflement des comprimés, ainsi que l'absorption et la diffusion de l'eau, augmentent avec la teneur en médicament, tandis que le pourcentage de libération du médicament est similaire pour tous les comprimés. Le gonflement in vitro des comprimés d'un complexe polyélectrolyte à base d'amidon carboxyméthylé et de chitosane a également été étudié par imagerie RMN. Ces comprimés sont sensibles au pH : ils gonflent beaucoup plus dans les milieux acides que dans les milieux neutres en raison de la dissociation des deux composants et de la protonation des chaînes du chitosane. La comparaison des résultats avec ceux d'amidon à haute teneur en amylose indique que les deux matrices ont des gonflements et des profils de libération du médicament semblables dans les milieux neutres, alors que les comprimés complexes gonflent plus dans les milieux acides en raison de la dissociation du chitosane et de l'amidon.

Categorical quantum computation

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

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.

Does Chance hide Necessity? : a reevaluation of the debate ‘determinism - indeterminism’ in the light of quantum mechanics and probability theory

Dans cette thèse l’ancienne question philosophique “tout événement a-t-il une cause ?” sera examinée à la lumière de la mécanique quantique et de la théorie des probabilités. Aussi bien en physique qu’en philosophie des sciences la position orthodoxe maintient que le monde physique est indéterministe. Au niveau fondamental de la réalité physique – au niveau quantique – les événements se passeraient sans causes, mais par chance, par hasard ‘irréductible’. Le théorème physique le plus précis qui mène à cette conclusion est le théorème de Bell. Ici les prémisses de ce théorème seront réexaminées. Il sera rappelé que d’autres solutions au théorème que l’indéterminisme sont envisageables, dont certaines sont connues mais négligées, comme le ‘superdéterminisme’. Mais il sera argué que d’autres solutions compatibles avec le déterminisme existent, notamment en étudiant des systèmes physiques modèles. Une des conclusions générales de cette thèse est que l’interprétation du théorème de Bell et de la mécanique quantique dépend crucialement des prémisses philosophiques desquelles on part. Par exemple, au sein de la vision d’un Spinoza, le monde quantique peut bien être compris comme étant déterministe. Mais il est argué qu’aussi un déterminisme nettement moins radical que celui de Spinoza n’est pas éliminé par les expériences physiques. Si cela est vrai, le débat ‘déterminisme – indéterminisme’ n’est pas décidé au laboratoire : il reste philosophique et ouvert – contrairement à ce que l’on pense souvent. Dans la deuxième partie de cette thèse un modèle pour l’interprétation de la probabilité sera proposé. Une étude conceptuelle de la notion de probabilité indique que l’hypothèse du déterminisme aide à mieux comprendre ce que c’est qu’un ‘système probabiliste’. Il semble que le déterminisme peut répondre à certaines questions pour lesquelles l’indéterminisme n’a pas de réponses. Pour cette raison nous conclurons que la conjecture de Laplace – à savoir que la théorie des probabilités présuppose une réalité déterministe sous-jacente – garde toute sa légitimité. Dans cette thèse aussi bien les méthodes de la philosophie que de la physique seront utilisées. Il apparaît que les deux domaines sont ici solidement reliés, et qu’ils offrent un vaste potentiel de fertilisation croisée – donc bidirectionnelle.

Polymères de coordination et éponge cristalline : de nouveaux matériaux pour la conversion de l’énergie solaire et la résolution de la structure cristalline de composés huileux.

Le premier volet de ce travail portera sur l’expérience acquise lors d’un stage d’étude à Tokyo, au Japon, dans le groupe de recherche du Pr. Makoto Fujita, une sommité d’envergure internationale dans le domaine de l’auto-assemblage. En continuité avec les plus récents travaux du Pr. Fujita, des systèmes poreux auto-assemblés présentant des cavités fonctionnalisées ont été développés dans le but d’encapsuler des acides gras afin d’en déterminer la structure cristalline. Ces éponges ont été caractérisées par des techniques courantes telles que la spectroscopie à résonance magnétique nucléaire 1H, 13C{1H} et Cosy, la spectrométrie de masse, l’analyse élémentaire, la microscopie optique infrarouge ainsi que la diffraction des rayons X. Une autre approche employée pour obtenir de meilleures propriétés spectroscopiques fut la synthèse de dendrimères métalliques de génération 0. Un nouveau ligand de type 1,3,5-triazine a été synthétisé par une réaction typique de cyclisation de nitrile en présence catalytique d’hydrure de sodium. Des espèces mono-, bis- et trinucléaire de Ru(II) furent synthétisés ainsi que deux espèces hétérométalliques de Ru(II)/Pt(II) et de Ru(II)/Os(II). Tous les complexes obtenus furent caractérisés par spectroscopie à résonance magnétique nucléaire (1H, 13C{1H} et Cosy) à l’état liquide, par spectroscopie de masse à haute résolution et par analyse élémentaire. La génération de dihydrogène à partir de l’espèce hétérométallique a été étudiée. Les propriétés optiques et électroniques ont été analysées par spectroscopie UV-Vis, par analyse de la luminescence, du temps de vie de luminescence, par des analyses de rendement quantique ainsi que par des analyses de voltampérométrie cyclique à balayage. Finalement, dans le but d’améliorer les propriétés spectroscopiques d’absorption de complexes métalliques, nous avons synthétisé une série de polymères homo- et hétérométalliques, intégrant des ligands de type bis(2,2’:6,2’’-terpyridine). Les complexes générés furent caractérisés par diverses techniques tel que la spectroscopie à résonance magnétique nucléaire (1H, 13C{1H} et Cosy) à l’état liquide, par spectroscopie de masse à haute résolution ainsi que par analyse élémentaire. Les propriétés optiques et électroniques ont été analysées par spectroscopie UV-Vis, par analyse de la luminescence, du temps de vie de luminescence, par des analyses de rendement quantique ainsi que par des analyses de voltampérométrie cyclique à balayage.

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).

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.