La question ne fait maintenant plus débat : le passage à l'échelle commande de nouvelles stratégies algorithmiques. En chimie, une approche originale - la méthode Monte-Carlo quantique ou QMC - exploite massivement le parallélisme intrinsèque des méthodes probabilistes. Une implémentation judicieuse peut même y ajouter une vraie résilience aux pannes matérielles...
La question ne fait maintenant plus débat : le passage à l'échelle commande de nouvelles stratégies algorithmiques. En chimie, une approche originale - la méthode Monte-Carlo quantique ou QMC - exploite massivement le parallélisme intrinsèque des méthodes probabilistes. Une implémentation judicieuse peut même y ajouter une vraie résilience aux pannes matérielles...
Nous presentons plusieurs contributions methodologiques aux approches de type monte carlo quantique et quelques applications a des problemes de la matiere condensee et de la chimie theorique. Apres un expose general, nous presentons une demonstration originale de l'instabilite de l'algorithme sans biais le plus naturel (methode pure diffusion monte carlo). Tres recemment, des approches basees sur un processus de reconfiguration stochastique d'une population de marcheurs ont ete developpees pour y remedier. Nous proposons ici une optimisation substantielle de ce type de methode. Nous considerons ensuite une approche originale pour ameliorer l'echantillonnage de l'espace des configurations. Pour cela nous montrons qu'il est possible d'integrer exactement l'evolution temporelle des trajectoires stochastiques confinees dans un domaine donne. Un deuxieme type de developpement vise a reduire la variance des quantites moyennees : introduction de fonctions d'onde de qualite pour des modeles quantiques unidimensionnels et mise en place d'un principe de variance nulle pour le calcul de toute observable quantique. Notre application principale est la mise en evidence d'une transition de mott metal-isolant pour une generalisation tres simple du modele de hubbard unidimensionnel (modele su(n), n > 2). A cette occasion nous avons developpe une methodologie theorique et numerique efficace pour analyser les transitions de phase continues dans les modeles quantiques unidimensionnels. Utilisant le cadre theorique de la bosonisation, nous effectuons un controle non-perturbatif des predictions theoriques au moyen de resultats monte carlo quantique de grande precision. Nous presentons egalement d'autres applications (oscillateur quartique, atome d'helium, modele d'ising bidimensionnel) mettant en valeur les differentes ameliorations proposees.
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.
Simulations de Monte Carlo quantique améliorées : de systèmes ouverts aux solides cristallins Dans cette thèse nous présentons des progrès algorithmiques ainsi que plusieurs applications des méthodes de Monte Carlo quantique (QMC) pour simulations à partir des premiers principes. Les améliorations que nous proposons permettent d'étudier par QMC des systèmes de plus grosse taille voire périodiques, avec l'ambition de faire du QMC une alternative valable à la théorie de la fonctionnelle de la densité (DFT). Tous les résultats ont été obtenus par le logiciel TurboRVB. D'abord, nous présentons une implémentation du QMC basée sur la fonction d'onde Jastrow-Geminale qui combine une grande flexibilité avec un traitement précis des corrélations électroniques. On a appliqué une technique originale de plongement pour réduire la taille de la base atomique à la molécule d'eau ainsi qu'à un modèle simplifié du transfert de protons (TP) dans l'eau. Nos résultats ouvrent la voie à l'étude des phénomènes microscopiques tels que le TP directement par QMC. Ensuite, on a amélioré notre méthode afin de simuler les solides cristallins. Grâce à une nouvelle procédure pour choisir de manière appropriée les conditions aux limites, nous avons pu réduire les erreurs de taille finie qui affectent les simulations QMC des solides. Sur la base des techniques développées, nous étudions enfin le supraconducteur FeSe. Le QMC fournit le meilleur résultat concernant sa structure cristalline; via une étude systématique du paysage énergétique à différentes configurations magnétiques, nous montrons un lien fort entre la structure, le magnétisme et les mouvements de charge dans ce matériau, prélude à une compréhension quantitative de la supraconductivité à haute température des premiers principes.
Le modèle en couches constitue aujourd'hui un cadre théorique de référence pour appréhender les propriétés des noyaux à basse énergie. Son applicabilité demeure toutefois limitée par une croissance rédhibitoire de la dimension de l'espace des états aussi bien avec le nombre de couches de valence qu'avec le nombre de nucléons. Les méthodes Monte-Carlo quantiques (QMC) permettent a priori de contourner une telle difficulté en offrant une alternative à la diagonalisation du hamiltonien. Elles reposent sur une reformulation stochastique de l'équation de Schrödinger qui ramène le problème à N-corps à un ensemble de problèmes à un corps, numériquement solubles, et décrivant des particules indépendantes évoluant chacune dans un champ extérieur fluctuant. L'originalité de l'échantillonnage QMC proposé dans ce mémoire réside dans l'utilisation d'une approche variationnelle, avec restauration des symétries avant variation, pour guider le mouvement brownien et pour le contraindre afin de contrôler le problème de phase inhérent aux schémas QMC pour des fermions en interaction. Dans les couches sd et fp et avec les interactions résiduelles réalistes, nous avons ainsi pu obtenir une spectroscopie " yrast " en excellent accord avec les résultats issus de la diagonalisation du hamiltonien. En outre, une ouverture vers les systèmes d'électrons fortement corrélés est présentée au travers de nouveaux schémas QMC récemment suggérés pour le modèle de Hubbard en géométrie bidimensionnelle. Contrairement aux échantillonnages traditionnels, ils garantissent des trajectoires à poids positifs quel que soit le régime considéré. Nous avons prouvé que ces méthodes sont en réalité reliées à l'approche stochastique mise en oeuvre pour le modèle en couches. L'origine des erreurs systématiques qu'exhibent ces schémas, pourtant exempts de problème de signe avec le hamiltonien de Hubbard, est par ailleurs élucidée.
Développement et implémentation parallèle de méthodes d'interaction de configurations sélectionnées Cette thèse, ayant pour thème les algorithmes de la chimie quantique, s'inscrit dans le cade du changement de paradigme observé depuis une douzaines d'années, dans lequel les méthodes de calcul séquentielles se doivent d'être progressivement remplacées par des méthodes parallèles. En effet, l'augmentation de la fréquences des processeurs se heurtant à des barrières physiques difficilement franchissables, l'augmentation de la puissance de calcul se fait par l'augmentation du nombre d'unités de calcul. Toutefois, là où une augmentation de la fréquence conduisait mécaniquement à une exécution plus rapide d'un code, l'augmentation du nombre de cœurs peut se heurter à des barrières algorithmiques, qui peuvent nécessiter une adaptation ou un changement d'algorithme. Parmi les méthodes développées afin de contourner ce problème, on trouve en particulier celles de type Monte-Carlo (stochastiques), qui sont intrinsèquement "embarrassingly parallel", c'est à dire qu'elles sont par construction constituées d'une multitudes de tâches indépendantes, et de ce fait particulièrement adaptées aux architectures massivement parallèles. Elles ont également l'avantage, dans de nombreux cas, d'être capables de produire un résultat approché pour une fraction du coût calculatoire de l'équivalent déterministe exacte. Lors de cette thèse, des implémentations massivement parallèles de certains algorithmes déterministes de chimie quantique ont été réalisées. Il s'agit des algorithmes suivants : CIPSI, diagonalisation de Davidson, calcul de la perturbation au second ordre, shifted-Bk, et Coupled Cluster Multi Références. Pour certains, une composante stochastique a été introduite en vue d'améliorer leur efficacité. Toutes ces méthodes ont été implémentées sur un modèle de tâches distribuées en TCP, où un processus central distribue des tâches par le réseau et collecte les résultats. En d'autres termes, des nœuds esclaves peuvent être ajoutés au cours du calcul depuis n'importe quelle machine accessible depuis internet. L'efficacité parallèle des algorithmes implémentés dans cette thèse a été étudiée, et le programme a pu donner lieu à de nombreuses applications, notamment pour permettre d'obtenir des énergies de références pour des systèmes moléculaires difficiles.