⚛️ quantum physics

Cutting-plane methodology via quantum optimization for solving the Traveling Salesman Problem

Cet article propose une méthodologie itérative combinant une pré-réduction des arcs et la génération dynamique de contraintes pour résoudre le problème du voyageur de commerce, démontrant par des expériences computationnelles que cette approche améliore les performances des solveurs classiques, quantiques directs et hybrides sur le matériel D-Wave.

Auteurs originaux : Alessia Ciacco, Luigi Di Puglia Pugliese, Francesca Guerriero

Publié 2026-04-23

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Alessia Ciacco, Luigi Di Puglia Pugliese, Francesca Guerriero

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

🌍 Le Problème : Le Voyageur de Commerce Perdu

Imaginez que vous êtes un vendeur ambulant (le "Voyageur de Commerce") qui doit visiter 30 villes différentes pour vendre ses produits. Votre mission est simple :

Visiter chaque ville une seule fois.
Revenir à votre point de départ.
Faire le plus court chemin possible pour économiser l'essence et le temps.

Cela semble facile, non ? Le problème, c'est que le nombre de combinaisons possibles explose littéralement. Si vous avez 10 villes, il y a des milliers de façons de les visiter. Si vous en avez 30, le nombre de possibilités est plus grand que le nombre d'atomes dans l'univers ! C'est ce qu'on appelle un problème "NP-difficile".

🚧 L'Obstacle Majeur : Les "Boucles Interdites"

Pour résoudre ce problème avec un ordinateur, on utilise des équations. Mais il y a un piège énorme : les boucles interdites (ou subtours).

Imaginez que votre ordinateur propose un itinéraire où vous visitez Paris, Lyon et Marseille, puis vous revenez à Paris, sans jamais avoir visité Rome ou Berlin. C'est une boucle fermée qui laisse des villes de côté.
Pour éviter cela, il faut ajouter une règle mathématique pour chaque groupe possible de villes : "Vous ne pouvez pas faire une boucle uniquement entre ces 3 villes".
Le problème ? Avec 30 villes, il faut des milliards de règles pour couvrir toutes les combinaisons possibles. C'est comme essayer de construire un mur avec des milliards de briques avant même de commencer à bâtir la maison. L'ordinateur s'effondre sous le poids des règles.

💡 La Solution Proposée : Deux Astuces Magiques

Les auteurs de ce papier (Alessia, Luigi et Francesca) ont trouvé une façon intelligente de contourner ce mur de briques en utilisant deux stratégies combinées :

1. La Méthode "Coupe-à-Coupe" (Le Détective)

Au lieu d'écrire toutes les règles interdites d'un coup (ce qui est impossible), ils utilisent une approche itérative, comme un détective qui enquête pas à pas.

Étape 1 : L'ordinateur propose un itinéraire rapide, sans se soucier des boucles interdites.
Étape 2 : Le détective regarde le résultat. "Ah ! Vous avez fait une boucle entre Paris et Lyon sans aller à Rome ?"
Étape 3 : Il ajoute une seule règle pour interdire cette boucle précise.
Étape 4 : Il relance le calcul.
Il ne ajoute des règles que lorsqu'elles sont vraiment nécessaires. C'est comme si on nettoyait une pièce sale : on ne nettoie pas tout le sol d'un coup, on enlève juste les taches au fur et à mesure qu'on les voit.

2. Le Filtre "Raccourcis" (Le Tri Sélectif)

Avant même de commencer, ils utilisent une astuce appelée Filtrage par Coût (CAF).
Imaginez que vous devez aller de Paris à Lyon. Vous avez le choix entre 100 routes. La plupart sont des détours immenses. L'astuce consiste à dire : "On ne va même pas regarder les routes qui font 10 fois plus de kilomètres que la plus courte. On ne garde que les 20 routes les plus logiques."
Cela réduit considérablement le nombre de choix à faire pour l'ordinateur, rendant le problème beaucoup plus petit et plus facile à résoudre.

⚛️ L'Apport du "Quantum" : Le Saut dans le Tunnel

Le papier teste ces méthodes sur deux types d'ordinateurs :

Les ordinateurs classiques (comme votre PC).
Les ordinateurs quantiques (comme ceux de D-Wave).

Les ordinateurs quantiques fonctionnent différemment : au lieu de calculer une seule solution à la fois, ils utilisent des phénomènes comme le tunneling quantique. Imaginez que vous cherchez le point le plus bas d'un paysage montagneux (la meilleure solution). Un ordinateur classique doit grimper et descendre chaque colline pour trouver le fond. Un ordinateur quantique, lui, peut littéralement traverser les montagnes comme un fantôme pour trouver le point bas plus vite.

Cependant, les ordinateurs quantiques actuels sont petits et fragiles. Ils ne peuvent pas gérer les problèmes trop gros. C'est là que les deux astuces (le détective et le filtre) deviennent cruciales : elles réduisent le problème à une taille que l'ordinateur quantique peut vraiment "manger".

🏆 Les Résultats : Qui Gagne ?

Les auteurs ont testé leur méthode sur des problèmes réels (des villes réelles) :

Sur les ordinateurs classiques : La méthode "Coupe-à-Coupe" combinée au filtre a permis de résoudre des problèmes 30 fois plus grands que la méthode classique habituelle, en une fraction de seconde.
Sur les ordinateurs quantiques (Direct) : Sans ces astuces, l'ordinateur quantique échouait dès 8 ou 9 villes. Avec les astuces, il a réussi à trouver de bonnes solutions jusqu'à 10-12 villes, ce qui est un progrès énorme.
Sur les ordinateurs hybrides (Le meilleur des deux mondes) : C'est le grand gagnant. Ils ont mélangé la puissance de l'ordinateur classique (pour gérer la logique) et celle du quantique (pour explorer les solutions). Résultat : ils ont trouvé la solution parfaite pour des problèmes de 25 villes, et une solution quasi-parfaite (à 1% près) pour 30 villes.

🚀 En Résumé

Ce papier nous dit que l'ordinateur quantique n'est pas encore prêt à tout résoudre tout seul. Mais si on l'aide avec de bonnes méthodes classiques (comme ne regarder que les routes logiques et ne poser des questions que quand nécessaire), il devient un partenaire très puissant.

C'est comme si on donnait à un super-héros (l'ordinateur quantique) un plan de bataille précis (les méthodes classiques) : soudainement, il peut accomplir des tâches qu'il ne pouvait pas faire seul. C'est une étape importante vers l'avenir où nous utiliserons ces technologies pour résoudre des problèmes complexes de logistique, de trafic ou de livraison.

1. Problématique

Le Problème du Voyageur de Commerce (TSP) est un problème classique d'optimisation combinatoire NP-difficile. Il consiste à trouver le chemin le plus court visitant un ensemble de villes exactement une fois et revenant au point de départ.

Défi principal : La formulation mathématique standard (Programmation Linéaire en Nombres Entiers - ILP) nécessite l'ajout de contraintes d'élimination des sous-tours (subtour elimination constraints) pour garantir que la solution forme un cycle unique.
Complexité : Le nombre de ces contraintes croît de manière exponentielle ( $O(2^n)$ ) avec le nombre de villes $n$ . Inclure explicitement toutes ces contraintes rend la formulation intractable, même pour des instances de taille modérée.
Contexte Quantique : L'application de l'optimisation quantique (notamment le recuit quantique sur les machines D-Wave) au TSP est limitée par la capacité des qubits et la difficulté d'encoder des contraintes complexes dans des modèles QUBO (Quadratic Unconstrained Binary Optimization) ou CQM (Constrained Quadratic Model).

2. Méthodologie Proposée

Les auteurs proposent un cadre hybride combinant des techniques d' recherche opérationnelle éprouvées avec des approches d'optimisation quantique. La méthodologie repose sur deux piliers complémentaires :

A. Approche par Plans Coupants (Cutting-Plane Approach - CPA)

Au lieu d'inclure toutes les contraintes d'élimination des sous-tours dès le départ, l'approche est itérative et paresseuse (lazy constraint generation) :

Modèle initial : Résolution d'un modèle relaxé ne contenant que les contraintes de degré (chaque ville visitée une fois) et les contraintes de domaine binaire.
Détection : Analyse de la solution obtenue pour détecter la présence de sous-tours (cycles disjoints).
Ajout dynamique : Si des sous-tours sont détectés, les contraintes d'élimination correspondantes sont ajoutées dynamiquement au modèle ("coupes").
Itération : Le problème est résolu à nouveau. Ce processus se répète jusqu'à l'obtention d'un cycle Hamiltonien unique.

Avantage : Réduit drastiquement la taille du modèle initial en n'ajoutant que les contraintes strictement nécessaires.

B. Prétraitement par Filtrage d'Arêtes basé sur le Coût (Cost-based Arc Filtering - CAF)

Une phase de prétraitement est intégrée pour réduire l'espace de recherche :

Pour chaque ville, les arêtes sortantes sont triées par coût.
Seuls les voisins les plus proches (un sous-ensemble d'arêtes) sont conservés ; les arêtes à coût élevé, peu susceptibles de faire partie d'une solution optimale, sont éliminées.
Avantage : Réduit le nombre de variables de décision et la densité du modèle tout en préservant la connectivité nécessaire.

C. Implémentations Quantiques

L'étude compare plusieurs paradigmes d'exécution sur l'écosystème D-Wave :

Exécution Directe sur QPU (QUBO) : Transformation du problème en modèle QUBO où les contraintes sont intégrées via des termes de pénalité dans la fonction objectif. Exécuté directement sur le processeur quantique.
Solveurs Hybrides Quantique-Classique (CQM) : Utilisation du modèle CQM qui permet de représenter explicitement les contraintes linéaires/quadratiques. Le solveur hybride (LeapCQMHybrid) orchestre des heuristiques classiques et des cycles de recuit quantique pour explorer l'espace de recherche.

3. Contributions Clés

Première application itérative : C'est la première application d'une génération paresseuse de contraintes (CPA) dans un cadre de recuit quantique pour le TSP.
Réduction de complexité : Démonstration que la combinaison CPA + CAF permet de réduire significativement la taille du modèle (variables et contraintes), le rendant compatible avec les architectures quantiques actuelles.
Comparaison exhaustive : Analyse comparative entre les méthodes classiques (ILP complet vs CPA), l'exécution directe sur QPU et les solveurs hybrides.
Passage à l'échelle : Capacité à résoudre des instances de TSP standard (TSPLIB) jusqu'à 45 nœuds avec des méthodes classiques et jusqu'à 30 nœuds avec des méthodes quantiques hybrides, dépassant les limites habituelles des approches quantiques pures (souvent limitées à <10-15 nœuds).

4. Résultats Expérimentaux

Les expériences ont été menées sur des instances TSPLIB (jusqu'à 45 villes) avec un processeur Intel et des ressources D-Wave (Advantage2).

Performance Classique :
- L'approche ILP complet devient intractable dès $n=20$ (temps de calcul prohibitif).
- L'approche CPA + CAF résout des instances jusqu'à $n=45$ en moins d'une seconde, avec une réduction des contraintes de plus de 95-100% par rapport à l'ILP complet.
Performance Quantique Directe (QPU) :
- L'approche ILP (QUBO) échoue rapidement : aucune solution réalisable trouvée pour $n \ge 6$ en raison de la densité excessive du modèle QUBO.
- L'approche CPA (QUBO) montre une meilleure robustesse, trouvant des solutions réalisables jusqu'à $n=8$ avec un écart d'optimalité faible, mais échoue au-delà de $n=10$ en raison des limites matérielles de connectivité et de bruit.
Performance Hybride (CQM) :
- C'est l'approche la plus performante.
- Optimalité : Solutions optimales trouvées pour toutes les instances jusqu'à $n=25$ (écart d'optimalité de 0%).
- Extensibilité : Pour $n=30$ , un écart d'optimalité très faible de 1% est observé.
- Temps de calcul : Les temps restent raisonnables (de ~44s pour $n=12$ à ~140s pour $n=30$ ), démontrant une scalabilité bien supérieure aux méthodes directes.

5. Signification et Conclusion

Réduction de l'écart de scalabilité : L'article démontre que les limitations actuelles de l'optimisation quantique ne sont pas uniquement dues au matériel, mais aussi à la manière dont les problèmes sont modélisés. Une modélisation intelligente (CPA + CAF) est cruciale.
Supériorité des approches hybrides : Les solveurs hybrides (CQM) surpassent nettement les exécutions directes sur QPU pour les problèmes combinatoires complexes comme le TSP, en combinant la puissance d'exploration classique avec l'affinement quantique.
Perspectives : Ce travail ouvre la voie à l'utilisation pratique de l'optimisation quantique pour des problèmes réels de logistique et de routage, en attendant l'amélioration future du matériel quantique. Il suggère que l'avenir réside dans l'intégration de techniques de réduction de modèle avancées avec des solveurs hybrides.

En résumé, cette étude prouve que l'application de techniques classiques de réduction de complexité (plans coupants et filtrage d'arêtes) est indispensable pour rendre l'optimisation quantique applicable à des problèmes de taille significative, comblant ainsi le fossé entre la théorie quantique et les applications pratiques.