Cette 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.
Cette 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.
Nous présentons dans ce travail plusieurs résultats dans différents domaines de l'information quantique. Après une première partie où nous proposons une introduction au domaine, nous proposons des caractérisations simples et efficaces du phénomène de l'intrication des états purs. Les deux formes de séparabilité étudiées sont la séparabilité totale et la p-q séparabilité. Ces caractérisations nous ont permis de donner des algorithmes optimaux de détection de la séparabilité ayant un gain quadratrique par rapport aux méthodes connues. La troisième partie s'intéresse aux jeux quantiques. Nous présentons tout d'abord une analyse fine des jeux octaux classiques et donnons une stratégie optimale pour le jeu des dominos. Nous proposons ensuite une quantisation de certains jeux combinatoires, définissant ainsi la famille des jeux octaux quantiques. Nous présentons ainsi un modèle formel permettant de parler des jeux quantiques à information totale et proposons une approche qui utilise des pièges pour des jeux quantiques très étudiés, appelés jeux de dés à distance. La dernière partie étudie des problèmes d'optimisation, en développant pour cela des outils optimaux de recherche de minima. Ces outils nous ont permis d'analyser la complexité en requêtes de certains problèmes de graphes. Nous avons ainsi trouvé des algorithmes quantiques pour les problèmes de connectivité, forte connectivité, arbre couvrant de poids minimal et plus courts chemins à une source donnée. Puis, nous avons prouvé leur optimalité en utilisant des techniques de bornes inférieures, déterminant ainsi les limites du facteur de gain qu'offre l'informatique quantique pour résoudre ce problème.
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.
Le problème typique du physicien théoricien, tel qu'il peut être décrit dans certains manuels scolaires, consiste à rendre compte de faits expérimentaux et d'observations à l'aide d'un modèle théorique. L'expérimentateur (qui peut être la même personne) quant à lui valide ou invalide le modèle au moyen de nouvelles expériences. Pour le physicien et épistémologiste Thomas S. Kuhn (''La structure des révolutions scientifiques'', 1960), cette vision du progrès scientifique qui suppose, notons le en passant, que l'on ait affaire à des théories réfutables au sens de Popper, est quelque peu naïve. En effet, expérimentateurs et théoriciens sont déjà de connivence pour accepter les mêmes paradigmes au sens de Kuhn, c'est-à-dire en particulier qu'il y a accord, en général tacite, sur les problèmes susceptibles d'être formulés. Ils répondent malgré eux à des questions qu'ils ne se sont pas posés. Notre travail s'inscrit dans le cadre orthodoxe de la théorie quantique. Nous avons cependant tenté de répondre à quelques questions que l'on omet généralement de poser. Ceci aussi bien au niveau des méthodes et des concepts de la chimie théorique qu'au niveau de l'analyse de données expérimentales. Par exemple, dans nos travaux théoriques nous nous sommes demandé si la définition de certains concepts tenus pour fondamentaux était véritablement indépendante de toute approximation ou représentation arbitraire, et inversement si d'autres concepts supposés liés à une approximation particulière, ne pouvaient pas être étendus ou avoir une signification plus profonde que celle qu'on leur accorde habituellement (cas des surfaces de Born-Oppenheimer). Dans nos travaux d'analyse de données nous avons tenté de remonter à des données expérimentales aussi brutes que possible pour éviter les biais que peuvent introduire les traitements qu'elles subissent. Ces traitements sont fonctions des modèles physiques auxquels les données sont supposées se conformer et que nous avons remis en question. Depuis notre thèse, nous nous sommes efforcé de maintenir un équilibre entre une recherche fondamentale tournée vers la théorie et permettant de voir de façon plus synthétique ou plus critique, certains aspects de la chimie quantique, et une recherche tournée vers l'expérience et les applications astrophysiques. La présentation de nos travaux s'articulera donc naturellement sur deux volets. Notons aussi que cette présentation n'est pas exhaustive. En particulier nous n'aborderons pas ici nos travaux sur les hydrocarbones polycycliques aromatiques qui entrent dans une des thématiques traditionnelles de notre laboratoire. Notre exposé se limitera aux principaux projets de recherches dont nous avons eu l'initiative et qui ont donné lieu à des collaborations, (à l'exception de notre travail sur les bases flottantes dont il ne sera pas non plus question dans cette présentation). Ce choix nous a paru conforme à l'esprit de l'habilitation à diriger des recherches.
Le calcul quantique est nouveau paradigme qui sera peut-être en capacité de résoudre certains problèmes intéressants et très spécifiques plus vite qu'un ordinateur classique. Mais pour atteindre le régime dans lequel les ordinateurs quantiques seront plus efficaces que leurs équivalents classiques, plusieurs étapes cruciales doivent être atteintes. Les taux d'erreur des puces quantiques actuelles doivent être drastiquement améliorés, tout comme leur nombre de qubits, les algorithmes doivent évoluer pour prendre en compte le taux d'erreur élevé des puces, les compilateurs et implémentations doivent être adaptés à la puce quantique qui sera utilisée pour l'exécution et les façons d'analyser des états ou programmes quantiques nécessitent des améliorations.Dans cette thèse, nous nous concentrons sur certaines de ces étapes et améliorons l'état de l'art en essayant de se rapprocher le plus possible du régime où les ordinateurs quantiques auront un avantage sur les ordinateurs classiques. Nous commençons par montrer comment nous avons implémenté un algorithme quantique non trivial et analysé son comportement ainsi que les ressources nécessaires à son exécution.Cette analyse a confirmé que les puces quantiques actuelles étaient incapables d'exécuter ce genre d'implémentation, même après avoir pris en compte les subtilités dues au matériel et optimisé grandement le programme. Cet effort d'optimisation a donné lieu à l'implémentation de l'outil qprof, un profileur de programme quantique capable d'analyser des implémentations et de générer un rapport textuel et lisible résumant la hiérarchie des appels et leur coût approximatif.Nous présentons aussi un algorithme classique pour résoudre le problème du routage de qubit, une des étapes les plus coûteuse en terme de porte quantique additionnelle dans les compilateurs de programme quantiques. Cet algorithme permet de prendre en compte les calibrations les plus récentes de la puce quantique visée afin d'adapter le programme quantique compilé aux différents taux d'erreurs de la puce. Nous décrivons comment l'algorithme fonctionne et montrons qu'il apporte une amélioration substantielle de la fidélité de l'état quantique créé par le programme compilé par rapport à l'état de l'art.Nous avons aussi implémenté un algorithme variationnel permettant de résoudre des systèmes linéaires et analysé son comportement sur des puces quantiques actuelles ainsi que les besoins en ressources quantiques afin d'exécuter cet algorithme avec différents systèmes linéaires. Finalement, nous avons effectué une étude sur les erreurs présentes sur des qubits isolés et introduit une nouvelle visualisation permettant de mettre en avant des erreurs systématiques et non mitigées par les calibrations automatiques réalisées à intervalles réguliers sur les puces quantiques.
Bruit et capacité d'apprentissage en apprentissage automatique quantique Cette thèse est consacrée à l'exploration de l'interface entre l'informatique quantique et l'apprentissage automatique, en mettant l'accent sur les effets du bruit et de la décohérence. Dans la première partie, nous étudions l'utilisation de systèmes quantiques ouverts pour la réalisation de tâches classiques de reconnaissance des formes. En particulier, nous nous intéressons à l'impact du bruit sur les machines à noyau quantique dans une configuration de calcul à réservoir. Les modèles que nous considérons sont basés sur l'utilisation d'un système quantique de grande taille et non contrôlé, un réservoir, qui est excité par un signal d'entrée à traiter. Des mesures sont ensuite effectuées sur le système et une combinaison linéaire des résultats est optimisée afin de réaliser la tâche souhaitée. Dans le cadre théorique associé aux méthodes à noyau, nous analysons l'effet de la dissipation sur l'expressivité de ces modèles. Nous montrons que le bruit affectant le réservoir peut agir comme une régularisation implicite qui aide à prévenir l'ajustement excessif. Ces résultats sont accompagnés d'une étude numérique d'un ensemble de machines à noyaux bruitées basées sur des chaînes de spins quantiques sujets à de la décohérence, et dont l'évolution markovienne est décrite par une équation maîtresse de type Lindblad. Dans la deuxième partie de la thèse, nous nous concentrons sur les algorithmes quantiques variationnels. Nous y présentons un schéma de simulation classique efficace pour estimer des quantités moyennées à la sortie d'un circuit quantique paramétré dont les paramètres de rotation sont choisis aléatoirement. Nous étudions d'abord les canaux quantiques associés aux moyennes de rotations aléatoires d'un et de deux qubits autour d'un axe Z. Sous certaines hypothèses, nous montrons que ces canaux peuvent être décomposés en sommes convexes de canaux associés à des transformations unitaires de Clifford. Ce résultat peut être interprété comme un effet de décohérence artificiel induit par le choix aléatoire des angles de rotation. Il nous permet construire un schéma de simulation efficace basé sur le célèbre théorème de Gottesman-Knill. Cette méthode permet notamment d'estimer efficacement l'amplitude moyenne du gradient de la fonction de coût par des simulations classiques avec une complexité polynomiale en le nombre de qubits. Elle peut donc être utilisée pour explorer des stratégies de conception de circuits variationnels quantiques permettant d'éviter les difficultés d'entrainement due à une disparition du gradient.
Sécurité et efficacité du calcul quantique délégué L'information quantique promet de révolutionner notre monde, de la façon dont nous communiquons à la façon dont nous calculons, en tirant sa puissance directement des lois qui régissent le comportement de la nature à des échelles extrêmement petites - la mécanique quantique. Dans un avenir proche, le matériel des ordinateurs quantiques éventuellement utiles devrait rester très coûteux et donc hors de portée de la plupart des utilisateurs finaux intéressés. Dans un tel monde, il est important de fournir des garanties de sécurité aux clients qui souhaitent donner des instructions à distance à des serveurs quantiques, en gardant leurs données privées (aveuglement) et en vérifiant l'exactitude des résultats (vérification). Cette fonctionnalité de l'informatique quantique déléguée sécurisée a reçu beaucoup d'attention au cours des dernières années, mais il reste encore beaucoup de questions ouvertes. Dans cette thèse, nous explorons l'(im)possibilité de sécuriser les calculs quantiques délégués dans différents contextes : quel est le matériel auquel le client doit avoir un accès sécurisé, quel est le matériel minimum requis par le serveur, et comment les parties doivent-elles communiquer ? Ce travail est motivé par la volonté de faire tomber les barrières qui nous empêchent de sécuriser et de vérifier les calculs quantiques dans la pratique, en identifiant et en supprimant les frais généraux inutiles. Nous commençons par nous interroger sur la nécessité d'une communication quantique entre le client et le serveur, et nous constatons que, si dans certaines situations la communication classique est tout à fait suffisante, le plus souvent la sécurité des protocoles de délégation repose de manière irremplaçable sur le caractère quantique de l'information échangée entre les parties. Cela prouve que la communication quantique est en effet un atout essentiel dans notre boîte à outils cryptographique. Nous nous concentrons ensuite sur le serveur qui souffrait de frais généraux irréalisables dans les tentatives précédentes de vérification quantique. Nous montrons que pour une large classe de calculs quantiques intéressants, il n'y a pas de besoin fondamental de réserver du matériel supplémentaire pour des techniques cryptographiques. En effet, nous donnons des constructions concrètes de protocoles sécurisés qui atteignent la cécité et la vérification sur du matériel de la même taille que celui qui serait nécessaire pour effectuer le calcul original non sécurisé, et nous fournissons un moyen systématique d'optimiser leur efficacité dans des contextes personnalisés. Notre voyage nous amène ensuite au problème du calcul multipartite sécurisé quantique, une généralisation de la fonctionnalité précédente à plus de deux parties participantes qui se méfient mutuellement. Nous explorons comment les améliorations que nous avons obtenues dans le cadre bipartite peuvent être transférées au cas multipartite, et nous terminons par la présentation de deux expériences réelles qui démontrent l'impact pratique et la faisabilité dans le monde réel des résultats obtenus au cours de cette thèse.