Academic literature on the topic 'Algorithmes quantiques'

Le développement des technologies quantiques est aujourd’hui l’objet d’importants efforts de recherche, mais les résultats seront-ils à la hauteur des attentes ? L’ordinateur quantique peut résoudre certains problèmes difficiles, qui demandent à l’ordinateur classique un temps de calcul trop important, et peut également attaquer les schémas actuels de cryptage. Cependant, la réalisation d’un ordinateur quantique suffisamment puissant pour résoudre des problèmes pratiques demeure un véritable défi technologique. Il existe plusieurs technologies d’implémentation hardware , chacune avec ses avantages et ses inconvénients. Comme ils sont plus faciles à réaliser, la recherche se dirige également vers la mise au point d’ordinateurs quantiques analogiques et de simulateurs quantiques. Parallèlement, ces travaux ont pour conséquence la conception de capteurs extrêmement sensibles, qui ont de nombreuses applications dans l’industrie de la prospection géologique, dans l’imagerie médicale, dans les technologies militaires et la mise au point de nouvelles méthodes de cryptage immunes contre l’attaque par un algorithme quantique.

International audience A driving question in (quantum) cohomology of flag varieties is to find non-recursive, positive combinatorial formulas for expressing the quantum product in a particularly nice basis, called the Schubert basis. Bertram, Ciocan-Fontanine and Fulton provide a way to compute quantum products of Schubert classes in the Grassmannian of $k$-planes in complex $n$-space by doing classical multiplication and then applying a combinatorial rimhook rule which yields the quantum parameter. In this paper, we provide a generalization of this rim hook rule to the setting in which there is also an action of the complex torus. Combining this result with Knutson and Tao's puzzle rule provides an effective algorithm for computing the equivariant quantum Littlewood-Richardson coefficients. Interestingly, this rule requires a specialization of torus weights that is tantalizingly similar to maps in affine Schubert calculus. Une question importante dans la cohomologie quantique des variétés de drapeaux est de trouver des formules positives non récursives pour exprimer le produit quantique dans une base particulièrement bonne, appelée la base de Schubert. Bertram, Ciocan-Fontanine et Fulton donnent une façon de calculer les produits quantiques de classes de Schubert dans la Grassmannienne de $k$-plans dans l’espace complexe de dimension $n$ en faisant la multiplication classique et appliquant une règle combinatoire “rimhook” qui donne le paramètre quantique. Dans cet article, nous donnons une généralisation de ce règle rimhook au contexte où il y a aussi une action du tore complexe. Combiné avec la règle “puzzle” de Knutson et Tao, cela donne une algorithme effective pour calculer les coefficients équivariants de Littlewood-Richard. Il est intéressant d'observer que cette règle demande une spécialisation des poids du tore qui est similaire d’une manière tentante aux applications dans le calcul de Schubert affiné.

Nous avons étudié les algorithmes quantiques dans le but de calculer le permanent d'une matrice avec une machine quantique. Après avoir construit quelques algorithmes, nous nous sommes interessés aux équivalents quantiques des marches aléatoires. Ces marches peuvent être à la base de nouveaux algorithmes quantiques. Nous avons commencé par généraliser le modèle existant et classifier les marches sur des graphes de Cayley de groupes simples. Nous avons étudié des marches sur l'hypercube et le réseau simple à une et deux directions. Pour ces graphes nous avons calculé analytiquement la fonction d'onde et exploré numériquement le temps d'arrivée et la variance. Nous avons de plus élargi deux théorèmes existants concernant l'existence des marches scalaires et la limite faible. Ces résultats nous permettent d'envisager de compléter la classification des marches pour des graphes plus complexes dans le but d'obtenir des informations structurales sur les sous-algorithmes quantiques possibles
We have studied quantum algorithms with the purpose of calculating a matrix permanent with a quantum computer. After constructing some algorithms, we started to study the quantum equivalent of a random walk. These walks have been introduced hoping to build new quantum algorithms from them. We started by generalizing the existing model of quantum walk and started a classification of the walks defined on Cayley graphs of the simplest groups. We studied then quantum walks over the hypercube and simple lattices in one and two dimensions and we obtained an analytical expression for the wave function, in order to explore numerically quantities such as the hitting time and the variance. Finally, we also extended two existing theorems about the existence of quantum scalar walks and about the weak limit of the walk. These results enable us to consider the classification of more complex graphs with an aim of obtaining structural information on the quantum sub-algorithms that can be constructed

Nous avons étudié les algorithmes quantiques dans le but de calculer le permanent d'une matrice avec une machine quantique. Après avoir construit quelques algorithmes, nous nous sommes interessés aux équivalents quantiques des marches aléatoires. Ces marches peuvent être à la base de nouveaux algorithmes quantiques. Nous avons commencé par généraliser le modèle existant et classifier les marches sur des graphes de Cayley de groupes simples. Nous avons étudié des marches sur l'hypercube et le réseau simple à une et deux directions. Pour ces graphes nous avons calculé analytiquement la fonction d'onde et exploré numériquement le temps d'arrivée et la variance. Nous avons de plus élargi deux théorèmes existants concernant l'existence des marches scalaires et la limite faible. Ces résultats nous permettent d'envisager de compléter la classification des marches pour des graphes plus complexes dans le but d'obtenir des informations structurales sur les sous-algorithmes quantiques possibles.

Dans cette thèse, nous commençons par donner avec précision une définition formelle des groupes boîtes noires, et nous rappelons les principaux algorithmes existant dans ce cadre. Dans un deuxième temps, nous proposons une définition nouvelle d’un groupe boîte noire quantique. Nous formalisons, par ailleurs, précisément cette définition et donnons les principaux algorithmes quantiques connus dans ce cadre. Ensuite, nous donnons un certain nombre d’algorithmes de calcul de théorie algorithmique quantique des groupes dans les groupes résolubles, et dans certaines sous-classes particulières de ces groupes. Enfin, nous présentons un résultat original, démontré au cours de l’élaboration de cette thèse. Nous expliquons comment résoudre efficacement le problème du sous-groupe caché dans les groupes extraspéciaux et nilpotents de classe deux, en calcul quantique. Au passage, nous donnons un certain nombre de réductions du problème du sous-groupe caché, valable dans un groupe nilpotent de classe supérieure. Le dernier chapitre, un peu à part dans cette thèse, explique comment résoudre efficacement un système d’équations quadratiques dans un corps fini, résultat nécessaire pour résoudre le problème du sous-groupe caché dans les groupes nilpotents de classe 2
We start off this Ph. D. Thesis with giving the definition of a black-box group and reminding some algorithm associated with this group representation. Then, we put forward a new definition of a quantum black-box group. We explain precisely this new approach and we enumerate the main algorithms associated to this notion. After that, we give some algorithm of quantum computational group theory in solvable groups and in some subclasses of these solvable groups such as nilpotent groups, p-groups or extraspecial groups. Finally, we present a new result that was proved during this thesis. We show that we can solve efficiently, with a quantum computer, the hidden subgroup problem in extraspecial and nilpotent group of class 2. In addition, we give some reduction of the Hidden subgroup problem in nilpotent groups of higher classes. The last chapter of this thesis shows how to solve some system of quadratic equations over a finite field. This result is needed to solve the Hidden subgroup problem in nilpotent groups of class 2

L'informatique quantique est un domaine en plein essor qui a suscité un intérêt considérable au cours des deux dernières décennies en raison de sa promesse de révolutionner plusieurs domaines des affaires et de la science. Il s'agit d'une nouvelle façon d'effectuer des calculs en utilisant les propriétés fondamentales de la mécanique quantique telles que la superposition et l'intrication. L'optimisation, quant à elle, est un domaine omniprésent dans l'industrie et où de petites améliorations peuvent avoir un impact significatif. Cette thèse vise à résoudre des problèmes d'optimisation à l'aide d'algorithmes quantiques.Les problèmes d'optimisation NP-difficiles ne sont pas considérés comme pouvant être résolus exactement par des algorithmes généraux en temps polynomial. Les algorithmes quantiques variationnels (VQA en anglais) destinés à résoudre ces problèmes combinatoires ont récemment fait l'objet d'un grand intérêt. Ces algorithmes sont heuristiques et visent à obtenir une solution approximative. Cependant, le matériel en est encore à ses débuts et les ordinateurs quantiques bruyants à échelle intermédiaire (NISQ en anglais) actuels ne sont pas en mesure d'optimiser les problèmes d'intérêt industriel. De plus, le stockage des qubits et l'introduction de l'intrication nécessitent des conditions physiques extrêmes. Les algorithmes d'optimisation quantique contemporains, tels que le algorithme d'optimisation approximative quantique, Quantum Approximate Optimization Algorithm (QAOA) en anglais, posent un problème : leur échelle est linéaire en fonction de la taille du problème. Pour résoudre ce problème, nous présentons l'encodage LogQ, qui permet de concevoir des algorithmes variationnels quantiques dont l'échelle est logarithmique avec la taille du problème, ce qui ouvre la voie au traitement de problèmes d'optimisation d'une ampleur sans précédent sur des ordinateurs quantiques basés sur des portes. Nous montrons comment cet algorithme peut être appliqué à plusieurs problèmes d'optimisation combinatoire tels que Maximum Cut, Minimum Partition, Maximum Clique and Maximum Weighted Independent Set (MWIS). Ensuite, ces algorithmes sont testés sur un simulateur quantique avec des graphes de plus d'une centaine de nœuds et sur un véritable ordinateur quantique jusqu'à des graphes de taille 256. À notre connaissance, il s'agit des plus grands problèmes réalistes d'optimisation combinatoire jamais exécutés sur une machine NISQ, dépassant de près de dix fois la taille des problèmes résolus précédemment.Ensuite, nous appliquons le codage LogQ à deux cas d'utilisation pour de grandes entreprises telles que TotalEnergies. La conversion de la flotte est le processus de transition d'une flotte de véhicules vers des alternatives plus durables et plus respectueuses de l'environnement. Il est modélisé comme un schéma de génération de colonnes avec le problème MWIS comme sous-problème ou problème de travailleur. Nous utilisons la méthode LogQ pour résoudre le problème de travailleur MWIS et démontrons comment les solveurs quantiques et classiques peuvent être utilisés ensemble pour aborder un cas d'utilisation de taille industrielle. La segmentation de maillage fait référence au processus de division d'un maillage complexe (composé de sommets, d'arêtes et de faces) en parties ou régions significatives et sémantiquement cohérentes. La segmentation du maillage joue un rôle important dans la modélisation informatique, qui est largement utilisée dans les domaines clés des activités de TotalEnergies, tels que l'imagerie terrestre, la modélisation physique des réservoirs, etc. Nous définissons le problème comme un problème d'optimisation de graphe et utilisons l'encodage LogQ pour le résoudre
Quantum computing is a rapidly developing field that has seen a huge amount of interest in the last couple of decades due to its promise of revolutionizing several domains of business and science. It presents a new way of doing computations by making use of fundamental properties of quantum mechanics such as superposition and entanglement. Optimization, on the other hand, is a field that is omnipresent in the industry and where small improvements can have a significant impact. This thesis aims to tackle optimization problems using quantum algorithms.NP-hard optimization problems are not believed to be exactly solvable through general polynomial time algorithms. Variational quantum algorithms (VQAs) to address such combinatorial problems have been of great interest recently. Such algorithms are heuristic and aim to obtain an approximate solution. The hardware, however, is still in its infancy and the current Noisy Intermediate Scale Quantum (NISQ) computers are not able to optimize industrially relevant problems. Moreover, the storage of qubits and introduction of entanglement require extreme physical conditions.An issue with contemporary quantum optimization algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) is that they scale linearly with problem size. To tackle this issue, we present the LogQ encoding, using which we can design quantum variational algorithms that scale logarithmically with problem size - opening an avenue for treating optimization problems of unprecedented scale on gate-based quantum computers. We show how this algorithm can be applied to several combinatorial optimization problems such as Maximum Cut, Minimum Partition, Maximum Clique and Maximum Weighted Independent Set (MWIS). Subsequently, these algorithms are tested on a quantum simulator with graph sizes of over a hundred nodes and on a real quantum computer up to graph sizes of 256. To our knowledge, these constitute the largest realistic combinatorial optimization problems ever run on a NISQ device, overcoming previous problem sizes by almost tenfold.Next, we apply the LogQ encoding to two use-cases for large companies such as TotalEnergies. Fleet conversion is the process of transitioning a fleet of vehicles to more sustainable and environmentally friendly alternatives. It is modeled as a column generation scheme with the MWIS problem as the sub-problem or worker problem. We use the LogQ method to solve the MWIS Workers and demonstrate how quantum and classical solvers can be used together in a hybrid manner to approach an industrial-sized use-case. Mesh segmentation refers to the process of dividing a complex mesh (composed of vertices, edges, and faces) into meaningful and semantically coherent parts or regions. Mesh segmentation plays an important part in computer modeling, which is extensively used in the core domains of TotalEnergies' activities such as Earth imaging, physical modeling for reservoirs, and others. We define the problem as a graph optimization problem and use the LogQ encoding to solve it

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
Quantum entanglement is one of the most interesting phenomenon in Quantum Mechanics, and especially in Quantum Information. It is a fundamental resource in Quantum Computing, and its role in the efficiency and accuracy of quantum algorithms or protocols is not yet fully understood. In this thesis, we study quantum entanglement of multipartite states, and more precisely the nature of entanglement involved in quantum algorithms. This study is theoretical, and uses tools mainly coming from algebraic geometry.We focus on Grover’s and Shor’s algorithms, and determine what entanglement classes are reached (or not) by these algorithms, and this is the qualitative part of our study. Moreover, we quantitatively measure entanglement, using geometric and algebraic measures, and study its evolution through the several steps of these algorithms. We also propose original geometrical interpretations of the numerical results.On another hand, we also develop and exploit new tools for measuring, characterizing and classifying quantum entanglement. First, from a mathematical point of view, we study singularities of hypersurfaces associated to quantum states in order to characterize several entanglement classes. Secondly, we propose new candidates for maximally entangled states, especially for symmetric and fermionic systems, using polynomial invariants and geometric measure of entanglement. Finally, we use Machine Learning, more precisely the supervised approach using neural networks, to learn how to recognize algebraic varieties directly related with some entanglement classes

Cette thèse explore la mesure de l'intrication dans certains états hypergraphiques, dans certains algorithmes quantiques tels que les algorithmes quantiques d'estimation de phase et de comptage, ainsi que dans les circuits d'agents réactifs, à l'aide de la mesure géométrique de l'intrication, d'outils issus des polynômes de Mermin et des matrices de coefficients. L'intrication est un concept présent en physique quantique qui n'a pas d'équivalent connu à ce jour en physique classique.Le coeur de notre recherche repose sur la mise en place de dispositifs de détection et de mesure de l'intrication afin d'étudier des états quantiques du point de vue de l'intrication.Dans cette optique, des calculs sont d'abord effectués numériquement puis sur simulateur et ordinateur quantiques. Effectivement, trois des outils exploités sont implémentables sur machine quantique, ce qui permet de comparer les résultats théoriques et "réels"
This thesis explores the measurement of entanglement in certain hypergraph states, in certain quantum algorithms like the Quantum Phase estimation and Counting algorithms as well as in reactive agent circuits, using the geometric measurement of entanglement, tools from Mermin polynomials and coefficient matrices. Entanglement is a concept present in quantum physics that has no known equivalent to date in classical physics.The core of our research is based on the implementation of entanglement detection and measurement devices in order to study quantum states from the point of view of entanglement.With this in mind, calculations are first carried out numerically and then on a quantum simulator and computer. Indeed, three of the tools used can be implemented on a quantum machine, which allows us to compare theoretical and "real" results

Quel est le point commun entre les étoiles formant une galaxie, les gouttes d'eau s'écoulant dans une rivière, et les électrons d'une céramique superconductrice lévitant au-dessus d'un aimant ? Tous ces systèmes ne peuvent être décrits par le mouvement isolé d'une seule de leurs composantes. C'est l'ensemble des particules et de leurs interactions qui fait émerger leurs singulières propriétés : on parle du problème à N corps.Dans cette Thèse, nous nous intéressons aux propriétés des systèmes d'électrons fortement corrélés, dont la physique est gouvernée par les principes de la mécanique quantique. Les méthodes analytiques étant rapidement limitées, nous développons de nouvelles approches numériques afin de quantifier précisément les propriétés de matériaux dans lesquels les interactions entre particules deviennent importantes.Nous nous intéressons tout d'abord aux propriétés d'équilibre de la pérovskite Sr2IrO4, un matériau structurellementéquivalent au cuprate supraconducteur La2CuO4. Nous mettons en évidence l'existence d'un pseudogapet décrivons la structure électronique de ce matériau en fonction du dopage.Nous développons ensuite des extensions aux algorithmes de Monte Carlo déterminantaux pour l'étude de quantités dynamiquescomme l'énergie propre, et nous montrons qu'il est possible de regrouper un nombre factoriel de diagrammes en une somme de déterminants, réduisantainsi fortement le problème de signe fermionique.Dans un deuxième temps, nous décrivons les systèmes fortement corrélés hors d'équilibre.Nous commençons par revisiter le Monte Carlo diagrammatique en temps réel dans une nouvelle base qui permet aux diagrammes du vide de s'annulerdirectement. Au cours d'un échantillonnage statistique, ceci permetd'atteindre la limite de long temps nécessaire à l'étude des états stationnaires des systèmes hors d'équilibre.Pour terminer, nous étudions la transition métal-isolant induite par un champ électrique de Ca2RuO4, qui coexiste avec une transition structurelle.Un algorithme basé sur l'approximation sans croisement nous permettent de calculer le courant en fonction du champ crystallin dans ce matériauet de comparer nos résultats aux données expérimentales
What do stars in a galaxy, drops in a river, and electrons in a superconducting cuprate levitating above a magnet all have in common? All of these systems cannot be described by the isolated motion of one of their parts. These singular properties emerge from particles and their interactions as a whole: we talk about the emph{many-body problem}.In this Thesis, we focus on properties of strongly-correlated systems, that obey quantum mechanics. Analytical methods being rapidly limited in their understanding of these materials, we develop novel numerical techniques to precisely quantify their properties when interactions between particles become strong.First, we focus on the equilibrium properties of the layered perovskite Sr2IrO4, a compound isostructural to the superconducting cuprate La2CuO4,where we prove the existence of a pseudogap and describe the electronic structure of this material upon doping.Then, in order to address the thermodynamic limit of lattice problems, we develop extensions of determinant Monte Carlo algorithms to compute dynamical quantities such as the self-energy. We show how a factorial number of diagrams can be regrouped in a sum of determinants, hence drastically reducing the fermionic sign problem.In the second part, we turn to the description of nonequilibrium phenomena in correlated systems.We start by revisiting the real-time diagrammatic Monte Carlo recent advances in a new basis where all vacuum diagrams directly vanish.In an importance sampling procedure,such an algorithm can directly addressthe long-time limit needed in the study of steady states in out-of-equilibrium systems.Finally, we study the insulator-to-metal transition induced by an electric field in Ca2RuO4, which coexists with a structural transition.An algorithm based on the non-crossing approximation allows us to compute the current as a function of crystal-field splitting in this material and to compare our results to experimental data

Soit q, un nombre complexe transcendant sur Q. Nous démontrons que les idéaux premiers H-invariants de l'algèbre des matrices quantiques Oq (Mm,p [C]) sont engendrés par des mineurs quantiques. Ce résultat fournit, lorsque q est transcendant sur Q, une réponse positive à une question de K. R. Goodearl et T. H. Lenagan. Nous construisons ensuite un algorithme calculant un système générateur explicite de mineurs quantiques pour chaque idéal premier H-invariant de Oq (Mm,p [C]). (Bien entendu, cet algorithme n'aboutit que pour des valeurs de m et p fixées). Dans le cas général, nous construisons (en explicitant, pour chacun d'eux, un système générateur de mineurs quantiques) de nouveaux exemples d'idéaux premiers H-invariants de Oq (Mm,p [C])
Let q be a complex number which is transcendental over Q. We prove that the H-invariant prime ideals in the algebra Oq (Mm,p [C]) of quantum matrices are generated by quantum minors. When q is transcendental over Q, this gives a positive answer to a conjecture of K. R. Goodearl and T. H. Lenagan. Next, we construct an algorithm which provides an explicit generating set of quantum minors for each H-invariant prime ideal in Oq (Mm,p [C]). (Of course, these generating sets can be computed with this algorithm only when m and p have fixed values). In the general case, we construct some new examples of H-invariant prime ideals in Oq (Mm,p [C]) (providing for each of them an explicit generating set of quantum minors)

Cette thèse utilise la théorie des bases cristallines De Kashiwara pour étudier des problèmes algorithmiques et combinatoires liés aux algèbres quantiques de type B, C et D. Nous obtenons tout d'abord, pour tout poids dominant lambda, un algorithme général de calcul de la base globale d'un Uq (sp2n) module de dimension finie et de plus haut poids lambda. Nous avons de plus une description explicite de la base canonique lorsque lambda est un poids dominant. Nous donnons ensuite une présentation de monoi͏̈des, analogues pour les types B, C et D, au monoi͏̈de plaxique de Lascoux et Schützenberger. Nous décrivons alors les algorithmes d'insertion correspondant à ces monoi͏̈des. Dans le cas du type C, nous démontrons que nos relations plaxiques sont compatibles avec l'algorithme de glissement de Sheats ce qui nous permet d'obtenir un Jeu de Taquin complet pour les types B et C. Finallement, nous obtenons une généralisation de la correspondance de Robinson-Schensted aux autres types classiques qui prend en compte les représentations spinorielles des cas orthogonaux.

L’intersection de la cryptographie non commutative et multivariée contient des études sur les applications cryptographiques des sous-mi-groupes et des sous-groupes des semi-groupes affines de Crémone définis sur l’anneau commutatif fini K avec l’unité. Nous considérerons des sous-mi-groupes spéciaux (plateformes) dans un semi-groupe de tous les endomorphismes de K[x1, x2, …, xn]. Les homomorphismes calculés efficacement entre ces plateformes peuvent être utilisés dans les protocoles d’échange de clés post-quantiques lorsque les correspondants élaborent une transformation commune de (K*)n. La sécurité de ces systèmes est basée sur un problème de complexité de décomposition d’un élément d’un semi-groupe en un produit de générateurs donnés. Ce chapitre prpopose trois protocoles de ce type (avec un groupe et avec deux semi-groupes comme plateformes) pour leur utilisation avec des systèmes de signature numérique multivariés. L’utilisation de protocoles nous permet de convertir les cartes publiques de ces systèmes en modes privés, c’est-à-dire qu’un correspondant utilise la carte de collision pour transférer en toute sécurité la règle multivariée sélectionnée à son partenaire.