Comparaison des machines de type "recuit simulé quantique" et des machines numériques

Antoine Browaeys

Daniel Vert

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.

Julien Rodriguez

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.

Daniel Estève, Michel Devoret

Daniel Vert

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.

Daniel Estève, Michel Devoret