Hybrid quantum-classical end-to-end pipeline for solving MILPs: a vehicle routing case study

Résumé technique : Pipeline hybride quantique-classique de bout en bout pour la résolution de problèmes MILP

Énoncé du problème
Les problèmes de programmation linéaire en nombres entiers mixtes (MILP) sont au cœur de la prise de décision à fort impact dans des secteurs tels que la logistique et la gestion de la chaîne d'approvisionnement, mais ils sont informatiquement complexes en raison de leur nature combinatoire. Bien que les techniques de décomposition comme la décomposition de Benders (BD) soient largement utilisées pour résoudre des MILP à grande échelle en séparant un problème maître (MP) et des sous-problèmes (SP), elles souffrent souvent d'une convergence lente. Cette convergence dépend de manière critique de la sélection de « coupes » (contraintes) informatives à ajouter au problème maître. Des travaux antérieurs par Paterakis [1] ont proposé d'utiliser le recuit quantique pour résoudre l'étape de sélection de coupes — formulée comme un problème de couverture minimale d'ensembles — afin d'accélérer ce processus. Cependant, le recuit quantique nécessite des procédures de micro-encapsulation (minor-embedding) coûteuses qui introduisent un surcoût important lors de la mise à l'échelle.

Méthodologie
Cet article présente un cadre d'optimisation hybride quantique-classique de bout en bout qui étend l'approche de décomposition de Benders « Multiple Cuts via Multiple Solutions » (MCMS). L'innovation centrale est le remplacement de l'étape de recuit quantique par des implémentations de l'algorithme d'optimisation approximative quantique (QAOA) basées sur des portes logiques.

Le cadre fonctionne comme suit :

1. Décomposition de Benders MCMS : L'algorithme génère plusieurs solutions candidates par itération, résolvant plusieurs sous-problèmes en parallèle pour produire un ensemble de coupes candidates.
2. Sélection de coupes sous forme de QUBO : Pour éviter que le problème maître ne devienne trop coûteux en raison d'un nombre excessif de coupes, un sous-ensemble de coupes informatives est sélectionné. Cela est formulé comme un problème de couverture minimale d'ensembles, qui est ensuite transposé en une instance d'optimisation quadratique non contrainte binaire (QUBO).
3. Intégration de QAOA : Contrairement à l'approche précédente basée sur le recuit quantique, ce cadre résout le QUBO en utilisant QAOA. Le pipeline s'interface avec trois solveurs distincts :
   • Ava de Fermioniq : Un émulateur de circuit par réseau de tenseurs.
   • MPS-JuliQAOA : Un émulateur de réseaux de tenseurs à matrice produit (MPS) open-source construit en Julia.
   • IBM Quantum : Exécution directe sur un matériel quantique supraconducteur (processeur IBM Eagle).
4. Étude de cas : Le cadre est évalué sur le problème de tournées de véhicules (VRP), un problème classique de logistique. L'étude utilise un benchmark standardisé de QOptLib (20 clients, 4 véhicules) et des instances de test aléatoires (5 clients) pour tester la faisabilité du pipeline.

Contributions clés

• Extension basée sur les portes : L'article étend le cadre HQC-MCMS existant du recuit quantique vers le calcul quantique basé sur les portes, permettant l'exécution sur des émulateurs de réseaux de tenseurs ainsi que sur des processeurs quantiques supraconducteurs.
• Implémentation de bout en bout : Les auteurs démontrent avec succès un pipeline entièrement fonctionnel qui intègre des sous-programmes QAOA dans une boucle de décomposition de Benders classique.
• Évaluation empirique : L'étude fournit une analyse comparative des performances du pipeline à travers différents backends de solveurs (Cbc classique, MPS-JuliQAOA, Fermioniq et IBM Quantum) sur des instances de VRP.

Résultats
Les résultats expérimentaux fournissent plusieurs enseignements critiques concernant la viabilité actuelle de l'avantage quantique dans ce contexte spécifique :

• Performance classique : Dans le cadre entièrement classique (utilisant Cbc pour la sélection de coupes), le pipeline trouve avec succès des solutions réalisables pour l'instance VRP de 20 clients, avec un écart d'optimalité qui diminue au fil des itérations. L'approche Multi-Cut (utilisant plus de sous-problèmes) conduit à des solutions réalisables en moins d'itérations.
• Goulots d'étranglement de l'exécution : L'analyse du pipeline classique révèle que l'étape de sélection de coupes ne consomme qu'une faible fraction du temps total d'itération. La majeure partie du temps de calcul est consacrée à la résolution du Problème Maître.
• Performance quantique : Lorsque l'étape de sélection de coupes est remplacée par QAOA (en utilisant MPS-JuliQAOA) sur un problème de test, le temps d'exécution total augmente considérablement par rapport à l'approche classique. L'étude note que MPS-JuliQAOA est beaucoup moins efficace que le solveur classique Cbc pour le problème de couverture minimale d'ensembles à cette échelle.
• Sortie QAOA : Les expériences sur le matériel quantique et les émulateurs montrent que, pour les configurations testées, la majorité des échantillons QAOA aboutissent à des solutions infaisables (c'est-à-dire qu'ils ne forment pas une couverture d'ensemble valide). Bien que des circuits plus profonds ($p=3$) aient produit des échantillons de coût plus optimaux que les circuits plus courts ($p=1$), la performance globale n'a pas surpassé les méthodes classiques.

Signification et affirmations
L'article conclut par une évaluation modeste du cadre actuel. Les auteurs déclarent explicitement que, pour les tailles de problèmes et les configurations testées, l'avantage quantique est peu probable. La raison est double :

1. L'étape de sélection de coupes, qui est la cible de l'accélération quantique, n'est pas un goulot d'étranglement computationnel dans le pipeline MCMS classique actuel ; la résolution du Problème Maître domine le temps d'exécution.
2. Le solveur classique (Cbc) surpasse largement les implémentations QAOA pour les instances spécifiques de couverture minimale d'ensembles générées à cette échelle.

Les auteurs soulignent que, bien que le pipeline soit techniquement fonctionnel et démontre une étape reproductible vers l'optimisation assistée par le quantique, la transposition du problème de couverture d'ensembles en QUBO introduit un surcoût substantiel. Ils soutiennent que les recherches futures doivent se concentrer sur des benchmarks à plus grande échelle où l'étape de sélection de coupes pourrait devenir un goulot d'étranglement plus significatif, et où des unités de traitement quantique (QPU) plus puissantes pourraient potentiellement apporter de la valeur. L'étude sert d'analyse empirique de mise en garde, soulignant que les méthodes quantiques actuelles n'offrent pas encore d'accélération pour cette étape de décomposition spécifique dans des instances pratiques de petite à moyenne échelle.