Études algorithmiques des configurations quantiques contextuelles La thèse contribue à l'étude de la contextualité quantique en utilisant des approches algébriques et géométriques qui facilitent l'analyse de ces configurations et mettent en évidence les distinctions fondamentales entre les configurations classiques et les configurations quantiques. Ce travail se concentre sur la génération de configurations d'observables quantiques, l'analyse de leurs propriétés contextuelles et développe des méthodes efficaces pour construire et évaluer des configurations quantiques afin de déterminer si elles présentent des propriétés contextuelles. L'objectif de cette approche algorithmique est de s'aider de la puissance de calcul pour explorer les structures géométriques riches liées à la contextualité quantique, puis d'en dégager des propriétés qui permettent de mieux comprendre et d'établir de meilleurs cadres théoriques pour comprendre et quantifier ce phénomène.
Études algorithmiques des configurations quantiques contextuelles La thèse contribue à l'étude de la contextualité quantique en utilisant des approches algébriques et géométriques qui facilitent l'analyse de ces configurations et mettent en évidence les distinctions fondamentales entre les configurations classiques et les configurations quantiques. Ce travail se concentre sur la génération de configurations d'observables quantiques, l'analyse de leurs propriétés contextuelles et développe des méthodes efficaces pour construire et évaluer des configurations quantiques afin de déterminer si elles présentent des propriétés contextuelles. L'objectif de cette approche algorithmique est de s'aider de la puissance de calcul pour explorer les structures géométriques riches liées à la contextualité quantique, puis d'en dégager des propriétés qui permettent de mieux comprendre et d'établir de meilleurs cadres théoriques pour comprendre et quantifier ce phénomène.
Etudes calculatoires de l'intrication et de la contextualité quantiques dans la perspective de leur vérification formelle Bien que les ordinateurs quantiques actuels se limitent à l'utilisation de quelques qubits, les fondations de la programmation quantique se sont développées au cours des 20 dernières années. Ces fondations ont été théorisées dès les années 80 mais la complexité de leur mise en œuvre a rendu ces pistes inaccessibles jusqu'à très récemment. Dans ce contexte, l'objectif de cette thèse est de contribuer à l'adaptation des méthodes de spécification formelle et de vérification déductive des programmes classiques aux programmes quantiques. Je présente donc mes contributions à l'étude des propriétés quantiques dans le but de les formaliser. J'étudie en particulier l'intrication quantique et la contextualité quantique. Ces propriétés permettent de classifier les états et les protocoles quantiques, et en particulier de les différencier des états et protocoles classiques. Mon étude de l'intrication est fondée plus spécifiquement sur l'évolution de l'intrication au cours de deux algorithmes quantiques : l'algorithme de Grover et la transformée de Fourier quantique. Pour quantifier l'intrication le long de ces algorithmes, j'utilise des polynômes de Mermin, qui ont l'avantage de pouvoir être implémentables dans des ordinateurs quantiques réels. Mon étude de la contextualité s'appuie, elle, sur des géométries finies représentant des expériences, qui sont dites contextuelles quand aucune théorie classique non-contextuelle ne peut en prédire les résultats. Ces géométries sont associées à des espaces polaires symplectiques binaires dont nous explorons la structure, avec comme objectif d'utiliser cette structure pour obtenir des intuitions sur les protocoles quantiques en utilisant la contextualité. L'étude de ces propriétés a conduit à des conjectures intéressantes que nous avons commencé à formaliser dans des environnements de preuve tels que Coq et Why3, mais qui sont laissées en perspective car ces travaux n'ont pas encore abouti.
Contextualité quantique, géométries finies & informatique quantique 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.
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.
L’intrication quantique est un des phénomènes les plus intéressants et intriguant en Mécanique Quantique, et de surcroît en Théorie de l’Information Quantique. Ressource fondamentale pour le calcul quantique, son rôle dans l’efficacité et la fiabilité des protocoles ou algorithmes quantiques n’est toujours pas totalement compris. Dans cette thèse, nous étudions l’intrication quantique des états multipartites, et notamment la nature de sa présence dans les algorithmes quantiques. L’étude de l’intrication se fait d’un point de vue théorique, en utilisant principalement des outils issus de la géométrie algébrique.Nous nous intéressons alors aux algorithmes de Grover et de Shor et déterminons quelles sont les classes d’intrication présentes (ou non) dans ces algorithmes, et ceci constitue donc une étude qualitative de l’intrication. De plus, nous mesurerons l’intrication quantitativement, à l’aide de mesures algébriques et géométriques, et étudions son évolution tout au long des différentes étapes de ces algorithmes. Nous proposons également des interprétations géométriques originales de ces résultats numériques.D’autre part, nous cherchons également à développer et exploiter de nouveaux outils pour mesurer, caractériser et classifier l’intrication quantique. Ceci se fait dans un premier temps d’un point de vue mathématique en étudiant les singularités des hypersurfaces liées aux systèmes quantiques pour caractériser différentes classes d’intrication. Dans un second temps, nous proposons des candidats pour les états maximalement intriqués, notamment pour les états symétriques et fermioniques, en utilisant des polynômes invariants et une mesure géométrique de l’intrication pour quantifier l’intrication. Enfin, nous avons également adopté une approche de type Machine Learning, notamment en entraînant des réseaux de neurones artificiels de manière supervisée, afin de reconnaitre certaines variétés algébriques modélisant certains types d’intrication précis.
L’intrication quantique est un des phénomènes les plus intéressants et intriguant en Mécanique Quantique, et de surcroît en Théorie de l’Information Quantique. Ressource fondamentale pour le calcul quantique, son rôle dans l’efficacité et la fiabilité des protocoles ou algorithmes quantiques n’est toujours pas totalement compris. Dans cette thèse, nous étudions l’intrication quantique des états multipartites, et notamment la nature de sa présence dans les algorithmes quantiques. L’étude de l’intrication se fait d’un point de vue théorique, en utilisant principalement des outils issus de la géométrie algébrique.Nous nous intéressons alors aux algorithmes de Grover et de Shor et déterminons quelles sont les classes d’intrication présentes (ou non) dans ces algorithmes, et ceci constitue donc une étude qualitative de l’intrication. De plus, nous mesurerons l’intrication quantitativement, à l’aide de mesures algébriques et géométriques, et étudions son évolution tout au long des différentes étapes de ces algorithmes. Nous proposons également des interprétations géométriques originales de ces résultats numériques.D’autre part, nous cherchons également à développer et exploiter de nouveaux outils pour mesurer, caractériser et classifier l’intrication quantique. Ceci se fait dans un premier temps d’un point de vue mathématique en étudiant les singularités des hypersurfaces liées aux systèmes quantiques pour caractériser différentes classes d’intrication. Dans un second temps, nous proposons des candidats pour les états maximalement intriqués, notamment pour les états symétriques et fermioniques, en utilisant des polynômes invariants et une mesure géométrique de l’intrication pour quantifier l’intrication. Enfin, nous avons également adopté une approche de type Machine Learning, notamment en entraînant des réseaux de neurones artificiels de manière supervisée, afin de reconnaitre certaines variétés algébriques modélisant certains types d’intrication précis.
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é.