Quantum-Assisted Vehicle Routing: Realizing QAOA-based Approach on Gate-Based Quantum Computer

Résumé Technique : Optimisation de Tournées de Véhicules Assistée par le Quantique via QAOA sur Matériel à Portes Logiques

Définition du Problème
Le problème de tournées de véhicules (VRP - Vehicle Routing Problem) est un défi d'optimisation combinatoire fondamental de classe NP-difficile, central pour la logistique et le transport, visant à minimiser les coûts (distance, temps, carburant) tout en respectant des contraintes telles que la visite des clients, la capacité des véhicules et la continuité des itinéraires. Les algorithmes classiques peinent à trouver des solutions optimales, même pour des instances de taille modeste, en raison d'une croissance exponentielle. Ce travail aborde le défi de la transposition du VRP sur des ordinateurs quantiques à portes logiques dans le régime NISQ (Noisy Intermediate-Scale Quantum), en se concentrant spécifiquement sur les limitations imposées par la profondeur des circuits, la connectivité des qubits et le bruit matériel.

Méthodologie
Les auteurs proposent un cadre ancré dans le matériel, intégrant l'algorithme d'optimisation approximative quantique (QAOA) avec une formulation basée sur les liens du VRP. La méthodologie se déroule selon les étapes suivantes :

1. Formulation du Problème : Le VRP est modélisé à l'aide de variables d'arêtes directionnelles ($x_{i,j}$) représentant si un véhicule emprunte un lien entre les nœuds $i$ et $j$. Contrairement aux formulations basées sur l'expansion temporelle ou l'ordre des routes, cette approche évite les variables de séquençage explicites.
2. Encodage des Contraintes : Les contraintes critiques — conservation du flux (chaque client visité exactement une fois), comptes d'entrée/sortie au dépôt et élimination des sous-tours — sont encodées directement dans l'Hamiltonien de coût ($H_C$) via des termes de pénalité. Cela transforme le problème contraint en un problème d'optimisation binaire quadratique non contrainte (QUBO).
3. Cartographie de l'Hamiltonien : Le QUBO est mappé sur un Hamiltonien d'Ising adapté au QAOA. L'Hamiltonien de coût se compose de termes Pauli-Z ($Z_i$) pour les coûts linéaires et d'interactions Pauli-Z ($Z_i Z_j$) pour les pénalités quadratiques. Un Hamiltonien de mélange standard ($H_M = \sum X_i$) est utilisé pour explorer l'espace des solutions.
4. Implémentation du Circuit : L'algorithme est implémenté sur l'IBM Quantum System One (Eagle r3, 127 qubits). Le flux de travail comprend :
   • Transpilation : Cartographie des qubits logiques vers la topologie de réseau "heavy-hex", introduisant les portes SWAP nécessaires.
   • Atténuation des Erreurs : Application du découplage dynamique (pour préserver la cohérence des qubits inactifs) et du "Pauli twirling" (pour convertir les canaux de bruit en signatures spécifiques).
   • Optimisation Hybride : Un optimiseur classique (COBYQA) ajuste de manière itérative les paramètres variationnels ($\gamma, \beta$) pour minimiser le coût attendu $\langle \psi | H_C | \psi \rangle$.
5. Paramètres Expérimentaux : L'étude examine l'impact de la mise à l'échelle des pénalités (notamment en fixant les coefficients de pénalité à deux fois la somme des poids des arêtes) et de la normalisation des coefficients (bornant les magnitudes des termes de Pauli à un) sur la faisabilité des solutions.

Contributions Clés

• Formulation Basée sur les Arêtes Directionnelles : Les auteurs développent une formulation qui intègre la conservation du flux et l'élimination des sous-tours directement dans l'Hamiltonien de coût. Cette approche évite le surcoût de qubits des formulations d'expansion temporelle et la complexité factorielle des formulations d'ordre de route, ce qui la rend plus adaptée aux dispositifs actuels.
• Pipeline Matériel Complet : Le travail exécute l'intégralité du pipeline — de l'encodage du problème et du mappage d'Ising à la synthèse du circuit, la transpilation et l'exécution — sur du matériel quantique réel, plutôt que de s'appuyer uniquement sur des simulations idéalisées.
• Analyse Empirique des Goulots d'Étranglement : L'étude évalue quantitativement comment les formulations de VRP impactent le nombre de qubits et la profondeur des portes à deux qubits après transpilation, identifiant la profondeur du circuit comme le principal goulot d'étranglement pour le routage contraint sur les architectures supraconductrices actuelles.
• Aperçus sur la Sensibilité des Paramètres : La recherche démontre que la faisabilité des solutions dépend de manière critique de la sélection des paramètres de pénalité et de la normalisation des coefficients de l'Hamiltonien. Plus précisément, la normalisation améliore considérablement l'échantillonnage des solutions faisables pour les instances plus grandes (4 et 5 nœuds) où les approches non normalisées échouent.

Résultats

• Succès à Petite Échelle : Pour une instance de 3 nœuds et 2 véhicules, le QAOA a identifié avec succès la solution optimale (chaîne de bits 111010) avec une probabilité élevée, respectant toutes les contraintes, y compris l'élimination des sous-tours.
• Défis de Scalabilité : À mesure que la taille du problème augmentait (par exemple, instances de 4 et 5 nœuds), le nombre de portes requises croissait exponentiellement. Un problème à 4 nœuds nécessitait un circuit de 14 qubits avec plus de 3 000 portes, prenant plus de deux heures d'exécution, mais produisant des solutions infaisables. Un problème à 5 nœuds nécessitait un circuit de 30 qubits avec environ 30 000 portes.
• Impact de la Normalisation : Sans la normalisation des coefficients, l'algorithme n'a pas réussi à identifier de manière cohérente les routes optimales dans la région de haute probabilité pour les instances de 4 et 5 nœuds. Avec la normalisation et un multiplicateur de pénalité de 1,5–2,0, le ratio de faisabilité des 1 000 chaînes de bits échantillonnées s'est nettement amélioré.
• Limitations Matérielles : L'étude confirme que le bruit matériel actuel et les temps de cohérence limités empêchent l'exécution des circuits QAOA profonds requis pour les instances de VRP plus larges. Les 10 états échantillonnés les plus probables pour le problème à 4 nœuds étaient tous infaisables sans un réglage minutieux des paramètres.

Signification et Revendications
L'article revendique sa pertinence non pas comme une démonstration d'avantage quantique sur les solveurs classiques pour le VRP à grande échelle, mais comme une évaluation pratique exécutée sur matériel qui clarifie les limitations actuelles de l'ère NISQ. Les auteurs soutiennent que bien que le QAOA puisse théoriquement résoudre le VRP, la croissance rapide de la complexité des circuits (spécifiquement la profondeur des portes à deux qubits) et l'accumulation de bruit restreignent actuellement son application à de très petites instances.

La valeur primaire de l'étude réside dans la fourniture d'informations de conception concrètes pour l'optimisation quantique future :

1. Choix de la Formulation : Les formulations basées sur les arêtes sont actuellement plus réalisables que les encodages d'expansion temporelle ou d'ordre de route sur le matériel disponible, en raison de leurs exigences moindres en qubits et en portes.
2. Heuristiques de Paramètres : La normalisation des coefficients et une mise à l'échelle spécifique des pénalités (environ 2x la somme des poids des arêtes) sont essentielles pour récupérer des solutions faisables sur des instances plus grandes.
3. Direction Méthodologique : Le travail souligne que l'avancement de l'optimisation quantique pour le VRP nécessite non seulement des améliorations algorithmiques, mais aussi des avancées matérielles (nombre de qubits plus élevé, taux d'erreur plus faible) et des stratégies hybrides (par exemple, transfert d'apprentissage de paramètres, circuits dynamiques) pour atténuer les contraintes de bruit et de profondeur.

Les auteurs concluent que bien que la scalabilité reste contrainte, ce travail établit une voie pratique pour l'implémentation du VRP sur le matériel quantique et identifie les directions méthodologiques spécifiques nécessaires aux progrès futurs de l'optimisation quantique à court terme.