Ce travail porte sur les algorithmes quantiques pour le mélange de chaînes de Markov non-réversibles et de leur décomposition en circuits. Il commence par la description des idées fondamentales sous-jacentes aux algorithmes quantiques : implémentations d'opérateurs par projection d'unitaires, structure spectrale du produit de réflexions et traitement de signal. Viennent ensuite la définition des processus de Markov ergodiques et celle de leur temps de mélange vers une mesure stationnaire. On définit alors les marches quantiques ergodiques comme unitaires ayant pour unique point fixe l'état cohérent correspondant à la loi stationnaire. Sont ensuite introduites les trois contributions majeures de cette thèse. La première construction centrale porte sur les opérations contrôlées, d'aussi grande importance en informatique quantique que classique. On fournit la première construction de portes NOT contrôlées en profondeur polylogarithmique à l'aide d'un seul bit de mémoire ancillaire. On étudie ensuite les marches quantiques de Szegedy de chaînes de Markov non-réversibles. On introduit un temps de réversibilization et montre que l'on peut réfléchir au travers l'espace engendré par la loi stationnaire en la moyenne géométrique du temps de mélange et de ce temps de réversibilisation. Ce résultat étend les résultats connus du cadre réversible. Enfin, on fournit une implémentation quantique de l'algorithme de Metropolis-Hastings avec peu de qubits ancillaires. Ce résultat est obtenu grâce à la définition d'un noyau dual sur les paires d'états possibles. La première marginale évoluant selon le noyau de Metropolis-Hastings, elle présente les mêmes propriétés de convergence.
Ce travail porte sur les algorithmes quantiques pour le mélange de chaînes de Markov non-réversibles et de leur décomposition en circuits. Il commence par la description des idées fondamentales sous-jacentes aux algorithmes quantiques : implémentations d'opérateurs par projection d'unitaires, structure spectrale du produit de réflexions et traitement de signal. Viennent ensuite la définition des processus de Markov ergodiques et celle de leur temps de mélange vers une mesure stationnaire. On définit alors les marches quantiques ergodiques comme unitaires ayant pour unique point fixe l'état cohérent correspondant à la loi stationnaire. Sont ensuite introduites les trois contributions majeures de cette thèse. La première construction centrale porte sur les opérations contrôlées, d'aussi grande importance en informatique quantique que classique. On fournit la première construction de portes NOT contrôlées en profondeur polylogarithmique à l'aide d'un seul bit de mémoire ancillaire. On étudie ensuite les marches quantiques de Szegedy de chaînes de Markov non-réversibles. On introduit un temps de réversibilization et montre que l'on peut réfléchir au travers l'espace engendré par la loi stationnaire en la moyenne géométrique du temps de mélange et de ce temps de réversibilisation. Ce résultat étend les résultats connus du cadre réversible. Enfin, on fournit une implémentation quantique de l'algorithme de Metropolis-Hastings avec peu de qubits ancillaires. Ce résultat est obtenu grâce à la définition d'un noyau dual sur les paires d'états possibles. La première marginale évoluant selon le noyau de Metropolis-Hastings, elle présente les mêmes propriétés de convergence.
Algorithmes et Circuits Quantiques pour le Mélange de Chaînes de Markov Non-Réversibles Ce travail porte sur les algorithmes quantiques pour le mélange de chaînes de Markov non-réversibles et de leur décomposition en circuits. Il commence par la description des idées fondamentales sous-jacentes aux algorithmes quantiques : implémentations d'opérateurs par projection d'unitaires, structure spectrale du produit de réflexions et traitement de signal. Viennent ensuite la définition des processus de Markov ergodiques et celle de leur temps de mélange vers une mesure stationnaire. On définit alors les marches quantiques ergodiques comme unitaires ayant pour unique point fixe l'état cohérent correspondant à la loi stationnaire. Sont ensuite introduites les trois contributions majeures de cette thèse. La première construction centrale porte sur les opérations contrôlées, d'aussi grande importance en informatique quantique que classique. On fournit la première construction de portes NOT contrôlées en profondeur polylogarithmique à l'aide d'un seul bit de mémoire ancillaire. On étudie ensuite les marches quantiques de Szegedy de chaînes de Markov non-réversibles. On introduit un temps de réversibilization et montre que l'on peut réfléchir au travers l'espace engendré par la loi stationnaire en la moyenne géométrique du temps de mélange et de ce temps de réversibilisation. Ce résultat étend les résultats connus du cadre réversible. Enfin, on fournit une implémentation quantique de l'algorithme de Metropolis-Hastings avec peu de qubits ancillaires. Ce résultat est obtenu grâce à la définition d'un noyau dual sur les paires d'états possibles. La première marginale évoluant selon le noyau de Metropolis-Hastings, elle présente les mêmes propriétés de convergence.
Algorithmes quantiques pour la méthode de Monte Carlo La méthode de Monte Carlo est un paradigme central de l'algorithmique basée sur l'analyse statistique et sur les techniques d'échantillonnage aléatoire appliquées aux problèmes ayant une interprétation probabiliste. Cette thèse explore les avantages qu'offrirait un ordinateur quantique pour augmenter l'efficacité de cette méthode. Nous étudions dans un premier temps le problème d'estimation de valeurs moyennes par des techniques à temps de calcul minimal. Nous développons de nouveaux algorithmes quantiques pour estimer l'espérance d'une variable aléatoire réelle produite en sortie d'un processus quantique. Les estimateurs que nous construisons procurent une accélération quadratique par rapport au nombre d'échantillons classiques nécessaires pour obtenir une borne d'erreur sous-gaussienne ou une (epsilon,delta)-approximation. Nous décrivons également un cadre théorique fournissant une notion de «temps d'arrêt» pour un processus quantique générant une variable aléatoire. Nous démontrons que le problème d'estimation de la moyenne peut être résolu plus efficacement lorsque le temps d'arrêt moyen du processus sous-jacent est court. Ces résultats sont appliqués au développement d'un algorithme de requête quantique quasi-optimal pour approximer le nombre de triangles dans un graphe. Dans un second temps, nous étudions le problème d'échantillonnage préférentiel et ses applications en optimisation stochastique. Nous construisons un algorithme quantique pour échantillonner plusieurs éléments d'une distribution finie spécifiée par un vecteur de probabilité. Notre approche résout le problème plus général consistant à préparer plusieurs copies d'un état quantique dont les amplitudes sont accessibles via un oracle. L'utilité de ce résultat est illustrée à travers le développement de deux algorithmes hybrides quantiques-classiques basés sur la méthode des poids multiplicatifs et sur l'algorithme du gradient stochastique. Ces deux applications concernent la prédiction en ligne avec conseil d'experts, et la minimisation des fonctions sous-modulaires. La dernière partie de cette thèse est consacrée à l'étude des algorithmes quantiques à mémoire limitée. Nous étudions tout d'abord le problème d'approximation des moments de fréquence dans le modèle de flots de données à passes multiples. Nous construisons un algorithme quantique qui nécessite une quantité de mémoire moindre que les meilleurs algorithmes de streaming classiques possible. Notre méthode repose sur les estimateurs quantiques de moyenne susmentionnés et sur des techniques de simulation de calcul reversible. Nous explorons ensuite certaines limites des algorithmes à mémoire restreinte dans le modèle de requête quantique. Nous développons une nouvelle approche pour obtenir des bornes inférieures temps-mémoire, basée sur une technique récente d'enregistrement des requêtes quantiques. Ce résultat est appliqué au problème de la recherche de paires de collisions dans une fonction aléatoire. Nous démontrons que la complexité en requête quantique de cette tâche augmente lorsque la quantité de mémoire disponible diminue.
L'équation de Schrödinger polyélectronique régit l'évolution non relativiste des systèmes quantiques tels que les électrons, atomes et molécules. La chimie quantique ab initio consiste à trouver des solutions approximées de cette équation afin de prédire des propriétés moléculaires comme les longueurs de liaison, les spectres vibrationnels et les mécanismes réactionnels. Malgré les immenses progrès de la puissance de calcul, atteindre la précision chimique (une erreur d'énergie inférieure à 1 kcal/mol) reste exponentiellement coûteux pour les algorithmes classiques lorsque la taille du système augmente. Cette limite a conduit à envisager l'informatique quantique comme alternative pour la simulation moléculaire, les ordinateurs quantiques obéissant aux mêmes principes physiques que les systèmes simulés. Il a été établi que, sous certaines conditions, l'équation de Schrödinger moléculaire pouvait être résolue en temps polynomial sur un ordinateur quantique, permettant en principe une accélération exponentielle par rapport aux méthodes classiques. La concrétisation de cet avantage reste un problème ouvert et requiert des avancées tant matérielles (stabilité des processeurs) que algorithmiques (consommation de ressources). Ce dernier aspect constitue l'objectif principal de cette thèse. Trois défis fondamentaux sont identifiés: établir une correspondance et une discrétisation efficace entre le problème de structure électronique et les qubits; concevoir des algorithmes pour préparer de bonnes approximations de l'état fondamental ; décomposer les opérations quantiques en circuits implémentables à coût minimal. La première partie traite du court terme, où le faible nombre de qubits et le bruit limitent les opérations exécutables. Dans ce contexte, le Variational Quantum Eigensolver (VQE) et son extension adaptative ADAPT-VQE sont des références établies. Nous proposons plusieurs améliorations pour la construction adaptative d'ansätze. L'algorithme Greedy Gradient-Free Adaptive VQE simplifie le processus d'optimisation, réduisant considérablement la consommation de ressources et permettant même une démonstration sur un processeur de 25 qubits. La méthode Overlap-ADAPT-VQE introduit un schéma de compactification variationnelle qui reconstruit des approximations d'états quantiques cibles, permettant en chimie quantique d'accélérer significativement la convergence du VQE pour divers niveaux de corrélation électronique. Nous développons ensuite une stratégie d'initialisation des registres quantiques à partir de fonctions d'onde corrélées issues de calculs classiques, pour combiner calcul haute performance et post-traitement quantique. La seconde partie adopte une perspective de long terme centrée sur le comportement asymptotique des algorithmes. Nous présentons une décomposition de la porte NOT multi-contrôlée avec une profondeur de circuit polylogarithmique en nombre de qubits de contrôle, offrant une amélioration exponentielle sur les approches linéaires existantes. Enfin, nous proposons une méthode de chimie quantique en espace réel, compatible avec les algorithmes quantiques d'extraction de valeurs propres. L'objectif étant d'améliorer la convergence spatiale en remplaçant les discrétisations uniformes, utilisées dans la plupart des approches en première quantification, par des grilles non uniformes, adaptées à la molécule, qui concentrent les points de discrétisation dans les zones de forte densité électronique. Nous étendons cette stratégie aux hamiltoniens transcorrélés : des opérateurs qui régularisent les singularités du potentiel coulombien, et dont les fonctions propres sont lisses dans l'espace. Notre approche est plurielle, explorant tous les niveaux d'abstraction, de la théorie à l'implémentation, et couvrant des algorithmes exploitables sur des machines actuelles, et d'autres destinés aux architectures de long terme. Ces contributions renforcent les fondements des algorithmes quantiques pour la simulation moléculaire.
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.
Circuits quantiques bruités pour l'optimisation combinatoire Alors que les ordinateurs quantiques croissent en taille tout en restant affectés par le bruit, un défi clé consiste à déterminer quand et comment ils peuvent surpasser les meilleurs algorithmes classiques sur des tâches pratiques. Cela nécessite le développement d'algorithmes de simulation de circuits quantiques hautement efficaces. Les algorithmes de rétropropagation de Pauli font partie des plus prometteurs, ayant montré leur efficacité dans la simulation de certaines classes de circuits quantiques paramétrés, candidats sérieux pour l'avantage quantique à court terme, sous des hypothèses de circuits aléatoires et de bruit de dépolarisation. Cependant, leur efficacité n'avait pas été démontrée pour des modèles de bruit nonunital plus réalistes, tels que l'amortissement d'amplitude, qui capturent mieux le comportement des ordinateurs quantiques actuels. Nous comblons cette lacune en adaptant la rétropropagation de Pauli à la plupart des canaux de bruit à un qubit, incluant le bruit nonunital, et en prouvant qu'elle reste efficace sous ces conditions. Notre algorithme est parallélisable, économe en mémoire, et ne requiert aucune hypothèse sur la localité de l'observable, la géométrie de la puce quantique, ou la profondeur du circuit. Bien que le bruit des ordinateurs quantiques puisse fortement affecter la puissance de calcul dans des circuits hautement structurés et tolérants aux erreurs, nos résultats indiquent peu de différence pour la plupart des architectures variationnelles. Ceci établit la rétropropagation de Pauli comme une méthode efficace pour simuler les dispositifs quantiques bruités sous des hypothèses de bruit réalistes. Bien que ces avancées améliorent notre capacité à simuler des observables bruités, de nombreuses applications pratiques, incluant l'optimisation combinatoire, nécessitent un accès direct aux chaînes de bits produites par les circuits quantiques, car celles-ci encodent les solutions souhaitées. La réplication classique de tels échantillons bruités a jusqu'à présent été limitée au-delà du cadre des circuits aléatoires. Pour combler cette lacune, nous nous concentrons d'abord sur les problèmes dont les fonctions objectif ne dépendent que des corrélations sur deux sites, tel que Max-Cut, et appliquons des techniques d'arrondissement aléatoire gaussien aux marginales à deux qubits du circuit. Ceci produit des échantillons classiques dont le coût espéré est prouvablement proche de celui du dispositif quantique bruité. Des simulations à grande échelle et des expériences sur les ordinateurs quantiques d'IBM confirment que les échantillons arrondis reproduisent la distribution d'énergie complète, avec un comportement similaire sous divers modèles de bruit. Couplé avec la rétropropagation de Pauli pour estimer efficacement les marginales bruitées, cela donne un échantillonneur classique de bout en bout opérant en temps polynomial pour une large classe de circuits variationnels bruités. Nos résultats montrent donc que des circuits quantiques suffisamment bruités pour l'optimisation combinatoire peuvent être échantillonnés classiquement, clarifiant où les ordinateurs quantiques à court terme peuvent ou ne peuvent pas surpasser les algorithmes classiques.Enfin, nous allons au-delà des marginales sur un et deux sites et présentons un algorithme qui échantillonne des chaînes de bits valides directement depuis une distribution d'entropie maximale avec des moments correspondant à ceux du circuit quantique. Cette méthode ne repose pas sur la localité ou la parcimonie de l'Hamiltonien du problème et fonctionne bien sur une variété de circuits quantiques, incluant des circuits profonds sur de nombreux qubits. Lorsqu'elle est combinée avec la propagation de Pauli ou la mitigation d'erreur, elle fournit un pipeline pratique pour obtenir des échantillons de circuits quantiques à court terme, où la correction d'erreur pourrait ne pas encore être disponible.
Cette thèse présente différents résultats portant sur deux thèmes précis dans le domaine de l'information quantique. Le premier de ces thèmes concerne l'interférence présente dans les algorithmes quantiques. Par l'intermédiaire d’une mesure récemment introduite dans la littérature, il est possible de quantifier l'interférence présente dans tout algorithme quantique, dans le but de vérifier si il existe un lien entre interférence et ressource computationnelle. Pour ce faire, deux types de modèles statistiques d'algorithmes quantiques ont été utilisés. Le premier type, issu de la théorie des matrices aléatoires, est l'ensemble circulaire unitaire(CUE) tandis que le second est un ensemble de circuits quantiques, construits par des séquences aléatoires de portes quantiques. Les résultats analytiques et numériques obtenus dans cette thèse montrent qu'en moyenne tout algorithme quantique contient une grande quantité d'interférence. L'étape supplémentaire fût d'étudier l'influence de la décohérence engendrée par un bain thermique sur le comportement statistique de l'interférence. Grâce à l'utilisation de méthodes mathématiques d'intégrations sur le groupe unitaire U (N ), il est possible de généraliser les résultats analytiques et numériques précédents pour inclure les effets de la décohérence. Le deuxième thème étudié concerne la possibilité d'utiliser des algorithmes quantiques pour créer efficacement des ensembles de matrices aléatoires. Pendant les travaux sur l'interférence, une équivalence entre CUE et le modèle de circuits quantiques aléatoires fût observée. On peut attendre que de tels circuits quantiques aléatoires puissent être utilisé pour construire des matrices aléatoires distribuées comme CUE. Les résultats numériques de cette thèse montrent que certaines quantités statistiques propres à CUE sont bien reproduites par le modèle de séquences aléatoires, ceci de manière efficace. L'efficacité signifie que les séquences sont constituées d'un nombre de portes qui augmente comme le logarithme de la taille des matrices produites. Ces résultats sont en parfait accord avec des travaux analytiques récemment publiés.