Un algorithme heuristique variationnel économe en qubits pour MaxCut

Pourquoi les puces quantiques minuscules comptent pour de grands casse-tête

De nombreuses tâches réelles — de la disposition des circuits informatiques à la modélisation des matériaux — se ramènent à séparer un réseau en deux groupes tout en coupant autant de connexions que possible entre eux. Ce problème, connu sous le nom de MaxCut, est notoirement difficile pour les ordinateurs classiques. L'article présente une nouvelle méthode inspirée du quantique capable de traiter des réseaux étonnamment grands en n'utilisant que quelques bits quantiques (qubits), offrant une nouvelle manière de tester et d'améliorer à la fois les outils d'optimisation quantiques et classiques.

Couper un réseau en deux moitiés utiles

MaxCut pose une question au son simple : si vous avez un ensemble de points (nœuds) reliés par des lignes (arêtes), comment colorer chaque nœud, par exemple bleu ou blanc, de façon à ce que le maximum de lignes relient des nœuds de couleurs différentes ? Cette meilleure séparation possible est précieuse dans des domaines comme le design de circuits et la physique statistique, mais elle est très difficile à trouver exactement lorsque le réseau est grand. Une approche classique largement utilisée, l'algorithme de Goemans–Williamson (GW), effectue une relaxation astucieuse du problème et garantit de trouver une coupe d'au moins environ 88 % de la valeur optimale. L'informatique quantique promet de nouvelles façons d'attaquer ces problèmes, mais les dispositifs actuels sont bruyants et de taille limitée, ce qui rend difficile l'exécution de circuits profonds et de grande ampleur.

Résoudre de grands graphes avec seulement quelques qubits

Les approches quantiques standards telles que l'algorithme quantique d'approximation optimisée (QAOA) nécessitent un qubit par nœud du réseau : un graphe de 1 000 nœuds exigerait donc 1 000 qubits, bien au-delà des machines actuelles. La nouvelle méthode, appelée Qubit-Efficient MaxCut (QEMC), renverse cette échelle : elle n'utilise qu'environ le logarithme du nombre de nœuds, ce qui signifie que 11 qubits peuvent encoder des informations sur plus de 2 000 nœuds. Plutôt que d'associer chaque qubit à un nœud unique, QEMC exploite l'état quantique global comme un espace d'adressage compact et associe différents nœuds à différents états de base de ce petit registre. Cette épargne en qubits maintient les circuits peu profonds et plus faciles à exécuter sur du matériel bruyant, tout en représentant des graphes très grands.

Colorer les nœuds par probabilité plutôt que par états fixes

L'innovation clé réside dans la façon dont QEMC encode la « couleur » de chaque nœud. Plutôt que de forcer chaque nœud à être exactement bleu ou blanc dans un unique état quantique, la méthode laisse la couleur de chaque nœud être déduite de la probabilité avec laquelle son état de base est observé lors de la mesure. Un nœud dont l'état de base apparaît avec une faible probabilité est traité comme une couleur ; un nœud avec une probabilité plus élevée est traité comme l'autre. Une valeur-seuil sépare les deux régimes. Cela signifie que de nombreux états quantiques différents correspondent essentiellement au même partitionnement du graphe. La fonction de coût que QEMC minimise est construite de sorte que les nœuds connectés sont encouragés à se situer de part et d'autre de ce seuil de probabilité, ce qui tend à augmenter le nombre d'arêtes traversant entre les deux groupes de couleurs et à améliorer ainsi la coupe.

Tester les performances sur des machines réelles et simulées

Les auteurs testent QEMC sur deux fronts : des processeurs quantiques réels et des simulations classiques des circuits quantiques. Sur de petits graphes réguliers allant jusqu'à 32 nœuds (en n'utilisant que 2 à 5 qubits), QEMC exécuté sur du matériel supraconducteur IBM trouve des coupes qui égalent ou approchent les meilleures réponses possibles obtenues par recherche exhaustive, surpassant nettement le hasard et des études quantiques antérieures basées sur QAOA. Dans des simulations sans bruit, QEMC atteint systématiquement plus de 97 % de la coupe optimale pour ces petits graphes. La puissance de l'encodage devient encore plus évidente pour des graphes plus grands : pour des graphes 9-réguliers allant jusqu'à 2 048 nœuds, les simulations classiques de QEMC surpassent encore GW tant sur la coupe moyenne que sur la meilleure coupe de quelques pourcents, et des avantages similaires sont observés sur des graphes aléatoires de 128 nœuds avec différentes densités.

Vitesse, limites et promesse inspirée du quantique

Malgré son succès, QEMC n'apporte pas encore de vitesse quantique formelle. Parce qu'il n'utilise qu'environ log N qubits, la simulation classique de ses circuits évolue aussi approximativement linéairement avec le nombre de nœuds, et le temps nécessaire pour évaluer la fonction de coût croît avec le nombre d'arêtes. Des études empiriques suggèrent que le temps total pour atteindre les performances du niveau GW croît approximativement de façon quadratique avec la taille du graphe, ce qui reste à la portée pratique pour de nombreux problèmes. Cela signifie que QEMC, dans sa forme actuelle, sert davantage d'heuristique puissante inspirée du quantique que de preuve d'un avantage quantique.

Ce que ce travail signifie pour l'avenir

Pour un non-spécialiste, le message principal est que de petits dispositifs quantiques bruyants peuvent rester scientifiquement utiles si l'on conçoit des algorithmes qui tirent parti de leurs forces. En encodant les couleurs des nœuds dans des plages de probabilité flexibles plutôt que dans des valeurs binaires rigides, QEMC utilise très peu de qubits pour s'attaquer à des problèmes de réseau très vastes et tolère naturellement le bruit matériel. La méthode établit une nouvelle référence pour tester les algorithmes d'optimisation quantique et fournit aussi un algorithme classique pratique basé sur les mêmes idées. Plus généralement, elle montre comment repenser l'encodage de l'information — plutôt que de se contenter de fabriquer des machines plus grandes — peut ouvrir des voies prometteuses pour résoudre des problèmes computationnels difficiles.

Citation: Tene-Cohen, Y., Kelman, T., Lev, O. et al. A Variational Qubit-Efficient MaxCut Heuristic Algorithm. npj Quantum Inf 12, 50 (2026). https://doi.org/10.1038/s41534-026-01186-2

Mots-clés: MaxCut, optimisation quantique, algorithmes variationnels, partition de graphe, informatique inspirée du quantique