Multi-Objective Optimization by Quantum-Annealing-Inspired Algorithms

Cet article démontre que les algorithmes inspirés du recuit quantique basés sur les GPU (QAIAs) surpassent à la fois les heuristiques classiques de l'état de l'art et les processeurs quantiques précédemment étudiés pour résoudre des problèmes de MaxCut multi-objectifs en réalisant des temps d'exécution de bout en bout nettement plus rapides lorsqu'on prend en compte l'ensemble des surcharges de traitement.

L'essentiel

Imaginez que vous essayiez d'organiser une fête massive et chaotique. Vous avez trois objectifs différents qui entrent souvent en conflit : vous voulez que la musique soit forte, que la nourriture soit bon marché et que les invités soient heureux. Vous ne pouvez pas maximiser les trois à la fois ; si vous dépensez plus pour la nourriture, la musique risque de devenir plus calme. Votre objectif n'est pas de trouver un seul « plan de fête parfait », mais de trouver une liste des meilleurs compromis possibles (un « front de Pareto ») où vous ne pouvez pas améliorer une chose sans en nuire à une autre.

C'est cela, l'Optimisation Multi-Objectif : trouver le meilleur équilibre entre des objectifs contradictoires.

Cet article traite d'une nouvelle méthode ultra-rapide pour trouver ces compromis, en utilisant un programme informatique « inspiré du quantique » exécuté sur une carte graphique standard (GPU). Voici le détail en termes simples :

Le Problème : Le Dilemme de l'Organisateur de Fêtes

Dans le passé, les chercheurs ont tenté de résoudre ces problèmes en utilisant deux outils principaux :

1. Les Ordinateurs Quantiques Réels : Ce sont comme des boîtes noires magiques et mystérieuses capables d'explorer de nombreuses possibilités à la fois. Des études récentes ont montré qu'ils étaient bons pour trouver des plans de fête, mais qu'ils étaient lents à configurer et nécessitaient beaucoup de travail supplémentaire pour nettoyer les résultats.
2. Les Ordinateurs Classiques : Ce sont les ordinateurs standards que nous utilisons tous les jours. Ils sont fiables, mais parfois lents à trouver les meilleurs compromis.

Les auteurs de cet article ont remarqué que les études précédentes comparant ces deux outils étaient injustes. Ils ne comptaient que le temps que la « boîte magique » mettait pour émettre une liste brute d'idées, en ignorant le temps nécessaire pour construire le problème, exécuter la machine et nettoyer la liste afin de trouver les véritables gagnants.

La Solution : Le « Sprinter » Inspiré du Quantique

Les auteurs ont créé un nouvel algorithme appelé QAIA (Algorithme Inspiré du Recuit Quantique). Imaginez cela non pas comme un véritable ordinateur quantique, mais comme une simulation très intelligente de celui-ci, exécutée sur une puissante carte graphique (GPU) à l'intérieur d'un ordinateur ordinaire.

Pour rendre cette simulation encore meilleure dans la recherche de plans de fêtes diversifiés, ils ont ajouté un peu de « Bruit Gaussien ».

• L'Analogie : Imaginez un groupe de randonneurs essayant de trouver les plus hauts sommets d'une chaîne de montagnes brumeuse. Un algorithme standard est comme un randonneur qui reste coincé sur la première colline qu'il voit. La méthode des auteurs ajoute une « brise » (le bruit) qui pousse doucement les randonneurs hors de leurs endroits confortables, les forçant à explorer différentes vallées et sommets. Cela garantit qu'ils trouvent une plus grande variété des meilleurs compromis, et pas seulement un ou deux.

La Course : Qui est le Plus Rapide ?

L'équipe a organisé une course entre leur nouvelle méthode, les ordinateurs quantiques réels et les meilleures méthodes classiques.

1. La Vitesse d'Échantillonnage (Trouver des Candidats) :

   • Le Résultat : Leur méthode basée sur GPU était 100 fois plus rapide que les ordinateurs quantiques réels pour générer des listes brutes de solutions potentielles.
   • La Métaphore : Si l'ordinateur quantique est une voiture de course qui met 10 secondes à démarrer son moteur et à faire un tour, la nouvelle méthode est une Formule 1 qui est déjà en marche et qui complète le tour en une fraction de seconde.

2. Le Temps de Bout en Bout (Le Travail Complet) :

   • Cela inclut la construction du problème, l'exécution de la simulation et le nettoyage des résultats.
   • Le Résultat : Leur méthode était toujours 10 fois plus rapide que les meilleurs algorithmes classiques et nettement plus rapide que les ordinateurs quantiques lorsque l'on compte tout.
   • La Métaphore : Même en tenant compte du temps nécessaire pour emballer la voiture et se rendre sur le circuit, la méthode GPU a terminé tout le trajet bien avant les autres.

Le Bémol : Qualité contre Quantité

Bien que la nouvelle méthode soit incroyablement rapide pour produire des chiffres, l'article note un petit compromis :

• Les Ordinateurs Quantiques Réels étaient très « efficaces » en ce sens qu'ils avaient besoin de moins de suppositions totales pour trouver la liste parfaite des compromis.
• La Nouvelle Méthode avait besoin de faire quelques suppositions (échantillons) de plus pour trouver la même liste, mais comme elle était si incroyablement rapide pour faire ces suppositions, elle a tout de même gagné la course dans l'ensemble.

La Conclusion

L'article affirme que pour le type spécifique de problème qu'ils ont testé (MaxCut avec plusieurs objectifs), un ordinateur standard exécutant ce nouveau code « inspiré du quantique » est actuellement le meilleur outil disponible. Il bat à la fois les ordinateurs quantiques réels, coûteux et lents, et les méthodes classiques traditionnelles en termes de vitesse et de performance globale.

Ils concluent que, bien que les ordinateurs quantiques réels soient prometteurs, cette approche « inspirée du quantique » sur du matériel ordinaire est actuellement le champion pour résoudre ces équilibres complexes.

Résumé technique

1. Définition du problème

L'article aborde l'Optimisation Multi-Objectif (OMO), spécifiquement le problème du MaxCut Multi-Objectif (MO-MaxCut).

• Contexte : Contrairement à l'optimisation mono-objectif, l'OMO vise à trouver un ensemble de solutions Pareto-optimales (le front de Pareto), où aucun objectif ne peut être amélioré sans dégrader un autre.
• Le Défi : Les études existantes comparant les solveurs quantiques (QAOA à portes et Recuit Quantique) aux heuristiques classiques se concentrent souvent uniquement sur la vitesse d'échantillonnage, ignorant les frais généraux substantiels liés à la construction du modèle, à la compilation des circuits et au filtrage Pareto (post-traitement) intensif en calcul nécessaire pour extraire l'ensemble non dominé des échantillons bruts.
• Objectif : Fournir une comparaison rigoureuse de bout en bout des solveurs quantiques et classiques, en tenant compte du temps d'exécution total (modélisation + échantillonnage + filtrage) et en évaluant si le matériel quantique actuel offre un avantage pratique par rapport aux algorithmes classiques « inspirés du quantique » les plus avancés.

2. Méthodologie

Les auteurs proposent et évaluent un Algorithme Inspiré du Recuit Quantique (QAIA) accéléré par GPU basé sur la Bifurcation Simulée (SB).

A. Formulation mathématique

• Hamiltonien : Le problème MO-MaxCut est mappé sur un modèle d'Ising. Pour $K$ objectifs, le système minimise un vecteur d'Hamiltoniens $H(s) = (H_1, \dots, H_K)$.
• Scalarisation : Pour résoudre le problème multi-objectif à l'aide de solveurs mono-objectif, les auteurs utilisent la Méthode de la Somme Pondérée. Ils génèrent des vecteurs de poids en utilisant une conception de réseau simplexe de Das–Dennis pour créer des Hamiltoniens scalarisés : $H_{total}(s; c) = \sum c_k H_k(s)$.
• Filtrage Pareto : Les échantillons bruts sont traités via un algorithme classique de Tri Non-Dominé pour filtrer les solutions dominées et construire l'approximation finale du front de Pareto.

B. L'algorithme proposé : Bifurcation Simulée à Injection de Bruit (NI-SB)

Le solveur principal est une variante de l'algorithme de Bifurcation Simulée, qui simule la dynamique hamiltonienne classique d'oscillateurs non linéaires pour trouver des états de basse énergie.

• Ballistique (bSB) vs Discrète (dSB) : Les auteurs utilisent à la fois les variantes continues (ballistiques) et discrètes de la SB.
• Injection de bruit gaussien : Pour pallier le manque de diversité de la SB déterministe (qui converge souvent vers la même solution), les auteurs introduisent un bruit blanc gaussien dans l'équation de la quantité de mouvement :
  $$\dot{y}_i = -[a_0 - a(t)]x_i + c_0 \sum J_{ij}\phi(x_j) + \alpha \eta_i$$
  où $\eta_i \sim \mathcal{N}(0, 1)$. Ce « bruit thermique synthétique » permet aux trajectoires d'explorer des régions diverses de l'espace des solutions, ce qui est crucial pour couvrir efficacement le front de Pareto.
• Implémentation matérielle : L'algorithme est implémenté sur des GPU (NVIDIA RTX 4090), exploitant le parallélisme massif pour traiter des milliers de solutions candidates simultanément en utilisant une arithmétique de demi-précision (float16).

3. Contributions clés

1. Benchmarking de bout en bout : L'article déplace la métrique d'évaluation du « temps d'échantillonnage » vers le temps d'exécution total de bout en bout, incluant explicitement la construction du modèle et les frais généraux de filtrage Pareto, qui sont souvent omis dans les revendications d'avantage quantique.
2. Base de référence classique solide : Les auteurs établissent que le QAIA accéléré par GPU sert de base de référence classique redoutable, surpassant à la fois le matériel quantique et les heuristiques classiques traditionnelles.
3. SB à injection de bruit : L'introduction de bruit gaussien dans la SB améliore considérablement la diversité des échantillons pour l'OMO, permettant à l'algorithme de récupérer l'ensemble complet de Pareto avec moins d'échantillons totaux par rapport au QAOA.
4. Comparaison complète : L'étude compare la méthode proposée contre :
   • Quantique : D-Wave Advantage/Advantage2 (RQ) et IBM Fez (QAOA).
   • Heuristiques classiques : DCM, DPA-a, MOEA/D, NSGA-II, NSGA-III et RVEA.

4. Résultats

Les expériences ont été menées sur des instances MO-MaxCut avec un nombre variable de variables ($n$) et d'objectifs ($K=3, 4$).

• Vitesse d'échantillonnage :

  • Le QAIA est environ deux ordres de grandeur plus rapide pour échantillonner des solutions candidates que les processeurs quantiques précédemment étudiés (RQ et QAOA).
  • Le QAIA atteint le plateau d'Hypervolume optimal en $10^{-2}$ à $10^{-1}$ secondes, tandis que les systèmes RQ nécessitent de quelques secondes à quelques minutes.

• Efficacité et qualité des échantillons :

  • QAIA vs QAOA : Le QAIA récupère l'ensemble complet de Pareto avec ~10 fois moins de candidats que le QAOA.
  • QAIA vs RQ : Bien que le RQ nécessite moins d'échantillons en moyenne pour trouver l'ensemble de Pareto, le QAIA compense par une vitesse d'échantillonnage vastly supérieure.

• Performance de bout en bout :

  • Vs. Quantique : Le QAIA est ~1 ordre de grandeur plus rapide que le RQ et ~4 ordres de grandeur plus rapide que le QAOA en temps d'exécution total (filtrage inclus).
  • Vs. Heuristiques classiques : Sur des instances denses à 3 objectifs jusqu'à $n=200$, le QAIA surpasse MOEA/D, NSGA-II, NSGA-III et RVEA en termes de temps d'exécution et de qualité de solution (Hypervolume).
    • Exemple : Pour $n=200$, le QAIA a atteint 99 % de l'Hypervolume optimal en <1 seconde, tandis que les heuristiques classiques ont pris **9–11 secondes** et obtenu des ratios d'Hypervolume inférieurs (60–93 %).

• Évolutivité :

  • La méthode a géré avec succès $n=200$ (graphe complet), dépassant les limites d'encodage actuelles des topologies Pegasus et Zephyr de D-Wave (environ 180–193 nœuds).

5. Importance et conclusion

• Redéfinition de l'avantage quantique : L'article soutient que pour les benchmarks MO-MaxCut actuels, les solveurs classiques inspirés du quantique accélérés par GPU fournissent actuellement une base de référence de bout en bout plus forte que le matériel quantique disponible. L'« avantage quantique » en vitesse d'échantillonnage est annulé par les frais généraux de l'exécution quantique et le parallélisme supérieur des GPU modernes.
• Utilité pratique : Les résultats suggèrent que pour les tâches pratiques d'optimisation multi-objectif, les solveurs d'Ising classiques (spécifiquement NI-SB) sont actuellement l'outil le plus efficace, offrant une convergence rapide et une haute qualité de solution.
• Voies futures : Les auteurs soulignent la nécessité de métriques qui séparent la vitesse d'échantillonnage de la qualité des échantillons (par exemple, rendement non dominé, rappel de l'ensemble de Pareto). Ils suggèrent également de tester ces méthodes sur des problèmes OMO plus larges au-delà du MaxCut et d'explorer d'autres variantes de QAIA (par exemple, SB assistée par thermique).

En résumé, ce travail démontre que si le matériel quantique s'améliore, les algorithmes classiques inspirés du quantique s'exécutant sur des GPU dominent actuellement le paysage de l'optimisation multi-objectif en termes de temps total de résolution et d'évolutivité.