Le présent manuscrit démontre que l'inégalité P <> NP trouve une résolution empirique et formelle rigoureuse dans le domaine des sciences physiques appliquées et de l'algèbre fondamentale. Alors que les équations différentielles linéaires continues offrent l'illusion d'une complexité polynomiale (classe P), la modélisation discrète exacte de l'espace-temps révèle une explosion combinatoire inhérente à la nature physique de l'Univers. En appliquant le Calcul Extérieur Discret (DEC) à l'opérateur de Hodge sur un graphe 4D, et en étudiant sa complétude par la dualité de Langlands et les groupes de Galois, nous prouvons qu'une machine séquentielle est physiquement incapable d'explorer l'arbre exponentiel des solutions. Pour contourner ce mur algorithmique, nous introduisons une architecture de confinement cybernétique basée sur la théorie du contrôle : une projection DEC qui alimente un réseau de neurones morphologique en temps réel, ouvrant des applications immédiates en ingénierie multiphysique et en virologie quantique.
Le présent manuscrit démontre que l'inégalité P <> NP trouve une résolution empirique et formelle rigoureuse dans le domaine des sciences physiques appliquées et de l'algèbre fondamentale. Alors que les équations différentielles linéaires continues offrent l'illusion d'une complexité polynomiale (classe P), la modélisation discrète exacte de l'espace-temps révèle une explosion combinatoire inhérente à la nature physique de l'Univers. En appliquant le Calcul Extérieur Discret (DEC) à l'opérateur de Hodge sur un graphe 4D, et en étudiant sa complétude par la dualité de Langlands et les groupes de Galois, nous prouvons qu'une machine séquentielle est physiquement incapable d'explorer l'arbre exponentiel des solutions. Pour contourner ce mur algorithmique, nous introduisons une architecture de confinement cybernétique basée sur la théorie du contrôle : une projection DEC qui alimente un réseau de neurones morphologique en temps réel, ouvrant des applications immédiates en ingénierie multiphysique et en virologie quantique.
Depuis sa première définition par Hudson et Parthasarathy en 1984, l'intégration stochastique quantique offre un outil puissant pour la description de certaines évolutions en physique quantique. De nombreuses questions restent ouvertes cependant, en particulier dans le domaine de la représentabilité intégrale des opérateurs. La définition récente par Attal d'une méthode complètement explicite de l'approximation de l'espace de Fock usuel par un analogue discret a justifié l'intérêt d'une bonne connaissance du calcul stochastique quantique à temps discret. Nous définissons rigoureusement un tel calcul stochastique et obtenons une caractérisation des opérateurs admettant des représentations intégrales ou des représentations sous la forme de noyau de Maassen-Meyer, avec des expressions explicites dans les deux cas. Ces résultats nous permettent de préciser complètement le lien entre le calcul à temps discret et le calcul à temps continu et en particulier de montrer que la formule d'Itô quantique de composition des intégrales se déduit rigoureusement de relations de commutation, par exemple des relations de commutation entre matrices de Pauli. Nous appliquons ensuite nos résultats pour obtenir une caractérisation, dans l'espace de Fock usuel, des opérateurs qui sont représentables en intégrales stochastiques quantiques parmi les classes fondamentales que sont les opérateurs de seconde quantification et de seconde quantification différentielle. Enfin, nous utilisons ces techniques pour obtenir des résultats de convergence de solutions d'équations aux différences vers des équations différentielles stochastiques quantiques. Ces résultats nous permettent de montrer qu'une évolution en mécanique quantique obtenue par des interactions répétées est déterminée, à la limite, par une équation de Langevin quantique. Cette équation de Langevin décrit un couplage entre un ``petit système'' et un ``réservoir'', ce réservoir et les coefficients de l'équation se déduisant explicitement de l'interaction que l'on répète. Ces résultats permettent en particulier d'obtenir une description rigoureuse des mesures en continu et des approximations de ``coarse graining'' en optique 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.
Les ordinateurs quantiques exploitent les principes de la physique quantique pour encoder et traiter l'information, avec le potentiel de surpasser les capacités des ordinateurs classiques dans certains domaines. Cette thèse explore l'une des technologies majeures du calcul quantique : l'optique linéaire, où les calculs sont effectués à l'aide de photons traversant des circuits d'optique linéaire.Si ces circuits sont bien compris et simulables à petite échelle, leur véritable intérêt apparaît à grande échelle lorsqu'ils atteignent des régimes hors de portée du calcul classique. Cette thèse s'intéresse à cette transition sous deux aspects : sur le plan calculatoire d'une part, en développant des modèles plus efficaces pour repousser les limites des simulations classiques, et sur le plan formel d'autre part, en modélisant à un niveau plus abstrait les circuits optiques et leurs interactions.En simulation, l'un des défis majeurs est le calcul efficace des probabilités de sortie des circuits. Nous présentons dans cette thèse de nouveaux algorithmes pour calculer plusieurs de ces probabilités, où l'utilisation de la mémoire est optimisée pour significativement réduire le temps de calcul. Ce travail mène au développement de Perceval, une plateforme logicielle open-source dédiée au calcul quantique photonique.Sur le plan théorique, nous introduisons un cadre formel et diagrammatique qui capture pleinement la structure des processus d'optique linéaire. Plus précisément, nous utilisons le formalisme des langages graphiques pour modéliser ces circuits. Nous établissons une théorie équationnelle complète, démontrant que deux circuits équivalents d'optique linéaire peuvent toujours être réécrits localement avec notre ensemble d'équations.Enfin, nous montrons comment nos contributions ont des applications à la fois en physique et en informatique quantique théorique. En particulier, nous étendons notre théorie équationnelle complète des circuits optiques à une théorie équationnelle complète pour les circuits quantiques, résolvant ainsi un problème ouvert des dernières décennies.
Test de propriétés quantique et topologie algébrique Cette thèse explore la puissance et les limitations du calcul quantique en développant de nouveaux algorithmes classiques et quantiques, ainsi qu'en établissant des bornes inférieures. Au passage, nous revisitons des résultats existants et les étendons à de nouveaux contextes. Nous utilisons deux types de modèles algorithmiques : les algorithmes d'approximation et les tests de propriété. Les problèmes étudiés se répartissent en deux catégories principales. La première est motivée par l'analyse topologique des données que nous abordons sous l'angle de la topologie algébrique. Ici, l'entrée est un complexe simplicial, qui modélise des relations de haute dimension dans les données. L'objectif est d'estimer le nombre de « trous » de haute dimension - formellement, les nombres de Betti, ou les rangs des groupes d'homologie du complexe. Un algorithme quantique efficace était déjà connu pour estimer de manière additive les nombres de Betti normalisés en haute dimension. Nous complétons ce résultat en fournissant une solution classique : un algorithme probabiliste de Monte Carlo à intégrale de chemin. Alors que l'algorithme quantique est efficace lorsque la précision souhaitée et l'écart spectral du laplacien combinatoire sont inversement polynomiaux, notre algorithme probabiliste est efficace dans un régime de paramètres plus restreint - en particulier, lorsque la précision et l'écart spectral sont constants. Pour le cas particulier des complexes de cliques, nous proposons une extension de ce régime. Dans les tests (probabilistes) de propriétés, il suffit que l'algorithme distingue avec une forte probabilité les entrées qui satisfont une certaine propriété de celles qui sont « éloignées » (selon une certaine distance et un paramètre) de toute entrée qui la satisfait. Nous étudions également un problème de test de propriété en analyse topologique de données : déterminer si un complexe de cliques a un nombre de Betti élevé (sur le corps fini à deux éléments), ou s'il est éloigné de tout tel complexe. Nous montrons qu'un nombre constant de requêtes suffit à résoudre ce problème pour les complexes de cliques si la dimension et le paramètre de proximité sont constants. La seconde classe de problèmes est liée au problème des k-collisions, où le but est de détecter si une chaîne de caractères contient k-uplets de caractères identiques. Nous formalisons cela comme un problème de test de propriété : distinguer les entrées sans k-collisions de celles qui en sont éloignées. Alors que la complexité classique de ce problème est établie, le cas quantique restait ouvert, avec seulement des bornes inférieures et supérieures partielles connues dans ce cadre. Nous généralisons un algorithme quantique connu pour le problème des k-collisions à un problème de test de la propriété de non-présence de sous-graphes dans le modèle orienté à degré borné. Nous prouvons ensuite une borne inférieure en utilisant la méthode polynomiale duale, étendant des résultats antérieurs à un cadre plus général. Enfin, nous présentons quelques problèmes de test de propriétés de graphes, parmi lesquels la version test de la 3-colorabilité, et montrons qu'ils ont une complexité de requête quantique asymptotiquement maximale dans le modèle à degré borné.
Le développement de machines quantiques de tailles modestes accessibles en ligne permet aujourd'hui de réaliser des expériences sur des calculateurs à distance. L'avantage de l'informatique quantique repose sur des phénomènes strictement non classiques, tels que la superposition et l'intrication, qui sont des ressources maintenant bien connues. Le phénomène non-classique de la contextualité est peut-être moins bien établi bien qu'il ouvre aussi des perspectives très intéressntes à travers de nombreuses applications telles que la cryptographie quantique, les codes d'accès aléatoires, les codes correcteurs d'erreurs et l'avantage du coût de la mémoire pour la simulation des mesures quantiques. L'objectif de cette thèse est triple : développer de nouveaux tests résistants au bruit pour démontrer la contextualité avec des ordinateurs quantiques bruités d'échelle intermédiaire ; concevoir des algorithmes quantiques pour calculer les limites classiques de ces tests, avec une meilleure complexité par rapport aux algorithmes existants ; interpreter les invariants algébriques, utilisés pour distinguer les classes d'intrication, en termes d'observables à base d'opérateurs de Pauli. À ces fins, l'utilisation de configurations géométriques telles que les espaces polaires symplectiques et leurs sous-géométries est largement exploitée, permettant d'établir un lien solide entre le domaine, relativement ancien des géométries finies, et les concepts plus récents de la théorie de l'information quantique. Pour le premier objectif, nous utilisons l'apport de la géométrie pour fournir des tests de contextualité qui violent largement les limites classiques sur tous les ordinateurs quantiques IBM. Ces tests démontrent empiriquement l'absence de modèles à variables cachées non contextuelles décrivant le système sous-jacent. C'est un résultat d'intérêt ontologique. Plus précisément, il s'agit de la première violation connue du jeu de pseudotélépathie de Mermin sur de telles machines, et des plus grandes violations du test de Rio Negro. Concernant le deuxième objectif, nous nous appuyons sur les symétries de nos géométries pour construire un algorithme quantique basé sur l'algorithme de recherche de Grover. Cet algorithme identifie une affectation optimale de variables cachées classiques avec une complexité comparable à l'algorithme de Grover. Un tel avantage algorithmique est intéressant dans une grande famille de problèmes, connus sous le nom de Max Lin 2, où plusieurs contraintes sur un ensemble de données ne peuvent pas être satisfaites simultanément. Ainsi, l'étude de la contextualité - qui peut être vue comme une limitation de la satisfaction logique pour décrire les systèmes physiques - peut apporter de nouvelles perspectives à des problèmes où la satisfaction d'instruction logique simultanée n'est pas viable. Enfin, pour le troisième objectif, nous proposons de nombreuses connexions entre les géométries finies et les invariants algébriques, en commençant par des liens entre les quadrangles généralisés et les invariants cubiques de Cartan, puis en montrant comment les géométries maximalement mixtes permettent de reconstruire les polynômes de Mermin, et finalement en décrivant les sous-ensembles minimaux d'opérateurs de Pauli qui permettent de calculer les hyperdéterminants. On peut ainsi, grâce à ces invariants, identifier la classe d'intrication de systèmes de qubits N=2,3,4 par des mesures sans avoir besoin d'une tomographie complète du système. En résumé dans cette thèse, nous abordons une grande variété de questions à l'intersection de la géométrie finie et de l'informatique quantique - de la conception de tests de contextualité à l'étude de la non-localité à travers des invariants algébriques en passant par le calcul quantique de bornes classiques. Les idées proposées dans ce travail pourront être utiles à la fois pour l'étude des fondements de la mécanique quantique et pour son application à l'informatique quantique.
Dynamiques quantiques sur réseaux Le domaine de l’informatique quantique a connu ces dernières années un fort développement. Un nouveau phénomène a récemment été découvert sur atomes de Rydberg, le scarring, qui s’est révélé être un nouveau mécanisme de brisure d’ergodicité: certains états initiaux n’explorent pas l’entièreté de l’espace de Hilbert mais restent localisés. Ce type de mécanisme a un potentiel intérêt pour encoder de l’information dans des systèmes quantiques.Dans cette thèse, on étudie des dynamiques discrètes en espace temps, qui sont des modèles quantiques simples à plusieurs corps. Des exemples de ces dynamiques discrètes sont les marches quantiques et les automates cellulaires quantiques. Elles sont écrites en termes de portes quantiques, ce qui les rend adaptées aux plateformes expérimentales.Dans la première partie de la thèse, on s’est intéressé à ces dynamiques discrètes dans le but de simuler un système physique. Plus précisément, nous proposons un automate cellulaire quantique et montrons sa convergence vers une théorie quantique des champs, le modèle de Schwinger en 1+1 dimensions.Dans la seconde partie de la thèse, nous investiguons ces dynamiques quantiques hors équilibre et étudions leurs propriétés de thermalisation sous le point de vue de l’information quantique.Nous proposons une généralisation de la marche quantique telle qu’elle interagit avec des spins situés sur les liens d’un réseau, et nous étudions les propriétés de propagation de l’aimantation et de l’intrication.Nous étudions ensuite un automate cellulaire quantique et découvrons que parmi les états chaotiques générés par la dynamique une hiérarchie peut émerger.