⚛️ quantum physics

Solving The Travelling Salesman Problem Using A Single Qubit

Cet article présente un algorithme quantique économe en ressources qui résout le problème du voyageur de commerce pour jusqu'à neuf villes en utilisant un seul qubit en exploitant le parallélisme quantique et des méthodes de contrôle optimal basées sur une approche de Brachistochrone quantique, démontrant une précision supérieure et un potentiel d'accélération polynomiale par rapport aux méthodes quantiques et classiques existantes.

Auteurs originaux : Kapil Goswami, Gagan Anekonda Veereshi, Peter Schmelcher, Rick Mukherjee

Publié 2026-01-28

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Kapil Goswami, Gagan Anekonda Veereshi, Peter Schmelcher, Rick Mukherjee

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 grand problème : Le voyageur fatigué

Imaginez que vous êtes un vendeur itinérant avec une carte de villes. Votre travail est de visiter chaque ville exactement une fois et de revenir à la maison, mais vous voulez le faire en parcourant la distance la plus courte possible.

C'est le célèbre Problème du Voyageur de Commerce (TSP). C'est un casse-tête classique qui devient incroyablement difficile très rapidement. Si vous avez 4 villes, c'est facile. Si vous en avez 10, c'est gérable. Mais si vous en avez 20, le nombre de routes possibles est si immense que même les superordinateurs les plus rapides du monde mettraient plus de temps que l'âge de l'univers pour toutes les vérifier une par une.

L'ancienne méthode quantique : L'approche des « trop nombreuses clés »

Habituellement, quand les scientifiques essaient de résoudre cela sur un ordinateur quantique, ils traitent le problème comme une serrure géante avec de nombreux cylindres. Ils ont besoin d'un « cylindre » (un qubit) pour chaque ville et chaque connexion possible.

Le Problème : Pour résoudre un problème de seulement 9 ou 10 villes, les méthodes quantiques existantes nécessitent des centaines, voire des milliers de qubits.
La Réalité : Les ordinateurs quantiques actuels sont bruyants et fragiles. Ils ont du mal à faire fonctionner autant de qubits ensemble, et ils échouent souvent à trouver la réponse parfaite, même pour de petites cartes.

La nouvelle idée : Le qubit « Unicité »

Cet article propose une nouvelle façon radicale de résoudre le TSP en utilisant un seul qubit (l'unité de base de l'information quantique). Considérez ce qubit unique non pas comme un petit interrupteur, mais comme une toupie magique qui peut pointer dans n'importe quelle direction dans l'espace 3D.

Voici comment ils font fonctionner cela, étape par étape :

1. La carte est un globe (La sphère de Bloch)

Au lieu de dessiner les villes sur une feuille de papier plate, les auteurs les projettent sur la surface d'une sphère (comme un globe terrestre).

Les Villes : Les villes « réelles » sont placées le long de l'équateur de ce globe.
Les Distances : La distance entre deux villes ne se mesure pas en kilomètres, mais par la distance qu'il faut faire tourner la toupie pour passer d'un point de la ville à un autre.
L'Objectif : Le vendeur doit faire tourner la toupie de ville en ville, en visitant chaque point de l'équateur une seule fois, et en revenant à la maison, tout en minimisant l'effort de « rotation » total.

2. L'autoroute de la superposition

Dans l'ancienne méthode, vous vérifiez la Route A, puis la Route B, puis la Route C, l'une après l'autre.
Dans cette nouvelle méthode, les auteurs utilisent la superposition quantique. Imaginez que la toupie est un voyageur magique capable d'être à plusieurs endroits à la fois.

Au lieu de suivre un seul chemin, la « toupie » explore simultanément chaque route possible.
C'est comme envoyer mille explorateurs sur mille routes différentes simultanément, mais ils sont tous le même explorateur, existant simplement dans une « superposition » de tous les chemins.

3. Le raccourci « Brachistochrone »

L'article utilise un concept de la physique appelé le problème de la Brachistochrone. Historiquement, celui-ci demande : « Quel est le chemin le plus rapide pour qu'une balle roule entre deux points ? »

Les auteurs ont transformé le TSP en une version de ce problème. Ils traitent la recherche d'itinéraire comme une course contre la montre.
Ils utilisent une technique appelée Contrôle Optimal (pensez à un pilote automatique très intelligent) pour pousser et faire pivoter doucement le qubit unique.
Le pilote automatique ajuste la « rotation » de sorte que les chemins trop longs s'annulent entre eux (comme des casques à réduction de bruit), tandis que le chemin le plus court est amplifié et se distingue.

4. La vérification finale

Après que le qubit a « voyagé » sur tous les itinéraires à la fois, les scientifiques mesurent la position finale de la toupie.

Ils ne regardent pas chaque chemin individuellement. Ils regardent l'état final du voyage.
En analysant l'état final, ils peuvent remonter en arrière pour reconstruire la route gagnante.
C'est comme regarder un magicien réaliser un tour où il mélange un jeu de cartes, et en regardant la dernière carte, vous pouvez deviner l'ordre exact de tout le paquet.

Les Résultats : Qu'ont-ils trouvé ?

L'équipe a lancé des simulations informatiques pour tester cette méthode du « Qubit Unique ».

Le Test : Ils ont résolu des puzzles TSP de 4 à 9 villes.
Le Succès : Pour plus de 90 % des problèmes, leur méthode a trouvé la route parfaite, la plus courte.
La Sécurité : Dans les rares cas où ils n'ont pas obtenu la réponse parfaite, ils ont tout de même obtenu une très bonne approximation (environ 90 % de la meilleure solution possible).
L'Efficacité : Ils ont accompli tout cela en utilisant un seul qubit, alors que d'autres méthodes auraient nécessité des dizaines ou des centaines de qubits.

L'essentiel à retenir

Cet article ne prétend pas résoudre le TSP pour un million de villes dès demain. Il prouve plutôt un concept puissant : Vous n'avez pas besoin d'un ordinateur quantique massif pour résoudre des problèmes de routage complexes.

En traitant le problème comme un puzzle géométrique sur une seule sphère tournante et en utilisant le pouvoir d'« être à plusieurs endroits à la fois », ils ont montré qu'un seul qubit peut naviguer efficacement dans des labyrinthes complexes. C'est une nouvelle façon de penser l'optimisation quantique, plus légère en ressources, qui pourrait éventuellement être construite sur n'importe quelle plateforme quantique capable de faire tourner un qubit avec précision.

Résumé Technique : Résolution du Problème du Voyageur de Commerce à l'aide d'un Seul Qubit

Énoncé du Problème
Le Problème du Voyageur de Commerce (TSP - Travelling Salesman Problem) est un problème d'optimisation combinatoire fondamental de classe NP-difficile, qui nécessite l'identification de l'itinéraire le plus court permettant de visiter un ensemble de villes exactement une fois et de revenir à l'origine. Bien que des algorithmes classiques existent, les solutions exactes augmentent de manière exponentielle avec le nombre de villes, et les méthodes heuristiques ne garantissent pas l'optimalité. Les approches quantiques existantes, telles que celles utilisant l'Optimisation Binaire Non Contrainte Quadratique (QUBO) mappée sur des Hamiltoniens d'Ising ou des circuits d'estimation de phase, sont gourmandes en ressources. Elles nécessitent généralement un grand nombre de qubits (par exemple, des milliers de qubits physiques pour un problème de 10 villes) et souffrent souvent de faibles probabilités de succès sur le matériel bruyant actuel.

Méthodologie
Les auteurs proposent un algorithme qui projette un TSP arbitraire sur un seul qubit, en exploitant le principe du parallélisme quantique plutôt que celui de l'intrication. La méthodologie centrale comprend trois étapes principales :

Mappage vers un Problème de Brachistochrone Discret :
Le TSP est d'abord reformulé comme un problème de Brachistochrone discret fini. Dans cette analogie classique, les villes sont représentées comme des points sur un plan 2D, et les itinéraires sont des fonctions linéaires par morceaux. L'objectif est de minimiser un fonctionnel de temps $Q$ , qui correspond à la distance totale parcourue. Le problème est contraint de sorte que le chemin doive revenir à la ville initiale, ce qui est encodé par un segment linéaire supplémentaire vers un point final $F$ .
Encodage sur la Sphère de Bloch :
Le problème de Brachistochrone discret est mappé sur la géométrie de la sphère de Bloch d'un qubit unique.

Représentation d'État : Les villes ( $c_i$ ) sont représentées par des états quantiques $|P_{ii}\rangle$ situés sur l'équateur de la sphère de Bloch.
Encodage de la Distance : Les distances relatives entre les villes sont encodées sous forme de distances géométriques (géodésiques) sur la sphère. Les états intermédiaires $|P_{ij}\rangle$ sont placés sur des courbes géodésiques reliant les états équatoriaux à un pôle $P_0$ . La distance angulaire entre les états correspond à la distance euclidienne entre les villes.
Traversée : Le mouvement entre les villes est réalisé via des opérateurs de rotation ( $U^u$ et $U^d$ ). Une « étape » de la ville $i$ vers la ville $j$ implique une rotation « vers le haut » de l'équateur vers un état intermédiaire $|P_{ij}\rangle$ (plus proche du pôle), suivie d'une rotation « vers le bas » vers l'état équatorial $|P_{jj}\rangle$ .

Optimisation Quantique via la Superposition :
Contrairement à une approche par force brute qui parcourt les chemins séquentiellement, l'algorithme proposé utilise la superposition quantique pour traverser plusieurs chemins simultanément.

Création de la Superposition : Le système est initialisé dans un état correspondant à la ville de départ. Une série d'opérateurs de rotation ajustables crée un état de superposition à chaque couche du diagramme de routage, explorant ainsi tous les chemins valides et invalides simultanément.
Optimisation : L'algorithme emploie des méthodes de contrôle optimal, spécifiquement l'Approximation Stochastique par Perturbation Simultanée (SPSA), pour ajuster les opérateurs de rotation.
Fonction d'Objectif : Bien qu'une approche quantique par force brute pourrait minimiser un fonctionnel de temps $T$ , l'approche basée sur la superposition minimise la fonction de coût classique $D$ (distance totale). Ceci est nécessaire car la superposition inclut des chemins « classiquement interdits » qui ne forment pas de cycles hamiltoniens valides. L'optimisation cherche à maximiser la population du cycle hamiltonien valide dans l'état final.
Mesure et Post-traitement : L'algorithme se conclut par une mesure projective de l'état pénultième. Par la tomographie d'état quantique, la distribution de population est analysée pour identifier le chemin dominant, qui correspond à l'itinéraire optimal du TSP.

Résultats Clés
Les auteurs présentent des simulations numériques résolvant des instances de TSP de 4 à 9 villes en utilisant un seul qubit.

Précision : Pour les tailles de problèmes testées, l'algorithme a obtenu des solutions exactes (ratio d'approximation $\sim 1$ ) pour plus de 90 % des instances de problèmes.
Approximation : Dans les cas où des solutions exactes n'ont pas été trouvées, l'algorithme a atteint des ratios d'approximation élevés ( $\sim 0,90$ ).
Efficacité des Ressources : La méthode ne nécessite qu'un seul qubit, ce qui contraste fortement avec les algorithmes quantiques existants qui nécessitent des centaines ou des milliers de qubits pour des tailles de problèmes similaires.
Agnosticisme de Plateforme : L'algorithme est conçu pour être implémentable sur n'importe quelle plateforme quantique capable de rotations de qubits arbitraires de haute fidélité et de tomographie d'état, incluant les qubits supraconducteurs, les ions piégés, les centres azote-lacune (NV centers) et les atomes de Rydberg.

Signification et Revendications
L'article affirme que cette approche offre une alternative plus efficace en termes de ressources et plus précise que les algorithmes quantiques existants pour les instances de TSP de petite à moyenne taille. En utilisant le principe de superposition sur un seul qubit, la méthode contourne le besoin de grande intrication et de comptes de qubits élevés, répondant ainsi à un goulot d'étranglement majeur du matériel quantique actuel.

Les auteurs discutent d'un potentiel gain de vitesse polynomial par rapport aux algorithmes classiques, suggérant que le parallélisme quantique inhérent à la superposition des chemins pourrait fournir un avantage pratique tant en temps qu'en précision. Ce travail positionne le TSP non seulement comme un problème de routage, mais comme un cas spécifique de problème de Brachistochrone contraint soluble via le contrôle quantique, ouvrant une voie vers une optimisation quantique scalable sur des dispositaux de l'ère NISQ (Near-term Intermediate-Scale Quantum).