Invité par Daniel Bonamy
Cette présentation aborde une étude expérimentale du comportement des ordinateurs quantiques dits « analogiques » tels que ceux développés actuellement par la compagnie canadienne D-Wave. Nous étudions le comportement de ces machines lorsqu’elles sont confrontées à une classe de problèmes combinatoires au comportement pathologique appelé « maximum matching » spécifiquement conçus pour être (exponentiellement) difficiles à résoudre par recuit simulé. Nous avons étudié les résultats de calcul d’un processeur D-Wave «Washington» 2X avec 1098 qubits fonctionnels et nous avons observé qu’à part pour les cas les plus simples, ce processeur ne parvient pas de façon statistiquement significative à obtenir la solution optimale. Nos résultats suggèrent ainsi que le recuit quantique, au moins tel qu’il est mis en œuvre sur cette machine, tombe dans les mêmes pièges que ce ceux qui empêchent le recuit simulé de bien fonctionner sur cette classe de problèmes. Cela fournit une preuve supplémentaire qu’il existe des problèmes dont la difficulté de résolution est connue comme polynomiale mais que ce type de machines ne peuvent pas résoudre efficacement.
Solving pathological combinatorial problems by quantum annealing
This presentation experimentally investigates the behavior of analog quantum computers such as commercialized by D-Wave when confronted to instances of the maximum cardinality matching problem specifically designed to be hard to solve by means of simulated annealing. We benchmark a D-Wave « Washington » (2X) with 1098 operational qubits on various sizes of such instances and observe that for all but the most trivially small ones of these it fails to obtain an optimal solution. Thus, our results suggest that quantum annealing, at least as implemented in a D-Wave machine, falls in the same pitfalls as simulated annealing and therefore provides additional evidence that there exist polynomial-time problems that such a machine cannot solve efficiently to optimality.
CEA-Saclay, LIST