Solving the traveling salesman problem on $\lceil \log_2 (N-1)! \rceil$ qubits with a variational quantum Kolmogorov--Arnold network: exact-gradient CVaR training and generalization over time-dependent graphs

Imaginez un chauffeur de livraison qui doit visiter une liste de villes exactement une fois et revenir à son point de départ, en cherchant à parcourir la distance la plus courte possible. Il s'agit du problème du voyageur de commerce, un casse-tête classique qui est au cœur de la logistique, de la planification et de la conception de circuits. Si trouver l'itinéraire parfait pour quelques villes est facile, la difficulté explose à mesure que la liste s'allonge ; pour chaque nouvelle ville ajoutée, le nombre d'itinéraires possibles se multiplie si rapidement que même les superordinateurs les plus rapides peuvent rester bloqués en essayant de trouver le meilleur. Pendant des décennies, les scientifiques se sont tournés vers les ordinateurs quantiques, des machines qui utilisent les règles étranges des particules subatomiques pour traiter l'information, afin de résoudre ces énigmes. Cependant, un obstacle majeur est resté : comment traduire le problème dans un langage que l'ordinateur quantique comprenne sans noyer le calcul dans les erreurs et une complexité inutile.

Un chercheur de chez QuantScape Inc. a désormais démontré une nouvelle façon de guider un ordinateur quantique à travers ce labyrinthe, réussissant à trouver l'itinéraire le plus court pour des cartes allant jusqu'à dix villes. Ce travail, qui repose sur des simulations de matériel quantique plutôt que sur des machines physiques, introduit une méthode qui utilise beaucoup moins de bits quantiques — les unités de base de l'information dans un ordinateur quantique — que les approches précédentes. Plus important encore, il montre qu'un ensemble unique d'instructions peut s'adapter aux changements des conditions routières, comme le trafic qui varie au cours de la journée, sans avoir besoin d'être réentraîné pour chaque nouveau scénario. Les résultats suggèrent qu'avec un codage et des techniques d'entraînement appropriés, les ordinateurs quantiques pourraient bientôt s'attaquer à des problèmes d'optimisation actuellement hors de portée, à condition que le matériel continue de s'améliorer.

Le cœur du défi réside dans la manière dont le problème est écrit pour la machine. Les méthodes traditionnelles attribuent un bit quantique distinct à chaque combinaison possible d'une ville et d'une position dans l'itinéraire. Pour une carte de dix villes, cette approche nécessite quatre-vingt-un bits, et force l'ordinateur à vérifier et rejeter constamment les itinéraires invalides, gaspillant ainsi du temps et de l'énergie en pénalités. La nouvelle étude utilise une stratégie différente, inspirée d'un système mathématique appelé code de Lehmer, qui classe essentiellement chaque itinéraire possible par son ordre dans une liste. Cette méthode ne nécessite que dix-neuf bits pour dix villes, une réduction significative. En utilisant ce code compact, chaque état de l'ordinateur quantique représente un itinéraire valide, éliminant ainsi le besoin de vérifications de pénalités. Pour rendre la recherche efficace, les chercheurs ont disposé ces états de sorte que le basculement d'un seul bit dans le code corresponde à un changement logique mineur dans l'itinéraire, permettant à l'ordinateur d'explorer l'espace des solutions de manière fluide.

Pour guider l'ordinateur quantique, les chercheurs ont employé un système hybride appelé réseau de Kolmogorov-Arnold variationnel quantique. Imaginez cela comme un contrôleur intelligent qui observe la carte et l'heure de la journée, puis règle les cadrans du circuit quantique sur les bonnes positions. Au lieu de coder en dur les paramètres pour chaque carte spécifique, ce contrôleur apprend une règle générale : comment ajuster le circuit en fonction des distances entre les villes et de l'heure actuelle. Cela permet au système de gérer des graphes dépendants du temps, où les temps de trajet changent, comme un réseau électrique ou un réseau routier en période d'embouteillages. Le contrôleur a été entraîné avec un objectif spécifique : minimiser le risque de choisir un itinéraire long. Plutôt que de simplement chercher la longueur moyenne absolue, l'entraînement s'est concentré sur les scénarios les plus défavorables au sein des quelques pourcentages les plus probables des résultats, garantissant que le résultat final soit robuste et fiable.

Le processus d'entraînement lui-même était rigoureux, conçu pour éviter le piège courant de rester bloqué dans un minimum local, où l'ordinateur se contente d'une réponse « assez bonne » au lieu de la meilleure. Les chercheurs ont utilisé une stratégie en plusieurs étapes qui commençait par des recherches larges et se resserrait progressivement, combinée à une technique qui bousculait délibérément les paramètres pour échapper aux impasses. Ils ont également utilisé une méthode appelée « basin hopping » (saut de bassin), qui agit comme une légère secousse pour aider le système à sortir des vallées peu profondes dans le paysage de recherche. Testée sur des cartes de quatre à dix villes, incluant des formes symétriques et des réseaux aléatoires irréguliers, cette approche a trouvé l'itinéraire parfait dans chaque cas pour les petites cartes. Pour les cartes de dix villes, nettement plus difficiles, la méthode a trouvé l'itinéraire optimal dans 112 essais sur 120, les échecs restants n'étant qu'à un pour cent de la distance parfaite.

Crucialement, l'étude a écarté plusieurs idées alternatives qui auraient pu sembler prometteuses. Les chercheurs ont testé une approche plus simple utilisant seulement dix bits, un pour chaque ville, pour suivre la position du chauffeur étape par étape. Cette méthode a totalement échoué pour les cartes de six villes ou plus car elle ne pouvait pas représenter les relations complexes entre les arrêts successifs. Ils ont également comparé leurs résultats à un algorithme classique standard connu sous le nom de 2-opt, qui améliore un itinéraire en échangeant deux segments. Bien que le 2-opt soit efficace, le circuit quantique a fourni un bien meilleur point de départ, et la combinaison des deux a surpassé chaque méthode prise isolément. L'étude a confirmé que le succès provenait de la manière spécifique dont le problème était encodé et de l'entraînement sophistiqué du contrôleur, et non seulement de la puissance du circuit quantique lui-même.

Les conclusions soulignent également l'efficacité de la méthode concernant la mesure. Dans un véritable ordinateur quantique, lire la réponse nécessite de répéter le processus de nombreuses fois pour obtenir un signal clair. Les simulations ont montré que même avec seulement cent lectures, le système pouvait identifier de manière fiable le meilleur itinéraire. Cela suggère que lorsque des ordinateurs quantiques physiques dotés de suffisamment de bits seront disponibles, cette méthode pourra livrer des résultats rapidement sans nécessiter des millions de répétitions. Les chercheurs ont noté que, bien que le présent travail ait été réalisé sur un ordinateur classique simulant un comportement quantique, les techniques sont conçues pour fonctionner sur du matériel réel. Les prochaines étapes consistent à tester le système dans les conditions bruitées des machines réelles et à le mettre à l'échelle pour des cartes plus grandes où le nombre d'itinéraires possibles est trop vaste pour être vérifié manuellement.

Ce travail représente une étape importante pour rendre l'optimisation quantique pratique. En résolvant le problème de l'encodage et en créant un contrôleur qui se généralise à travers différentes cartes et différents moments, les chercheurs ont montré une voie pour que les machines puissent résoudre des problèmes de routage complexes efficacement. La capacité de gérer des changements dépendants du temps avec un ensemble unique de paramètres est particulièrement prometteuse pour les applications du monde réel où les conditions ne sont jamais statiques. Bien que le voyage vers un optimiseur quantique pleinement fonctionnel soit toujours en cours, cette étude fournit un plan clair sur la manière d'entraîner ces machines pour trouver le chemin le plus court à travers un monde complexe.