L'Adaptativité dans l'Apprentissage Classique et Quantique 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.
L'Adaptativité dans l'Apprentissage Classique et Quantique 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.
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.
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.
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.
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.
Cette thèse se situe à la frontière entre l’informatique quantique et l’apprentissage artificiel et a pour objectif le traitement des données dans de très grandes dimensions. L’apprentissage artificiel quantique est un nouveau domaine d’étude avec de récents travaux sur les versions quantiques d’algorithmes supervisés et non supervisés. Ces dernières années, de nombreux algorithmes d’apprentissage artificiel quantique ont été proposés afin d’améliorer le temps de traitement des algorithmes classiques. La première contribution de cette thèse est de donner un aperçu sur le domaine quantique dans l’apprentissage artificiel. Ensuite, la quantification des algorithmes classiques. Nous avons proposé une analyse et une comparaison des différentes distances pour les algorithmes de clustering basés sur des prototypes. Pour un ordinateur conventionnel, calculer les distances euclidiennes est facile, mais le faire de la même manière sur un ordinateur quantique serait beaucoup plus compliqué et exigerait plus de qubits que ce que nous pouvons nous permettre. Pour définir une distance quantique, nous utiliserons la nature probabiliste des qubits pour mesurer les amplitudes probabiliste. Pour les algorithmes de clustering quantique, les distances sont nécessaires mais ne doivent pas nécessairement être proportionnelles à la distance réelle, elles doivent avoir qu’une corrélation positive avec elle. Tous les algorithmes de clustering basés sur des prototypes pourraient être résolus en utilisant ces distances. En tant qu’application de cette tâche, nous avons présenté une version quantique de K-means qui est un algorithme de clustering basé sur un prototype. Cet algorithme quantique K-means donne une bonne classification tout comme sa version classique, la seule différence réside dans la complexité: alors que la version classique de K-means prend du temps polynomial, la version quantique ne prend que du temps logarithmique surtout en grand ensembles de données. Nous avons également proposé la version quantique de la factorisation matricielle seminon négative ainsi que la version collaborative de ces algorithmes à savoir: K-means quantique collaboratif et la factorisation matricielle semi-non négative quantique collaborative qui se basent sur la combinaison de plusieurs solutions de clustering pour obtenir une meilleure solution en termes de clustering et de complexité.
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.