L'ordinateur quantique en quête d'optimisation !

L'ordinateur quantique en quête d'optimisation !

Si vous n’êtes pas complètement novice avec le calcul quantique (ou si vous avez lu mes précédents articles), il est fort probable que les termes de « circuits » et de « portes » quantiques vous soient légèrement familiers. Mais ce n’est pas la seule manière de faire du calcul quantique ! Aujourd’hui, penchons nous sur le calcul quantique adiabatique !



Le calcul quantique adiabatique, également appelé recuit quantique, est une méthode de calcul quantique permettant de résoudre des problèmes d’optimisation. Pour faire simple, en mathématiques, résoudre un problème d’optimisation revient à trouver une solution satisfaisant au mieux un ensemble de critères parmi un (très) grand nombre de solutions possibles. Si les critères à satisfaire sont simples, les méthodes actuelles, comme l’intelligence artificielle, parviennent sans soucis à trouver une solution satisfaisante. Cependant, lorsque les critères se multiplient et rentrent en concurrence les uns avec les autres, tout se complique, et l’informatique quantique vient à la rescousse !



Un monde entier à optimiser !


Depuis plusieurs siècles maintenant, les mathématiciens ont théorisé de nombreux problèmes d’optimisation… et se sont creusé les méninges pour trouver les meilleurs méthodes de résolutions possibles. Prenons comme exemple un problème célèbre dans le milieu de l’optimisation : L’ordonnancement. C’est un terme barbare, mais vous avez tous certainement déjà payé les frais d’une mauvaise résolution de ce problème au moins une fois dans votre vie !


Par exemple, imaginez être le directeur d’un collège souhaitant répartir 300 élèves dans 10 classes. En toute logique, vous allez d’abord chercher à faire 10 classes de 30 élèves, mais il faut aussi que les niveaux entre les classes soient homogènes. Aussi, chacun des élèves à choisi une LV2, et il serait plus pratique que tous les collégiens ayant choisi espagnol, par exemple, soient dans la même classe. Dans l’idéal, il faudrait aussi respecter la parité. Ah oui, et aussi, n’oubliez pas aussi qu’avant les grandes vacances, chacun des élèves a noté les camarades avec lesquels il souhaitait être l’an prochain… Vous saisissez l’idée ?


Dans cet exemple, sauf situation idéale, il n’est pas possible de satisfaire à 100% tous les conditions énoncées, mais il existera toujours une solution dite optimale, qui satisfait mieux que toutes les autres solutions l’ensemble des critères. Afin de quantifier le niveau de satisfaction lié à une solution, on y associe un « coût ». Les meilleures solutions ont un coût bas, et les pires solutions (par exemple ici, faire une seule classe de 300 élèves) ont un coût très élevé. Afin d’évaluer ce coût, les mathématiciens modélisant se problème associent à chaque critère une « pondération ». Ces pondérations permettent de hiérarchiser les critères, et c’est bien cela qui rend les problèmes d’ordonnancement si complexes à résoudre !




Le calcul quantique à la rescousse !


Afin de résoudre un tel problème avec l’informatique classique, on doit procéder par étapes. Dans les approches dites « itératives », par exemple, considère une solution, obtenue en résolvant (parfois partiellement) le problème, puis l’on modifie légèrement cette solution. L’objectif est que la séquence modifiée ait un coût inférieur à la précédente, et on procède ainsi de suite jusqu’à ce qu’on arrête arbitrairement le calcul à une solution que l’on considère satisfaisante. Aucune garantie d’obtenir la meilleure solution donc…


Dans un calculateur quantique adiabatique, ce problème est principalement résolu grâce à la superposition d’états. Cela parait presque trop beau dit comme ça, cela mérite quelques explications :


Pour rappel, dans un ordinateur quantique, on doit paramétrer un système de manière à avoir de fortes chances d’obtenir les solutions qui résolvent notre problème (voir cet article pour plus de détails). Dans un ordinateur quantique « orienté circuit », on applique une série d’opérateurs appelés « portes quantiques » afin de modifier l’état du système et de faire varier les probabilités d’obtention des différentes solutions.





Dans un calculateur quantique adiabatique, on oublie les portes quantiques ! Ici, on part d’un état initial, dans lequel on a autant de chances de mesurer chacune des séquences possibles. On fait ensuite converger le système de cet état initial vers un état final. Dans cet état final, on encode notre problème avec ses pondérations, de manière à ce que chacune des solutions soit associée à un coût. La puissance du calcul quantique adiabatique, c’est que la probabilité de mesure d’une solution est inversement proportionnelle à son énergie. Autrement dit, plus l’énergie d’une solution est basse et plus on a de chances de la mesurer : Pratique non ?



Un grand pouvoir implique de grandes limitations


Et oui, comme toujours en quantique, c’est souvent un peu trop beau pour être vrai ! Comme dit précédemment, sur ces calculateurs, il n’est possible de résoudre que des problèmes d’optimisation… mais même au sein des problèmes d’optimisation, ce n’est pas si simple !


Sur un ordinateur quantique adiabatique, les problèmes doivent être soumis sous la forme de QUBOs, pour Quadratic Unconstrained Binary Optimization. Sans rentrer dans les détails mathématiques, retenez qu’il est souvent nécessaire de modifier le problème d’optimisation initial afin de trouver une formulation compatible avec la machine. En pratique, cette reformulation nécessite souvent de rajouter des variables au problème (et donc des qubits), dont le nombre est très limité sur les machines quantiques actuelles. Par conséquent, dans la littérature scientifique, ces contraintes de formulation mènent de nombreux chercheurs à conclure que le calcul quantique adiabatique ne serait pas, à long terme, concurrentiel avec les ordinateurs quantiques orientés circuit, plus versatiles. Mais cet avis ne fait pas l’unanimité !



D’une part, à l’heure actuelle, les calculateurs quantiques adiabatiques disposent d’un plus grand nombre de variables que leurs analogues orientés circuit. La dernière machine orientée circuit d’IBM possède un peu plus de 400 qubits, là où la dernière machine adiabatique de la société canadienne D-Wave en propose plus de 7000. Si cette tendance se poursuit, le nombre plus grand nombre de qubits disponibles sur les machines adiabatiques pourrait compenser le nombre de variables supplémentaires nécessaires pour reformuler les problèmes.

D’autre part, des chercheurs soulignent que la majorité des problèmes complexes à résoudre aujourd’hui, et donc pour lesquels on aurait un réel avantage à utiliser l’informatique quantique, peuvent être posés sous la forme de problèmes d’optimisation. Ainsi, bien que théoriquement moins versatiles, les calculateurs quantiques adiabatiques pourraient se révéler tout aussi utiles que les machines orientées circuit dans le futur !


En conclusion, même s’il est encore tôt pour se prononcer sur sa durabilité, le calcul quantique adiabatique apparait comme une alternative performante au calcul quantique orienté circuit. Aujourd’hui, de nombreux chercheurs se penchent sur la question de l’hybridation des calculateurs quantiques avec les ordinateurs classiques. On pourrait donc penser qu’à l’avenir, il serait pertinent d’également coupler les calculateurs quantiques entre eux, afin de tirer le meilleur parti de toutes les technologies quantiques !



Sources :


  1. Présentation globale des problèmes d’optimisation : https://towardsdatascience.com/unit-1-optimization-theory-e416dcf30ba8
  2. Présentation détaillée des problèmes d’ordonnancement : https://www.i3s.unice.fr/~malapert/thesis/split/chapitre3.pdf
  3. Présentation détaillée de l’algorithmie de l’annealing (en anglais) : https://arxiv.org/pdf/2112.07491.pdf 
  4. Site internet de D-Wave, constructeur de machines quantiques adiabatiques : https://www.dwavesys.com/

La technologie de la startup française Pasqal ; https://pasqal.io/technology/

Commentaire ( 0 ) :

S'inscrire à notre newsletter

Nous publions du contenu régulièrement, restez à jour en vous abonnant à notre newsletter.