Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Towards a formal compilation stack-frame in quantum computing

Agustín Borgna

Published Jan 13, 2023• 0 citations
Publisher

Abstract

Vers une formalisation d'une chaîne de compilation pour un ordinateur quantique L'avènement des ordinateurs quantiques capables de résoudre des problèmes irréalisables sur des ordinateurs classiques a motivé le développement de nouveaux langages et outils de programmation pour l'informatique quantique. Cependant, l'état de l'art actuel en matière de programmation quantique n'en est qu'à ses débuts. Dans cette thèse, nous présentons une série d'approches novatrices de différents aspects du processus de compilation quantique basé sur le calcul ZX. Tout d'abord, nous introduisons une nouvelle représentation intermédiaire pour les programmes quantiques capable d'encoder la récursion bornée et les structures de circuits répétés de manière compacte, basée sur les familles de l'extension Scalable du calcul ZX. Nous présentons ensuite un algorithme de compilation pour les circuits hybrides contenant à la fois des portes quantiques et classiques, basé sur l'optimisation de circuits purs de Duncan et al. Enfin, nous définissons le problème de la détection des sections de circuits quantiques qui peuvent être traduites en logique classique, et nous introduisons un algorithme heuristique pour le résoudre.

DOI
10.70675/48a49448z2a77z4bdaz9a11z6b16257bb4a5

Related papers

Formal Methods for Quantum Programming Languages

Dongho Lee

Méthodes Formelles pour les Langages de Programmation Quantiques Le modèle Qram est un modèle de calcul quantique pratique composé d’un ordinateur classique et un processus quantique qui communiquent entre eux. Le programme est exécuté sur l’ordinateur classique. Il envoie les instructions correspondant aux opérateurs quantiques sur le co-processeur, et reçoit le résultat de l’observation de l’état quantique. Ce modèle est considéré comme un modèle standard et plusieurs langages de programmation ont été conçus en basant sur ce modèle. Alors que les programmes dans ce modèle sont capables de réaliser tout calcul quantique grâce à l’usage de la mémoire quantique, il est difficile de les analyser sans l’aide d’un autre ordinateur quantique. Ce problème suscite le besoin pour des méthodes formelles pour les langages programmations quantiques : les outils formels pour raisonner sur l’optimisation du code, pour l’analyser des ressources, et pour spécifier et prouver les propriétés des programmes quantiques. La sémantique catégorique fait partie de ces méthodes qui fait le lien entre les opérateurs quantiques et les programmes et introduit le système logique qui peut décrire les propriétés sur l’état quantique dans le système de types. Bien que plusieurs travaux proposent des sémantiques catégoriques pour les langages de description de circuits quantiques, aucun ne supporte l’usage du résultat d’une mesure au sein du processeur classique (le ”levage dynamique”). Dans cette thèse, nous formalisons le levage dynamique qui transfère le résultat d’observations sur l’état quantique à l’information classique dans un langage de programmation de description de circuit quantique. En suivant l’approche du langage Proto-Quipper, nous définissons un langage typé de description de circuit quantique où l’information quantique levée est incorporée dans la structure ramifiée. Ensuite, le levage dynamique est formalisé dans le cadre de la sémantique opérationnelle et la sémantique catégorique. Notre sémantique catégorique est basée sur le modèle de Francisco Rios et Peter Selinger pour le langage programmation Proto-Quipper- M. Pourtant, pour formaliser le levage dynamique, nous construisons une catégorie de Kleisli en capturant la mesure quantique comme un effet de bord sur une catégorie concrète pour le circuit avec la mesure quantique. Nous prouvons le théorème de correction de la sémantique catégorique par rapport à la sémantique opérationnelle.

•Jul 21, 2022•1 citation

Implémentation, analyse et améliorations bas-niveau d'algorithmes quantiques pour le calcul scientifique

Adrien Suau

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.

•Oct 27, 2022•0 citations

Programming languages characterizing quantum efficiency

Mário Silva

Langages de programmation caractérisant l'efficacité quantique L'informatique quantique est un paradigme émergent de calcul, dans lequel des phénomènes physiques quantiques tels que l'intrication et la superposition sont exploités pour obtenir un avantage sur le calcul classique. Bien que le programmeur quantique dispose d'un large choix de langages de programmation, aucun ne permet de garantir la faisabilité de ses programmes. À cette fin, nous introduisons un langage de programmation quantique du premier ordre (FOQ) qui permet de raisonner sur la réalisabilité physique et la complexité des programmes quantiques. Nous introduisons des restrictions, vérifiables statiquement, sur les programmes FOQ qui nous permettent d'identifier des fragments sûrs et complets pour le temps polynomial quantique (PFOQ) et le temps polylogarithmique (LFOQ). Nous fournissons plusieurs exemples de programmes en temps polynomial et polylogarithmique capturés par ces fragments, représentant des fonctions quantiques pertinentes, telles que la transformée de Fourier quantique, l'arithmétique quantique, ainsi que des exemples comme la recherche dichotomique. Nous introduisons également de nouvelles techniques de compilation permettant de traduire des programmes PFOQ et LFOQ en circuits de complexité raisonnable, évitant l'explosion exponentielle pouvant résulter de l'utilisation récursive d'une instruction de contrôle quantique. Nous améliorons encore cette technique de compilation et définissons un fragment de FOQ qui est cohérent et complet pour le temps polynomial quantique, où la complexité en circuit de l'instruction conditionnelle quantique correspond au maximum des branches, et non leur somme. Nous développons un compilateur prototype implémentant ces idées pour les langages PFOQ et LFOQ.

•Jul 7, 2025•0 citations

Practical verification of quantum circuit transformations

Jérome Ricciardi

Vérification pratique des transformations de circuits quantiques L'informatique quantique, qui repose sur les principes de la physique quantique, promet des gains significatifs en termes de puissance de calcul. Cependant, elle introduit de nouveaux défis, notamment pour la vérification de programmes.En effet, les techniques de vérification classiques ne s'appliquent pas directement à l'informatique quantique. Cela s'explique principalement par l'utilisation de la mémoire quantique (unité d'information non standard) et de son opération de mesure, qui est le seul moyen de récupérer une information à partir d'un bit quantique et introduit un aspect probabiliste.Dans cette thèse, nous nous concentrons sur le modèle de calcul quantique par circuits et sur un aspect pratique de ce modèle : les transformations de circuit.Un circuit quantique peut être purement quantique (circuit unitaire) ou inclure du contrôle classique et de la mesure (circuit hybride).Les transformations de circuits se produisent tout au long du processus de calcul quantique, qu'il s'agisse de compiler un circuit décrit dans un langage de haut niveau vers un langage de bas niveau, d'optimiser un circuit pour un matériel particulier (transpilation), de changer de modèle de calcul (one-way measurement), ou de transférer un état quantique (téléportation).Chacune de ces transformations peut altérer le comportement du circuit ; nous avons donc besoin d'outils permettant de vérifier sa préservation.Mais la plupart des outils actuels sont limités au cas unitaire, donc limités à vérifier des transformations qui ne changent pas le type de circuit : un circuit unitaire est transformé en circuit unitaire.Et ceux qui s'aventurent dans le cas hybride sont limités à l'hybridation : un circuit unitaire est transformé en un circuit hybride.Alors que le vrai défi survient lors de l'introduction de fils auxiliaires, tels que les ancillas ou les discards (mesures intermédiaires non incluses dans la sortie du circuit), car il faut s'assurer que ces fils auxiliaires n'affectent pas les autres.Pour vérifier un circuit, plusieurs techniques existent (simulation, exécution symbolique, preuve), qui diffèrent par leur automatisation et leur scalabilité. La simulation, bien qu'automatisable, manque de scalabilité. L'exécution symbolique, automatisable, passe mieux à l'échelle. La preuve, insensible à l'échelle, est difficile à automatiser.Nous avons ainsi opté pour la preuve et pour l'exécution symbolique.Nous avons utilisé la preuve pour certifier une passe de compilation d'un langage de haut niveau vers un langage de bas niveau. Et l'exécution symbolique, en développant un outil de vérification d'équivalence de circuits hybrides avec discard.Pour nous aider dans la preuve, nous avons utilisé l'outil de preuve semi-automatique Qbricks, capable de prouver des circuits unitaires paramétrés basés sur les sommes de chemins, un formalisme permettant une modélisation compacte et encodable des circuits.En préalable au développement de notre outil de vérification de circuits hybrides avec discard, nous avons défini des relations d'équivalence partielles pour les circuits unitaires, ainsi qu'un mécanisme pour étendre les outils de vérification unitaires aux circuits hybrides.La combinaison de ces deux composants permet de traiter les circuits hybrides avec discard.Pour évaluer notre approche, nous avons implémenté dans l'outil SQbricks nos relations d'équivalence ainsi que notre mécanisme d'extension des outils limités aux unitaires.Nous avons démontré que les outils unitaires étendus au cas hybride sans discard surpassent, pour la plupart, largement l'état de l'art.Et qu'avec l'ajout d'un test de séparation au niveau unitaire, nous pouvons traiter des classes beaucoup plus vastes.

•Jun 4, 2026•0 citations

Adiabatic quantum computation

Jérémie Roland, Nicolas J. Cerf

Le développement de la Théorie du Calcul Quantique provient de l'idée qu'un ordinateur est avant tout un système physique, de sorte que ce sont les lois de la Nature elles-mêmes qui constituent une limite ultime sur ce qui peut être calculé ou non. L'intérêt pour cette discipline fut stimulé par la découverte par Peter Shor d'un algorithme quantique rapide pour factoriser un nombre, alors qu'actuellement un tel algorithme n'est pas connu en Théorie du Calcul Classique. Un autre résultat important fut la construction par Lov Grover d'un algorithme capable de retrouver un élément dans une base de donnée non-structurée avec un gain de complexité quadratique par rapport à tout algorithme classique. Alors que ces algorithmes quantiques sont exprimés dans le modèle ``standard' du Calcul Quantique, où le registre évolue de manière discrète dans le temps sous l'application successive de portes quantiques, un nouveau type d'algorithme a été récemment introduit, où le registre évolue continûment dans le temps sous l'action d'un Hamiltonien. Ainsi, l'idée à la base du Calcul Quantique Adiabatique, proposée par Edward Farhi et ses collaborateurs, est d'utiliser un outil traditionnel de la Mécanique Quantique, à savoir le Théorème Adiabatique, pour concevoir des algorithmes quantiques où le registre évolue sous l'influence d'un Hamiltonien variant très lentement, assurant une évolution adiabatique du système. Dans cette thèse, nous montrons tout d'abord comment reproduire le gain quadratique de l'algorithme de Grover au moyen d'un algorithme quantique adiabatique. Ensuite, nous montrons qu'il est possible de traduire ce nouvel algorithme adiabatique, ainsi qu'un autre algorithme de recherche à évolution Hamiltonienne, dans le formalisme des circuits quantiques, de sorte que l'on obtient ainsi trois algorithmes quantiques de recherche très proches dans leur principe. Par la suite, nous utilisons ces résultats pour construire un algorithme adiabatique pour résoudre des problèmes avec structure, utilisant une technique, dite de ``nesting', développée auparavant dans le cadre d'algorithmes quantiques de type circuit. Enfin, nous analysons la résistance au bruit de ces algorithmes adiabatiques, en introduisant un modèle de bruit utilisant la théorie des matrices aléatoires et en étudiant son effet par la théorie des perturbations.

•Sep 28, 2004•1 citation

Towards efficient quantum algorithms for optimization and sampling

Dániel Szilágyi

Vers des algorithmes quantiques efficaces pour l'optimisation et l'échantillonnage Récemment, avec l'avènement du big data et de l'apprentissage machine à grande échelle, il y a eu une demande croissante pour des algorithmes quantiques qui seraient plus directement applicables à des problèmes pertinents en pratique. Dans cette thèse, nous présentons trois algorithmes qui visent à nous rapprocher de cet objectif. Premièrement, nous développons un algorithme quantique pour l'optimisation cornettique, une classe de problèmes d'optimisation qui se situe entre les programmes linéaires et semi-définis en termes d'expressivité et de facilité de résolution. Ces problèmes sont le plus souvent résolus avec l'aide d'une méthode de point intérieur, dont la complexité est principalement imposée par le coût de la résolution d'une série de systèmes linéaires. Dans notre algorithme, nous résolvons ces systèmes linéaires de manière approximative à l'aide d'un algorithme quantique, et nous prouvons que la méthode des points intérieurs qui en résulte converge vers la solution correcte en un même nombre d'itérations. Nous donnons des preuves numériques que l'algorithme fournit des accélérations de bout en bout dans certaines applications de faible précision telles que les machines à vecteurs de support et l'optimisation de portefeuille financier. L'algorithme des systèmes linéaires quantiques que nous utilisons est le résultat d'une longue ligne de recherche engendrée par l'algorithme de système linéaire quantique de Harrow, Hassidim et Lloyd. Bien qu'il ait été prouvé qu'il est asymptotiquement optimal, le circuit correspondant compliqué et nécessite un prétraitement classique. La deuxième contribution de cette thèse est un algorithme quantique amélioré pour les systèmes linéaires, basé sur la méthode classique optimale de l'itération de Chebyshev. Enfin, nous observons que les algorithmes susmentionnés ont la propriété commune d'approximer l'unique vraie solution du problème donné. En général, la conception de tels algorithmes quantiques est difficile, car souvent la seule façon de récupérer (une approximation de) la vraie solution est d'exécuter l'algorithme plusieurs fois (soit naïvement, soit par amplification d'amplitude) et de calculer certaines statistiques (par exemple la moyenne) des sorties mesurées. Si les ordinateurs quantiques donnent intrinsèquement accès à l'échantillonnage de leurs sorties, pourrions-nous les exploiter pour accélérer les problèmes d'échantillonnage classiques? De manière surprenante, il s'avère que l'échantillonnage gaussien n'est pas un problème complètement résolu, même sur les ordinateurs classiques. Notre troisième contribution est un algorithme de Monte Carlo Hamiltonien classique pour l'échantillonnage gaussien dans le modèle d'interrogation du premier ordre. Nous surmontons et contournons plusieurs limites inférieures en prenant des étapes longues et aléatoires pour intégrer le hamiltonien au cœur de l'algorithme.

•Oct 20, 2022•0 citations
Vers une formalisation d'une chaîne de compilation pour un ordinateur quantique L'avènement des ordinateurs quantiques capables de résoudre des problèmes irréalisables sur des ordinateurs classiques a motivé le développement de nouveaux langages et outils de programmation pour l'informatique quantique. Cependant, l'état de l'art actuel en matière de programmation quantique n'en est qu'à ses débuts. Dans cette thèse, nous présentons une série d'approches novatrices de différents aspects du processus de compilation quantique basé sur le calcul ZX. Tout d'abord, nous introduisons une nouvelle représentation intermédiaire pour les programmes quantiques capable d'encoder la récursion bornée et les structures de circuits répétés de manière compacte, basée sur les familles de l'extension Scalable du calcul ZX. Nous présentons ensuite un algorithme de compilation pour les circuits hybrides contenant à la fois des portes quantiques et classiques, basé sur l'optimisation de circuits purs de Duncan et al. Enfin, nous définissons le problème de la détection des sections de circuits quantiques qui peuvent être traduites en logique classique, et nous introduisons un algorithme heuristique pour le résoudre.
Méthodes Formelles pour les Langages de Programmation Quantiques Le modèle Qram est un modèle de calcul quantique pratique composé d’un ordinateur classique et un processus quantique qui communiquent entre eux. Le programme est exécuté sur l’ordinateur classique. Il envoie les instructions correspondant aux opérateurs quantiques sur le co-processeur, et reçoit le résultat de l’observation de l’état quantique. Ce modèle est considéré comme un modèle standard et plusieurs langages de programmation ont été conçus en basant sur ce modèle. Alors que les programmes dans ce modèle sont capables de réaliser tout calcul quantique grâce à l’usage de la mémoire quantique, il est difficile de les analyser sans l’aide d’un autre ordinateur quantique. Ce problème suscite le besoin pour des méthodes formelles pour les langages programmations quantiques : les outils formels pour raisonner sur l’optimisation du code, pour l’analyser des ressources, et pour spécifier et prouver les propriétés des programmes quantiques. La sémantique catégorique fait partie de ces méthodes qui fait le lien entre les opérateurs quantiques et les programmes et introduit le système logique qui peut décrire les propriétés sur l’état quantique dans le système de types. Bien que plusieurs travaux proposent des sémantiques catégoriques pour les langages de description de circuits quantiques, aucun ne supporte l’usage du résultat d’une mesure au sein du processeur classique (le ”levage dynamique”). Dans cette thèse, nous formalisons le levage dynamique qui transfère le résultat d’observations sur l’état quantique à l’information classique dans un langage de programmation de description de circuit quantique. En suivant l’approche du langage Proto-Quipper, nous définissons un langage typé de description de circuit quantique où l’information quantique levée est incorporée dans la structure ramifiée. Ensuite, le levage dynamique est formalisé dans le cadre de la sémantique opérationnelle et la sémantique catégorique. Notre sémantique catégorique est basée sur le modèle de Francisco Rios et Peter Selinger pour le langage programmation Proto-Quipper- M. Pourtant, pour formaliser le levage dynamique, nous construisons une catégorie de Kleisli en capturant la mesure quantique comme un effet de bord sur une catégorie concrète pour le circuit avec la mesure quantique. Nous prouvons le théorème de correction de la sémantique catégorique par rapport à la sémantique opérationnelle.
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.
Langages de programmation caractérisant l'efficacité quantique L'informatique quantique est un paradigme émergent de calcul, dans lequel des phénomènes physiques quantiques tels que l'intrication et la superposition sont exploités pour obtenir un avantage sur le calcul classique. Bien que le programmeur quantique dispose d'un large choix de langages de programmation, aucun ne permet de garantir la faisabilité de ses programmes. À cette fin, nous introduisons un langage de programmation quantique du premier ordre (FOQ) qui permet de raisonner sur la réalisabilité physique et la complexité des programmes quantiques. Nous introduisons des restrictions, vérifiables statiquement, sur les programmes FOQ qui nous permettent d'identifier des fragments sûrs et complets pour le temps polynomial quantique (PFOQ) et le temps polylogarithmique (LFOQ). Nous fournissons plusieurs exemples de programmes en temps polynomial et polylogarithmique capturés par ces fragments, représentant des fonctions quantiques pertinentes, telles que la transformée de Fourier quantique, l'arithmétique quantique, ainsi que des exemples comme la recherche dichotomique. Nous introduisons également de nouvelles techniques de compilation permettant de traduire des programmes PFOQ et LFOQ en circuits de complexité raisonnable, évitant l'explosion exponentielle pouvant résulter de l'utilisation récursive d'une instruction de contrôle quantique. Nous améliorons encore cette technique de compilation et définissons un fragment de FOQ qui est cohérent et complet pour le temps polynomial quantique, où la complexité en circuit de l'instruction conditionnelle quantique correspond au maximum des branches, et non leur somme. Nous développons un compilateur prototype implémentant ces idées pour les langages PFOQ et LFOQ.
Vérification pratique des transformations de circuits quantiques L'informatique quantique, qui repose sur les principes de la physique quantique, promet des gains significatifs en termes de puissance de calcul. Cependant, elle introduit de nouveaux défis, notamment pour la vérification de programmes.En effet, les techniques de vérification classiques ne s'appliquent pas directement à l'informatique quantique. Cela s'explique principalement par l'utilisation de la mémoire quantique (unité d'information non standard) et de son opération de mesure, qui est le seul moyen de récupérer une information à partir d'un bit quantique et introduit un aspect probabiliste.Dans cette thèse, nous nous concentrons sur le modèle de calcul quantique par circuits et sur un aspect pratique de ce modèle : les transformations de circuit.Un circuit quantique peut être purement quantique (circuit unitaire) ou inclure du contrôle classique et de la mesure (circuit hybride).Les transformations de circuits se produisent tout au long du processus de calcul quantique, qu'il s'agisse de compiler un circuit décrit dans un langage de haut niveau vers un langage de bas niveau, d'optimiser un circuit pour un matériel particulier (transpilation), de changer de modèle de calcul (one-way measurement), ou de transférer un état quantique (téléportation).Chacune de ces transformations peut altérer le comportement du circuit ; nous avons donc besoin d'outils permettant de vérifier sa préservation.Mais la plupart des outils actuels sont limités au cas unitaire, donc limités à vérifier des transformations qui ne changent pas le type de circuit : un circuit unitaire est transformé en circuit unitaire.Et ceux qui s'aventurent dans le cas hybride sont limités à l'hybridation : un circuit unitaire est transformé en un circuit hybride.Alors que le vrai défi survient lors de l'introduction de fils auxiliaires, tels que les ancillas ou les discards (mesures intermédiaires non incluses dans la sortie du circuit), car il faut s'assurer que ces fils auxiliaires n'affectent pas les autres.Pour vérifier un circuit, plusieurs techniques existent (simulation, exécution symbolique, preuve), qui diffèrent par leur automatisation et leur scalabilité. La simulation, bien qu'automatisable, manque de scalabilité. L'exécution symbolique, automatisable, passe mieux à l'échelle. La preuve, insensible à l'échelle, est difficile à automatiser.Nous avons ainsi opté pour la preuve et pour l'exécution symbolique.Nous avons utilisé la preuve pour certifier une passe de compilation d'un langage de haut niveau vers un langage de bas niveau. Et l'exécution symbolique, en développant un outil de vérification d'équivalence de circuits hybrides avec discard.Pour nous aider dans la preuve, nous avons utilisé l'outil de preuve semi-automatique Qbricks, capable de prouver des circuits unitaires paramétrés basés sur les sommes de chemins, un formalisme permettant une modélisation compacte et encodable des circuits.En préalable au développement de notre outil de vérification de circuits hybrides avec discard, nous avons défini des relations d'équivalence partielles pour les circuits unitaires, ainsi qu'un mécanisme pour étendre les outils de vérification unitaires aux circuits hybrides.La combinaison de ces deux composants permet de traiter les circuits hybrides avec discard.Pour évaluer notre approche, nous avons implémenté dans l'outil SQbricks nos relations d'équivalence ainsi que notre mécanisme d'extension des outils limités aux unitaires.Nous avons démontré que les outils unitaires étendus au cas hybride sans discard surpassent, pour la plupart, largement l'état de l'art.Et qu'avec l'ajout d'un test de séparation au niveau unitaire, nous pouvons traiter des classes beaucoup plus vastes.
Le développement de la Théorie du Calcul Quantique provient de l'idée qu'un ordinateur est avant tout un système physique, de sorte que ce sont les lois de la Nature elles-mêmes qui constituent une limite ultime sur ce qui peut être calculé ou non. L'intérêt pour cette discipline fut stimulé par la découverte par Peter Shor d'un algorithme quantique rapide pour factoriser un nombre, alors qu'actuellement un tel algorithme n'est pas connu en Théorie du Calcul Classique. Un autre résultat important fut la construction par Lov Grover d'un algorithme capable de retrouver un élément dans une base de donnée non-structurée avec un gain de complexité quadratique par rapport à tout algorithme classique. Alors que ces algorithmes quantiques sont exprimés dans le modèle ``standard' du Calcul Quantique, où le registre évolue de manière discrète dans le temps sous l'application successive de portes quantiques, un nouveau type d'algorithme a été récemment introduit, où le registre évolue continûment dans le temps sous l'action d'un Hamiltonien. Ainsi, l'idée à la base du Calcul Quantique Adiabatique, proposée par Edward Farhi et ses collaborateurs, est d'utiliser un outil traditionnel de la Mécanique Quantique, à savoir le Théorème Adiabatique, pour concevoir des algorithmes quantiques où le registre évolue sous l'influence d'un Hamiltonien variant très lentement, assurant une évolution adiabatique du système. Dans cette thèse, nous montrons tout d'abord comment reproduire le gain quadratique de l'algorithme de Grover au moyen d'un algorithme quantique adiabatique. Ensuite, nous montrons qu'il est possible de traduire ce nouvel algorithme adiabatique, ainsi qu'un autre algorithme de recherche à évolution Hamiltonienne, dans le formalisme des circuits quantiques, de sorte que l'on obtient ainsi trois algorithmes quantiques de recherche très proches dans leur principe. Par la suite, nous utilisons ces résultats pour construire un algorithme adiabatique pour résoudre des problèmes avec structure, utilisant une technique, dite de ``nesting', développée auparavant dans le cadre d'algorithmes quantiques de type circuit. Enfin, nous analysons la résistance au bruit de ces algorithmes adiabatiques, en introduisant un modèle de bruit utilisant la théorie des matrices aléatoires et en étudiant son effet par la théorie des perturbations.
Vers des algorithmes quantiques efficaces pour l'optimisation et l'échantillonnage Récemment, avec l'avènement du big data et de l'apprentissage machine à grande échelle, il y a eu une demande croissante pour des algorithmes quantiques qui seraient plus directement applicables à des problèmes pertinents en pratique. Dans cette thèse, nous présentons trois algorithmes qui visent à nous rapprocher de cet objectif. Premièrement, nous développons un algorithme quantique pour l'optimisation cornettique, une classe de problèmes d'optimisation qui se situe entre les programmes linéaires et semi-définis en termes d'expressivité et de facilité de résolution. Ces problèmes sont le plus souvent résolus avec l'aide d'une méthode de point intérieur, dont la complexité est principalement imposée par le coût de la résolution d'une série de systèmes linéaires. Dans notre algorithme, nous résolvons ces systèmes linéaires de manière approximative à l'aide d'un algorithme quantique, et nous prouvons que la méthode des points intérieurs qui en résulte converge vers la solution correcte en un même nombre d'itérations. Nous donnons des preuves numériques que l'algorithme fournit des accélérations de bout en bout dans certaines applications de faible précision telles que les machines à vecteurs de support et l'optimisation de portefeuille financier. L'algorithme des systèmes linéaires quantiques que nous utilisons est le résultat d'une longue ligne de recherche engendrée par l'algorithme de système linéaire quantique de Harrow, Hassidim et Lloyd. Bien qu'il ait été prouvé qu'il est asymptotiquement optimal, le circuit correspondant compliqué et nécessite un prétraitement classique. La deuxième contribution de cette thèse est un algorithme quantique amélioré pour les systèmes linéaires, basé sur la méthode classique optimale de l'itération de Chebyshev. Enfin, nous observons que les algorithmes susmentionnés ont la propriété commune d'approximer l'unique vraie solution du problème donné. En général, la conception de tels algorithmes quantiques est difficile, car souvent la seule façon de récupérer (une approximation de) la vraie solution est d'exécuter l'algorithme plusieurs fois (soit naïvement, soit par amplification d'amplitude) et de calculer certaines statistiques (par exemple la moyenne) des sorties mesurées. Si les ordinateurs quantiques donnent intrinsèquement accès à l'échantillonnage de leurs sorties, pourrions-nous les exploiter pour accélérer les problèmes d'échantillonnage classiques? De manière surprenante, il s'avère que l'échantillonnage gaussien n'est pas un problème complètement résolu, même sur les ordinateurs classiques. Notre troisième contribution est un algorithme de Monte Carlo Hamiltonien classique pour l'échantillonnage gaussien dans le modèle d'interrogation du premier ordre. Nous surmontons et contournons plusieurs limites inférieures en prenant des étapes longues et aléatoires pour intégrer le hamiltonien au cœur de l'algorithme.