In this talk, I will introduce the concept of quantum algorithms, which aims to leverage the specific nature of quantum information manipulated by quantum computers to solve combinatorial problem intractable for classical computers. Then, I will present two new quantum algorithms to solve combinatorial optimisation problems, the first one to solve optimisation problems over the symmetric group of permutations, and the other one to solve polynomial binary optimisation problems, which are in bijection with cooperative games through the Möbius inverse transform. I will finally present applications of these algorithms to well-known combinatorial optimisation problems: Max-Cut, i.e., the identification of a two-block partition of the set of nodes of a graph such that the sum of the weights of the edges connecting these two blocks is maximised, the k-densest subgraph problem, for which we are looking to the densest subgraph (with the most edges, or the largest sum of their weights) of cardinality k of a given graph, as well as the 3-SAT problems, or the more general Quadratic Assignment Problem (QAP). 

Retour page d'accueil du séminaire