Study of the performance of quantum annealing machines for solving combinatorial problems
Daniel Vert · theses.fr (ABES) · 2021
La principale contribution de cette thèse est d'étudier expérimentalement le comportement des ordinateurs quantiques analogiques tels que ceux commercialisés par D-Wave lorsqu'ils sont confrontés à des cas de problèmes de couplage biparti de cardinalité maximale spécifiquement conçus pour être difficiles à résoudre au moyen d'un recuit simulé. Nous comparons un "Washington" (2X) de D-Wave avec 1098 qubits utilisables sur différentes tailles d'instances et nous observons que pour tous ces cas, sauf les plus triviaux, la machine ne parvient pas à obtenir une solution optimale. Ainsi, nos résultats suggèrent que le recuit quantique, du moins tel qu'il est mis en œuvre dans un dispositif D-Wave, tombe dans les mêmes pièges que le recuit simulé et fournit donc des preuves supplémentaires suggérant qu'il existe des problèmes polynomiaux qu'une telle machine ne peut pas résoudre efficacement pour atteindre l'optimalité. En outre, nous étudions dans quelle mesure les topologies d'interconnexion des qubits expliquent ces derniers résultats expérimentaux.