Nous présentons dans cette thèse un nouveau modèlepour les langages de programmation quantique. Notre modèle est uneadaptation de la sémantique de jeux probabilistes définie par Danos etHarmer: nous y ajoutons des stratégies quantiquespour permettre la représentation des états et des opérations quantiques.Nous établissons quelques propriétés de base de ces stratégies. Cespropriétés sont ensuite utilisées pour construire des sémantiquesdénotationnelles pour trois langages de programmation quantique. Le premierlangage est une formalisation du calcul par mesures proposé par Danoset al. Les deux autres langages sont nouveaux: ce sont deslangages quantiques d'ordre supérieur dont la syntaxe a été construiteà partir d'observations expliquant l'échec des tentatives précédentespour construire une sémantique dénotationnelle pour de tels langages. La sémantique de jeux présentée dans cette thèseest la première sémantique dénotationnelle pour de telslambda-calculs équipés de types et d'opérations supplémentairespermettant la programmation d'algorithmes quantiques. Les résultatsprésentés valident les deux approches différentes utilitées dans laconception de ces deux nouveaux languages d'ordre supérieur: une premièreoù les états quantiques sont indirectement accessibles via desréférences et une seconde où ils sont introduit directement comme desconstantes dans le langage. Les stratégies quantiques présentéespermettent de comprendre les contraintes devant êtreimposées aux systèmes de type quantique comportant des types d'ordresupérieurs. La contrainte la plus importante est le fait que l'abstractionsur une partie d'un état quantique comportant plusieurs qbits inconnus doitêtre prohibée. Les stratégies quantiques constituent un nouveau modèle mathématique quidécrit l'interaction entre les données classiques et quantiques par desdialogues entre système et environnement. L'interaction entre les differentespar
Nous présentons dans cette thèse un nouveau modèlepour les langages de programmation quantique. Notre modèle est uneadaptation de la sémantique de jeux probabilistes définie par Danos etHarmer: nous y ajoutons des stratégies quantiquespour permettre la représentation des états et des opérations quantiques.Nous établissons quelques propriétés de base de ces stratégies. Cespropriétés sont ensuite utilisées pour construire des sémantiquesdénotationnelles pour trois langages de programmation quantique. Le premierlangage est une formalisation du calcul par mesures proposé par Danoset al. Les deux autres langages sont nouveaux: ce sont deslangages quantiques d'ordre supérieur dont la syntaxe a été construiteà partir d'observations expliquant l'échec des tentatives précédentespour construire une sémantique dénotationnelle pour de tels langages. La sémantique de jeux présentée dans cette thèseest la première sémantique dénotationnelle pour de telslambda-calculs équipés de types et d'opérations supplémentairespermettant la programmation d'algorithmes quantiques. Les résultatsprésentés valident les deux approches différentes utilitées dans laconception de ces deux nouveaux languages d'ordre supérieur: une premièreoù les états quantiques sont indirectement accessibles via desréférences et une seconde où ils sont introduit directement comme desconstantes dans le langage. Les stratégies quantiques présentéespermettent de comprendre les contraintes devant êtreimposées aux systèmes de type quantique comportant des types d'ordresupérieurs. La contrainte la plus importante est le fait que l'abstractionsur une partie d'un état quantique comportant plusieurs qbits inconnus doitêtre prohibée. Les stratégies quantiques constituent un nouveau modèle mathématique quidécrit l'interaction entre les données classiques et quantiques par desdialogues entre système et environnement. L'interaction entre les differentespar
Sémantique des Jeux Quantique Cette thèse porte sur la sémantique des langages de programmation quantiques, et en particulier sur celle du lambda-calcul quantique, un langage paradigmatique dû à Selinger et Valiron qui marrie flot de contrôle classique riche (fonctions d’ordre supérieur, récursion, etc) avec des données quantiques (création de qubits, mesure, application d’opérateurs unitaires). Pour donner un modèle du lambda-calcul quantique, il convient de trouver une alliance harmonieuse entre les modèles traditionnels de sémantique dénotationnelle (qui donnent du sens aux programmes en les interprétant dans des univers mathématiques adéquats) et les mathématiques du quantique (espaces de Hilbert, matrices de densité, etc). Cette thèse comporte trois contributions principales : Premièrement, nous étendons la sémantique des jeux, une approche dynamique à la sémantique dénotationnelle, au cas quantique. Nous obtenons le premier modèle dénotationnel du lambda-calcul quantique complet qui soit à la fois compositionnel et interactif, c’est à dire qu’il représente la dynamique de l’exécution. Notre modèle est une généralisation naturelle de développements récents pour le cas probabiliste.Deuxièmement, nous relions formellement notre modèle au seul modèle dénotationnel pré-existant du lambda-calcul quantique complet, le modèle relationnel quantique dû à Pagani, Selinger et Valiron. Finalement, nous montrons que notre modèle de jeux est pleinement adéquat, la correspondance idéale entre un langage de programmation et sa sémantique dénotationnelle. Nous en déduisons que le modèle relationnel quantique était lui-aussi pleinement adéquat, un problème que ses auteurs avaient laissé ouvert. Cette thèse se décompose en trois parties. La première partie présente des préliminaires de théorie des catégories, qui permettent de définir un cadre formel englobant à la fois notre modèle de jeux quantique et le modèle relationnel quantique, puis des préliminaires sur les mathématiques du quantique, et enfin des préliminaires sur la programmation quantique et ses modèles. La deuxième partie commence par des préliminaires de sémantique des jeux, et définit notre modèle de jeux quantique dans un cadre simplifié : le lambda-calcul linéaire quantique. Enfin, la troisième partie s'appuie sur la deuxième pour présenter le modèle de jeux quantique complet, prouver que ce modèle est pleinement adéquat, et en déduire que le modèle relationnel quantique est lui aussi pleinement adéquat.
La recherche en informatique quantique a pris de l’ampleur dans les deux dernières décennies, notamment grâce aux financements massifs des gouvernements et de l’industrie dans les technologies quantiques. L’ordinateur quantique promet de résoudre des problèmes qui jusqu’à présent restaient insurmontables à cause du temps déraisonnable qu’il faudrait pour les résoudre sur les ordinateurs classiques les plus puissants. L’idée de l’ordinateur quantique consiste à utiliser des propriétés quantiques de la matière, telles que l’intrication et la superposition quantique des états, pour effectuer des calculs d’une nouvelle manière. L’informatique quantique requiert un nouveau type d’ordinateur où les bits d’information classique, généralement représentés par la présence ou non de courant à l’entrée d’un transistor, sont remplacés par des bits quantiques aussi appelés qubits, et qui sont représentés par l’état d’un système quantique. De plus, il est nécessaire de développer de nouveaux algorithmes capables d’être implémentés sur un ordinateur quantique et capables de tirer parti de l’avantage quantique. Cette thèse porte sur ces deux composantes complémentaires : la construction de portes logiques, un bloc fondamental de tout ordinateur, et la création de meilleurs algorithmes pour résoudre des problèmes pertinents sur ces machines. Parmi les plateformes les plus avancées pour l’ordinateur quantique, on trouve les circuits supraconducteurs, qui sont la plateforme sur laquelle ont misé Google, IBM, Alice&Bob, Nord Quantique et bien d’autres compagnies. Malgré les avancées des dernières décennies, de nombreux défis restent à être relevés pour que les machines existantes soient en mesure de résoudre des problèmes pertinents et surpassent les ordinateurs classiques. L’un des défis auquel cette thèse s’attaque est la réalisation de portes logiques à deux qubits rapides et à haute fidélité. La rapidité est cruciale pour pouvoir réaliser le plus d’opérations possible avant que les qubits ne perdent leur cohérence quantique, et une haute fidélité est requise pour minimiser les erreurs de calcul et permettre d’implémenter de la correction d’erreurs quantiques. De plus, certains qubits supraconducteurs sont connus pour être affectés par une interaction indésirable, l’interaction ZZ qui, même si relativement faible, affecte la fidélité des portes logiques quantiques, empêchant d’atteindre des fidélités supérieures à 99.9% nécessaires à la correction d’erreurs. En parallèle avec l’amélioration des composantes de l’ordinateur quantique, il est important de développer des applications pour ce nouveau type de machine. Parmi les approches étudiées, les algorithmes quantiques variationnels (VQA) sont ceux qui sont les plus susceptibles d’être déployés sur les ordinateurs quantiques de petites tailles existants. Ce sont des algorithmes hybrides qui nécessitent à la fois de la puissance de calcul classique et quantique. Ces algorithmes semblent prometteurs pour résoudre de nombreux problèmes concrets d’intérêt industriel, comme obtenir les propriétés de molécules ou trouver les solutions de problèmes d’optimisation combinatoire. En effet, ces problèmes peuvent être formulés sous forme d’un Hamiltonien et résolus en déterminant son état fondamental. Dans ce but, les VQAs utilisent un circuit quantique paramétré appelé ansatz, dont les paramètres sont optimisés pour s’approcher de l’état fondamental. Un premier défi consiste à trouver un ansatz qui permette, pour un problème donné, de converger le plus efficacement possible vers la solution. Un deuxième défi est de trouver un circuit fait de portes logiques facilement implémentables sur les plateformes physiques actuelles. Les travaux effectués dans cette thèse apportent des contributions à ces deux défis. Dans la première partie de la thèse, nous introduisons le dispositif que nous avons conçu et qui permet de réaliser des portes d’intrication paramétrique entre deux qubits supraconducteurs. Cette approche a permis à nos collaborateurs du groupe d’Andrew Houck de l’Université de Princeton de réaliser expérimentalement une opération de type √iSWAP en 15 ns avec une fidélité de 98.8%, et ce dans un dispositif où l’interaction ZZ est supprimée. Dans la seconde partie de la thèse, nous avons développé un ansatz pour les VQAs permettant de résoudre le modèle de Fermi Hubbard. Ce nouvel ansatz utilise les avantages de deux ansätze préexistants, et permet d’obtenir l’énergie et l’état fondamental du FHM avec une précision de plusieurs ordres de grandeur supérieure aux ansätze standards, et ce en réduisant significativement le nombre de portes d’intrication CNOT qui sont généralement imparfaites et longues à implémenter.
Combining classical and quantum control : A logical, syntactic and semantic perspective Cette thèse vise principalement à établir les fondements théoriques nécessaires à la conception d'un langage de programmation complet pour l'informatique quantique. L'idée qui a inspiré toutes les contributions de cette thèse est de produire dans le cadre quantique un développement similaire à celui utilisé pour les langages de programmation et la logique dans le paradigme classique. En nous appuyant sur les travaux préparatoires de la correspondance Curry-Howard-Lambek, nous essayons d'approfondir les trois pierres angulaires de cette correspondance : les langages de programmation, la logique et la théorie des catégories, en nous concentrant sur la combinaison de deux paradigmes et en considérant des programmes avec des flots de contrôle quantique et classique. Nous avons essayé d'aller plus loin. Nous avons également abordé les deux visions complémentaires de la mécanique quantique, celles de Heisenberg et de Schrödinger, et adopté l'une d'elles pour définir une sémantique physiquement intuitive pour les langages dont nous discutons. Cette thèse apporte deux contributions principales à la littérature existante sur les langages de programmation quantiques. Nous introduisons tout d'abord un lambda calcul quantique qui combine le contrôle quantique et classique, dont la conception s'appuie sur la structure mathématique de sa sémantique dénotationnelle physiquement intuitive. La sémantique opérationnelle de ce langage est basée sur une adaptation des configurations quantiques que nous introduisons, et est liée au modèle dénotationnel par un résultat d'adéquation. Le langage fournit également un prototype de types inductifs quantiques à travers le type qnat, un type pour les entiers naturels quantiques. Le modèle dénotationnel de ce calcul est basé sur les algèbres de von Neumann, qui sont au cœur de la formulation mathématique de la vision de Heisenberg de la mécanique quantique. La deuxième contribution est un langage de preuve pour le fragment IMALL de la logique linéaire qui s'appuie sur certaines observations clés du calcul présenté ci-dessus. Ce langage estl'un des premiers à pouvoir prendre en charge des programmes combinant des constructions telles que le quantum switch et la mesure. À cet égard, ce travail constitue une amélioration significative par rapport au calcul précédent, car il prend en charge une version plus fine du contrôle quantique, permettant ainsi l'écriture d'algorithmes tels que le quantum switch. La syntaxe du langage est par nature algébrique et linéaire, permettant d'écrire des combinaisons linéaires de termes. Une conséquence majeure, avec la sémantique de la modalité B qu'il introduit, est que la mesure n'est plus une construction de base du langage. Elle peut désormais être écrite comme un programme parmi d'autres dans le langage. Enfin, la sémantique dénotationnelle de ce travail est basée sur les algèbres C* - une généralisation des algèbres de von Neumann. Le modèle dénotationnel s'avère adéquat pour la sémantique opérationnelle, dont la linéarité en est une conséquence naturelle. Enfin, nous concluons cette thèse en présentant les limites de ces travaux et les orientations possibles pour des travaux futurs.
Compatibilité et non-localité L'un des concepts majeurs introduit par la théorie quantique est celui de la compatibilité des mesures quantiques. Il existe certains types de mesures qui ne peuvent pas être effectuées en même temps. Ainsi, on dit que les mesures sont compatibles si on peut mesurer en même temps et d'autre sont incompatibles. L'autre concept majeur de la mécanique quantique est celui de la nonlocalité qui est l'un des concepts les plus contre-intuitifs de la physique quantique. Ce concept majeur est dû à John Bell qui a montré que la mécanique quantique est intrinsèquement non locale. Ainsi, on parle de violation des inégalités de Bell par la mécanique quantique. Aujourd'hui, la nonlocalité est comprise à travers les jeux nonlocaux. Un jeux nonlocal consiste en deux joueurs ou plus Alice et Bob jouant contre un arbitre. Ce dernier posera un certain nombre de questions aux joueurs qui devront générer un certain nombre de réponses en utilisant une stratégie classique ou quantique. Il se trouve que le maximum des réponses qu'Alice et Bob peuvent générer est intrinsèquement relié à une norme tensorielle caractérisant le jeu. Dans ce formalisme, l'utilisation des stratégies classiques est relié à la norme de la matrice du jeux lui-même, ainsi la violation des inégalités de Bell se traduit par une inégalité stricte entre les normes tensorielles. Le but de cette thèse consiste à comprendre l'incompatibilité des mesures quantiques ainsi que le lien avec les inégalités de Bell. Dans un premier temps, nous avons introduit la compatibilité des mesures quantiques sous un nouveau point de vue, et analysé les types de bruit qu'on peut effectuer à fin de rendre le système compatible. Ce nouveau point de vue consiste à comprendre et à analyser l'effet de la dimension de l'espace de Hilbert sur l'incompatibilité des mesures. Par ailleurs à fin de rendre des mesures compatibles, on peut introduire l'effet d'un bruit. Comme application, certains états connu sous le nom de MUB sont de nature incompatible, on montre même si on rajoute du bruit aux MUB celle-ci restant incompatible, il existe une isométrie et un espace de Hilbert de dimension plus petite rendant les MUB compatibles. Dans un deuxième temps, nous avons analysé le lien intrinsèque reliant l'incompatibilité des mesures quantique et la violation des inégalités de Bell. Pour cela, on a considéré le cadre des jeux nonlocaux, où les mesures d'Alice sont fixées. Il est connu qu'une violation des inégalités de Bell nécessite l'utilisation des mesures incompatibles. Par ailleurs, si Alice veut savoir si elle observera une violation des inégalités de Bell si elle utilise des mesures incompatibles. Pour cela, elle doit calculer deux normes tensorielles d'un tenseur construit à partir de ses mesures. Ces normes tensorielles vont caractériser d'une part la compatibilité des mesures d'Alice et d'autre part la violation des inégalités de Bell. Dans ce cadre naturel, comprendre le lien entre incompatibilité des mesures quantiques et la violation des inégalités de Bell, revient à comparer les deux normes tensorielles. Or, il se trouve que pour le jeu CHSH ces deux normes sont égales, mais on peut montrer généralement qu'elles ne le sont pas. On peut se demander s'il existe d'autre types de jeux satisfaisant cette égalité des normes tensorielles ? Il se trouve que nous avons montré qu'avec des conditions suffisantes, seul le jeux CHSH à constante multiplicative près donne l'égalité entre les normes tensorielles.
Apprendre à partir de données est un problème fondamental en statistique qui a des applications dans presque tous les aspects de notre vie. Il existe deux classes naturelles de stratégies pour apprendre à partir de données. Les stratégies non adaptatives collectent toutes les données nécessaires, puis traitent toutes ces données en une seule fois, tandis que les stratégies adaptatives peuvent utiliser les informations accumulées pour décider si davantage d'échantillons doivent être collectés. De plus, avec les méthodes adaptatives, la façon dont les nouvelles informations sont obtenues peut également être adaptée en fonction de ce qui a été observé lors des étapes précédentes. Étant donné que notre objectif est de minimiser la quantité de données requises, dans cette thèse, nous étudions le nombre optimal de ressources pour les deux approches pour différents problèmes d'apprentissage classiques et quantiques.Pour tester les distributions classiques, nous montrons que les stratégies adaptatives surpassent leurs analogues non adaptatives d'un facteur de quatre lorsque la taille de l'alphabet est petite. De plus, les stratégies adaptatives peuvent s'arrêter plus tôt lorsque les distributions testées sont très différentes les unes des autres. Cet avantage est également présent même pour les grands alphabets.En ce qui concerne le test des états quantiques, nous présentons des situations où les stratégies adaptatives ont un avantage significatif par rapport aux stratégies non adaptatives. Celles-ci comprennent le test d'hypothèses (binaires), le test d'identité et de proximité des états quantiques.Cependant, dans certaines situations, nous avons plusieurs façons de générer les données. Ces situations peuvent être modélisées par des canaux quantiques qui produisent des données après avoir reçu une entrée choisie par la stratégie d'apprentissage. Ces entrées peuvent également être adaptées aux observations précédentes par les stratégies adaptatives, tandis que les stratégies non adaptatives doivent déterminer toutes les entrées à l'avance. Nous déterminons la complexité optimale pour tester si un canal est parfait ou non. De plus, nous caractérisons le nombre optimal de ressources pour apprendre un canal général ou un bruit de type Pauli dans le cadre non adaptatif. En outre, nous réduisons l'écart entre les stratégies adaptatives et non adaptatives pour l'apprentissage du bruit de type Pauli.
Cette thèse se trouve à l'intersection de la théorie des matrices aléatoires, des probabilités libres et de la théorie de l'information quantique. La plus grande partie des travaux présentés se concentrent sur les aspects probabilistes de l'information quantique et, en particulier, sur l'usage des matrices aléatoires dans différents modèles en théorie quantique. Une autre partie de cette thèse est dédiée à la théorie des probabilités libres et à ses liens avec les matrices aléatoires et l'information quantique. En théorie quantique de l'information, il existe différents modèles de matrices densités aléatoires. On s'intéresse, dans l'esprit de la théorie des matrices aléatoires, au comportement asymptotique des matrices densités, dans la limite où la taille du système converge vers l'infini. Le point de vue pris dans cette thèse est celui des systèmes quantiques ouverts, où l'espace qui nous intéresse est couplé avec l'environnement et le système composé se trouve dans un état pur uniforme. En prenant la trace partielle sur l'environnement, on obtient des matrices densités aléatoires que l'on étudie dans deux régimes asymptotiques. En exploitant des liens avec l'ensemble des matrices aléatoires dites de Wishart, on obtient les densités spectrales limites et les fluctuations des valeurs propres extrémales. En collaboration avec Clément Pellegrini, on étudie des interactions répétées entre un système quantique et une chaîne de systèmes auxiliaires. Nous avons introduit des éléments aléatoires dans ce modèle, soit en considérant que les états de la chaîne sont des variables indépendantes et identiquement distribuées, soit en choisissant, à chaque interaction, une matrice unitaire d'interaction aléatoire uniforme. On s'intéresse aux propriétés asymptotiques des matrices, après un grand nombre d'interactions. Au passage, on introduit un nouveau modèle de matrices densités aléatoires que l'on compare avec les modèles existants dans la littérature. Un problème qui occupe une place centrale dans cette thèse est la conjecture de Nielsen sur la catalyse en théorie quantique de l'information. En collaboration avec Guillaume Aubrun, nous avons progressé vers la preuve de cette conjecture et nous l'avons par la suite généralisée dans différentes directions. L'outil principal utilisé dans ces travaux nous vient de la théorie des probabilités : la théorie des grandes déviations nous permet de comparer stochastiquement des puissances de convolution des mesures de probabilités. Les techniques introduites et le lien avec la théorie des grandes déviations nous ont permis de voir ce problème sous un autre angle et de donner aux théoriciens de l'information quantique un outil de travail puissant. Enfin, toujours en lien avec les matrices aléatoires, cette thèse a donné lieu à deux travaux en probabilités libres. Les ensembles de matrices aléatoires sont des exemples importants et simples où l'on peut observer l'indépendance libre; il est donc naturel de se demander s'il est possible d'obtenir la notion de liberté avec des matrices déterministes. Une telle construction a été proposée par Philippe Biane, en utilisant des sommes de transpositions dans l'algèbre du groupe symétrique. Avec Florent Benaych-Georges, on a pu généraliser les résultats de P. Biane à des cycles quelconques. Notre approche est combinatoire ce qui nous a permis d'aboutir à des formules explicites pour les moments et les cumulants libres des variables à la limite. Grâce à cette même approche nous avons élaboré un modèle analogue en probabilités classiques en remplaçant le groupe symétrique par le groupe abélien des parties d'un ensemble fini, muni de l'opération de différence symétrique. En collaboration avec Stéphane Attal, nous avons construit une approximation de l'espace de Fock libre (qui joue un rôle central en théorie des probabilités non-commutatives) par un produit libre dénombrable d'espaces discrets. Cette idée généralise au cas libre une construction similaire pour l'espace de Fock symétrique, introduite et étudié par S. Attal. En même temps nous avons obtenu une approximation des opérateurs fondamentaux de création, d'annihilation et de jauge par des opérateurs construits à partir des matrices de taille 2. En utilisant ces constructions sont ensuite utilisées pour retrouver quelques approximations connues du mouvement brownien libre et du processus de Poisson libre. Tous ces résultats se généralisent au cas des espaces de Fock de multiplicité supérieure, qui permettent d'approcher des processus multidimensionnels. En conclusion, l'ensemble des travaux scientifiques présentés dans cette thèse se situe à l'intersection de trois grandes directions: les matrices aléatoires, les probabilités libres et la théorie quantique de l'information, l'accent étant mis sur les interactions et sur les liens entre ces domaines.