Thèse CEA sur Transformations polynomiales pour les calculateurs quantiques analogiques

Ces dernières années, sont apparues des machines quantiques dites analogiques, dont les calculateurs actuellement commercialisés par la société canadienne D-Wave sont les premiers représentants, fonctionnant selon un principe de recuit à accélération quantique. De manière abstraite, on peut voir un tel calculateur comme une machine spécialisée dans la résolution d'un problème d'optimisation NP-difficile (de type verre de spin) à l'aide d'un algorithme analogue à un recuit simulé mais bénéficiant d'un facteur d'accélération quantique (dont la détermination exacte n'est pas une question close). Si la théorie sous-jacente au recuit quantique est assez bien comprise par les physiciens, le fait que cette machine l'implémente correctement fait encore l'objet de controverse dans cette communauté. Néanmoins, cette machine à l'avantage d'exister à une échelle non triviale (entre 512 et 1000 bits d'état interne) et le chemin technologique en vue de son passage à l'échelle est beaucoup moins floue que celui de ses cousins numériques. Aujourd'hui, les physiciens estiment qu'une machine quantique analogique possédant un état interne entre 6000 et 10000 bits seraient compétitive avec les meilleurs calculateurs classiques actuels pour résoudre des problèmes d'optimisation. Dans ce contexte, l'objet de la présente thèse est d'investiguer des chemins de transformations polynomiales permettant aussi efficacement que possible de ramener des problèmes de NP (pas forcément prouvés NP-complets et à déterminer pendant la thèse) vers le problème de référence de la machine. Ainsi, l’objet de cette thèse est de développer une meilleure compréhension des performances théoriques de ces machines et éventuellement d’aller jusqu’à faire un peu d’expérimentation si un accès à une machine D-Wave est possible (via une institution possédant une telle machine). En fonction du profil du candidat, le sujet sera adapté plus vers les aspects physiques, en lien avec la théorie de la complexité ou encore ciblant certains domaines d’application (recherche opérationnelle, cryptanalyse notamment).