⚛️ quantum physics

Accuracy and Performance Evaluation of Quantum, Classical and Hybrid Solvers for the Max-Cut Problem

Cet article évalue les solveurs quantiques, classiques et hybrides sur des problèmes de Max-Cut à travers 139 instances, révélant que si les méthodes hybrides et de recuit simulé classique trouvent systématiquement les optima globaux pour les petites instances, la machine de bifurcation simulée et les variantes classiques plus lentes offrent une qualité de solution supérieure pour les grandes instances où les optima globaux sont inconnus.

Auteurs originaux : Jaka Vodeb, Vid Eržen, Timotej Hrga, Janez Povh

Publié 2026-07-07

📖 4 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Jaka Vodeb, Vid Eržen, Timotej Hrga, Janez Povh

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez de résoudre un puzzle massif et incroyablement complexe. Le but est de diviser un groupe de points connectés (comme un réseau social ou un circuit imprimé) en deux groupes distincts de manière à ce que le nombre de connexions entre les groupes soit le plus élevé possible. Cela s'appelle le problème du Max-Cut. C'est un type de puzzle célèbre, notoirement difficile à résoudre pour les ordinateurs, surtout quand le puzzle devient immense.

Ce document est essentiellement un « rapport de course ». Les auteurs ont réuni un groupe de différents « coureurs » (algorithmes informatiques) pour voir qui résout ces puzzles le mieux et le plus rapidement. Ils ont testé trois types de coureurs :

Le Coureur Quantique (D-Wave QPU) : Une machine flambant neuve et de haute technologie qui utilise les lois étranges de la physique quantique (comme l'effet tunnel pour traverser les murs) pour trouver des réponses.
Le Coureur Hybride (D-Wave Hybrid) : Un capitaine d'équipe intelligent qui utilise la machine quantique pour les parties difficiles, mais qui s'appuie sur des ordinateurs classiques pour le reste.
Le Coureur Classique (Simulated Annealing & SBM) : Des méthodes anciennes, éprouvées et perfectionnées au fil des ans. Imaginez des randonneurs très expérimentés et méthodiques.

Voici comment la course s'est déroulée, décomposée selon la taille du puzzle :

Les Petits Puzzles (100 à 151 points)

Pour ces puzzles plus petits, les auteurs connaissaient la solution parfaite (l'Optimum Global) car ils les avaient résolus auparavant avec une calculatrice extrêmement précise et lente.

Le Résultat : Le Coureur Hybride et les Coureurs Classiques étaient parfaits. Ils trouvaient l'exacte bonne réponse à chaque fois.
Le Coureur Quantique : Il a trébuché. Bien qu'il fût rapide, les réponses qu'il donnait étaient souvent loin d'être parfaites. C'était comme un sprinter qui court très vite mais qui n'arrête pas de trébucher sur ses propres lacets, manquant la ligne d'arrivée de quelques pas.

Les Puzzles Moyens (250 à 500 points)

Ces puzzles étaient trop grands pour que le Coureur Quantique puisse même entrer dans la course.

Le Résultat : Le Coureur Hybride et les Coureurs Classiques ont continué à dominer, trouvant les meilleures réponses connues de la science. Ils étaient comme une machine bien huilée, frappant la cible à chaque fois.

Les Puzzels Géants (800 à 10 000 points)

Ces puzzles étaient si massifs que personne ne connaissait la réponse parfaite. Les auteurs ont dû se fier à la « meilleure supposition » trouvée dans des recherches antérieures.

Le Résultat : C'est là que les choses sont devenues intéressantes.
- Le Toshiba SBM (une machine classique spécialisée) et le Coureur Classique lent et prudent (SA2) ont été les champions. Ils ont trouvé les solutions de la plus haute qualité, battant tout le monde. Cependant, le coureur « lent » a pris beaucoup de temps pour réfléchir, comme un grand maître d'échecs calculant chaque mouvement.
- Le Coureur Hybride était un second très proche en termes de qualité, mais il était beaucoup plus rapide, terminant dans un temps similaire à celui de la machine Toshiba.
- Le Coureur Classique rapide (SA1) était rapide mais a sacrifié la qualité, trouvant des solutions nettement moins bonnes.
- Le Coureur Quantique n'a même pas pu courir cette course ; les puzzles étaient simplement trop grands pour son matériel actuel.

Les Grandes Conclusions

Vitesse vs Précision : La nouvelle machine quantique est rapide, mais pour ces puzzles spécifiques, elle n'est pas encore assez précise. C'est comme une voiture de sport qui roule vite mais qui ne sait pas bien négocier les virages.
Le Problème de la « Boîte Noire » : Le solveur hybride (le capitaine d'équipe) est incroyablement efficace et peut gérer de très grands puzzles rapidement. Cependant, c'est une « boîte noire ». Les chercheurs ne peuvent pas voir à l'intérieur pour comprendre comment il fonctionne ni exactement quand il utilise la partie quantique. Il donne simplement une excellente réponse, mais le « comment » reste un mystère.
Les Vieux Chiens et les Nouveaux Tours : Les méthodes classiques et transparentes (Simulated Annealing), lorsqu'elles sont ajustées avec soin, battent toujours le matériel quantique sophistiqué en termes de recherche des meilleures réponses. Parfois, une approche lente et réfléchie (SA2) bat une approche rapide et tape-à-l'œil.

En résumé : Le document conclut que, bien que la technologie quantique soit passionnante et en progression, pour la tâche spécifique de résoudre ces puzzles de Max-Cut actuellement, un mélange d'informatique classique et de stratégies hybrides intelligentes surpasse la machine quantique pure, tant en précision qu'en capacité à gérer de grands problèmes. La machine quantique est un sprinter prometteur, mais elle n'a pas encore appris à courir le marathon parfaitement.

Résumé technique : Évaluation de la précision et des performances des solveurs quantiques, classiques et hybrides pour le problème Max-Cut

Définition du problème
Cette étude traite du problème Max-Cut, qui est NP-difficile, ainsi que de sa formulation équivalente, le problème d'optimisation binaire quadratique non contrainte (QUBO). L'objectif est de partitionner les sommets d'un graphe non orienté pondéré en deux ensembles disjoints de telle sorte que la somme des poids des arêtes reliant les ensembles soit maximisée. L'article évalue la capacité de divers solveurs à trouver des solutions proches de l'optimum global, en reconnaissant que pour les instances de grande taille, les solutions exactes sont souvent informatiquement intraitables, nécessitant ainsi des heuristiques approximatives.

Méthodologie et configuration expérimentale
Les auteurs ont mené une étude comparative approfondie utilisant trois ensembles de données distincts comprenant 139 instances de problèmes dont la taille varie de 100 à 10 000 nœuds.

Ensembles de données :
1. Billionnet et Elloumi (be) : 50 instances avec $n \in \{101, 121, 151\}$ . Les optima globaux ont été calculés à l'aide de solveurs exacts BiqBin et MADAM.
2. Collection Beasley (bqp) : 20 instances avec $n \in \{251, 501\}$ . Les optima pour $n=251$ ont été calculés exactement ; pour $n=501$ , les meilleures valeurs connues de la littérature ont été utilisées.
3. Jeu de données G (G) : 69 instances avec $n \in \{800, 1000, 2000, 3000, 5000, 7000, 8000, 9000, 10000\}$ . Les optima globaux sont inconnus ; les meilleures solutions connues de la littérature ont été utilisées comme références.
Solveurs évalués :
- Recuit quantique (QPU) : Système D-Wave Advantage utilisant une fonctionnalité de « recuit rapide » (fast annealing) pour isoler les qubits des effets environnementaux. Limité aux instances avec $n \le 151$ .
- Solveur hybride : Le « LeapHybridSampler » de D-Wave, basé sur le cloud, qui combine de manière itérative des méthodes classiques (recuit simulé interrompible, recherche tabou, trempe parallèle) avec des appels QPU. Capable de gérer toutes les tailles d'instances.
- Recuit simulé classique (SA) : Deux variantes de l'algorithme de [3] ont été implémentées :
  - SA1 : Pas de saut agressif, température initiale de 10 000 (optimisé pour un temps d'exécution comparable au QPU).
  - SA2 : Pas de saut conservateur, température initiale de 40 000 (optimisé pour la qualité de la solution).
- Machine de bifurcation simulée (SBM) : Le solveur matériel de Toshiba. Les résultats ont été tirés de la littérature existante [4], car les auteurs n'avaient pas d'accès direct au solveur.

Résultats clés

Petites instances ( $n \le 151$ ) : Le solveur hybride et les deux variantes de SA (SA1, SA2) ont systématiquement atteint l'optimum global pour toutes les instances. Le QPU, cependant, a systématiquement produit des solutions significativement éloignées de l'optimum global.
Instances moyennes ( $n = 251, 501$ ) : Le solveur hybride et les variantes de SA ont de nouveau égalé les optima globaux (pour $n=251$ ) ou les meilleures valeurs connues (pour $n=501$ ). Le QPU n'a pas pu être testé en raison de limites de capacité.
Grandes instances ( $n \ge 800$ ) :
- Qualité de la solution : Le SBM et le SA2 ont produit les solutions de la plus haute qualité, trouvant souvent les meilleures valeurs connues. Le solveur hybride a performé de manière notablement moins bien que le S SBM et le SA2, tandis que le SA1 a produit les solutions de la plus faible qualité parmi les méthodes testées.
- Temps de calcul : Le solveur hybride et le SBM ont démontré des temps de calcul efficaces (quelques secondes à quelques dizaines de secondes). Le SA2 a nécessité beaucoup plus de temps (des centaines de secondes, environ 1000 fois plus lent que l'Hybride/SBM dans certaines comparaisons) pour atteindre une qualité de solution supérieure. Le SA1 avait un temps d'exécution comparable au solveur hybride mais produisait des solutions inférieures.

Signification et affirmations
L'article affirme faire progresser la compréhension de l'optimisation assistée par ordinateur quantique en testant rigoureusement le nouveau QPU de recuit rapide de D-Wave et le solveur hybride contre des méthodes classiques de pointe sur un ensemble standardisé et public d'instances Max-Cut.

Les auteurs concluent que :

Limitations du QPU : Le QPU de D-Wave, même avec le recuit rapide, ne parvient pas à trouver des solutions optimales pour les instances testées et est limité par la taille du problème ( $n \le 151$ ).
Efficacité de l'hybride : Le solveur hybride de D-Wave est très efficace en termes de vitesse et d'évolutivité (gérant jusqu'à 10 000 nœuds) et produit des solutions quasi optimales pour les petites instances. Cependant, pour les plus grandes instances, il est surpassé en qualité de solution par le SA classique (spécifiquement la variante SA2) et le SBM.
Compétitivité du classique : Les algorithmes de recuit simulé classiques transparents (spécifiquement la variante SA2) restent hautement compétitifs, surpassant souvent le solveur hybride « boîte noire » en qualité de solution, bien qu'à un coût de calcul plus élevé.
Écart de transparence : Les auteurs expriment leur frustration concernant la nature « boîte noire » du solveur hybride, notant que le manque de visibilité sur son flux de travail interne et l'utilisation des ressources quantiques entrave l'analyse scientifique.

L'étude ne revendique pas d'avantage quantique pour les solveurs et les instances de problèmes spécifiques testés ; elle souligne plutôt que pour le Max-Cut, les heuristiques classiques actuelles (lorsqu'elles sont ajustées pour la qualité) et le matériel spécialisé comme le SBM peuvent surpasser ou égaler les performances des approches quantiques et hybrides testées.

Les Petits Puzzles (100 à 151 points)

Les Puzzles Moyens (250 à 500 points)

Les Puzzels Géants (800 à 10 000 points)

Les Grandes Conclusions

Articles similaires