Quantum algorithms for hypergraph bi-partitioning

Algorithmes quantiques pour le bi-partitionnement d'hypergraphes

Julien Rodriguez (1, 2, 3, 4, 5)

1 DSCIN (CEA, LIST) - Département Systèmes et Circuits Intégrés Numériques
2 TADAAM - Topology-Aware System-Scale Data Management for High-Performance Computing
3 LaBRI - Laboratoire Bordelais de Recherche en Informatique
4 LIST (CEA) - Laboratoire d'Intégration des Systèmes et des Technologies
5 LECA - Laboratoire Environnement de Conception & Architecture

The arrival of quantum machines may revolutionize many fields, in particular that of combinatorial algorithms. Indeed, these machines propose several optimization algorithms, such as QAOA for "Quantum Approximate Optimization Algorithm", VQE for "Variational Quantum Eigensolver" and the oracle-based search algorithm published by Lov Grover. These algorithms each bring a theoretical gain on the computation time for some combinatorial problems. However, to date there are several different technologies allowing the design of a quantum chip, none of which is dominant at the moment. In this work we are interested in machines called "gate machines" and "quantum annealing" machines. The executions for the gate machines are realized on IBM simulators and machines using the Qiskit library and the Ocean library of D-Wave for the quantum annealing machines. The objective is to propose different models with their associated quantum circuits for the hypergraph partitioning problem and to measure the complexity in space and in number of gates of the different optimization algorithms chosen.

L'arrivée des machines quantiques risque de révolutionner de nombreux domaines, en particulier celui des algorithmes combinatoires. En effet, ces machines proposent plusieurs algorithmes d'optimisation, tels que, QAOA pour "Quantum Approximate Optimization Algorithm", VQE pour "Variational Quantum Eigensolver" ainsi que l'algorithme de recherche à partir d'un oracle publié par Lov Grover. Ces algorithmes apportent chacun un gain théorique sur le temps de calcul pour certains problèmes combinatoires. Cependant, à ce jour il existe plusieurs technologies différentes permettant de concevoir une puce quantique dont aucune n'est pour l'instant dominante. Dans ce travail nous nous intéressons aux machines appelées "machines à portes" et aux machines dites à "recuit quantique". Les exécutions pour les machines à portes sont réalisées sur les simulateurs et les machines d'IBM à l'aide de la bibliothèque Qiskit et de la bibliothèque Ocean de D-Wave pour les machines de type recuit quantique. L'objectif est de proposer plusieurs modèles avec leurs circuits quantiques associés pour le problème de partitionnement d'hypergraphes et de mesurer la complexité en espace et en nombre de portes des différents algorithmes d'optimisation choisis.

Mots clés: recherche opérationnelle quantique; QAOA; Grover; partitionnement

Domaines: Recherche opérationnelle [math.OC]; Combinatoire [math.CO]

Julien Rodriguez. Algorithmes quantiques pour le bi-partitionnement d'hypergraphes. ROADEF 2022 - 23ème congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, INSA Lyon, Feb 2022, Lyon, France. ⟨hal-03595234⟩