L'optimisation combinatoire imprègne la science et l'ingénierie : de la planification d'itinéraires à la répartition des ressources. Beaucoup de ces problèmes sont équivalents à la recherche de l'état fondamental du modèle d'Ising, ce qui relève de la classe des problèmes NP-difficiles. Les heuristiques classiques, comme le recuit simulé, restent souvent bloquées dans des minima locaux à cause du paysage énergétique accidenté. Les approches quantiques, notamment QAOA, promettent une accélération, mais souffrent de problèmes d'apprentissage et de profondeur de circuit limitée sur le matériel actuel. Ce travail s'inscrit dans une série de tentatives récentes pour utiliser les processeurs quantiques intermédiaires bruyants (NISQ) pour des problèmes pratiques : des recherches voisines étudient les algorithmes quantiques, la correction d'erreurs et l'information quantique. La différence de ce travail réside dans le schéma hybride concret, où la partie quantique ne propose que des « sauts » entre les bassins, tandis que toute l'optimisation fine reste classique.
L'algorithme Qjump fonctionne de manière itérative. À partir d'une solution courante (une chaîne de bits), le circuit quantique génère un ensemble de candidats en « sautant » dans les bassins d'énergie voisins. Le circuit se compose d'une couche d'encodage, de L couches d'opérateurs de coût et de mélange (inspirées de QAOA) et de mesures. Les paramètres du circuit ne sont pas optimisés variationnellement, mais proviennent de valeurs précalculées pour un QAOA profond, ce qui élimine le problème des plateaux stériles. Après l'échantillonnage quantique, l'ordinateur classique effectue une recherche locale (descente gloutonne) pour chaque candidat et choisit la meilleure solution. Les expériences ont été menées sur un processeur supraconducteur de 104 qubits avec une précision médiane des portes à deux qubits de 99,5 %. Pour la comparaison, on a utilisé un recuit simulé classique hautement optimisé (SA) sur un CPU monocœur.
Sur 20 instances difficiles spécialement sélectionnées du problème d'Ising avec 104 qubits, Qjump a trouvé en moyenne le minimum global 2,23 fois plus souvent que SA, en un temps fixé. De plus, l'échantillonneur quantique montrait une probabilité plus élevée d'atteindre la région du minimum global par rapport à un échantillonnage aléatoire classique avec la même proportion de bits retournés. En se basant sur des hypothèses concernant le futur matériel quantique (fréquence d'échantillonnage de 0,4 MHz, contrôle rapide via FPGA), le temps jusqu'à la solution (TTS) a été estimé : Qjump a surpassé SA sur CPU monocœur de 2,34 fois. Pour des systèmes plus petits (60 et 84 qubits), l'avantage était moindre (0,98 et 1,56 fois respectivement), ce qui indique une amélioration avec la taille du problème. QAOA avec recherche locale s'est avéré presque inefficace pour ces problèmes.
Ce travail montre que les schémas hybrides, où le processeur quantique n'est utilisé que pour « sauter » sur le paysage, tandis que le classique effectue l'optimisation fine, peuvent être une voie pratique vers l'avantage quantique sur les dispositifs NISQ. Contrairement aux travaux voisins qui se concentrent sur des algorithmes purement quantiques ou la correction d'erreurs, ici est proposé un mécanisme concret de division du travail, réduisant les exigences sur la profondeur des circuits et la qualité des qubits. Cela élargit l'applicabilité des processeurs quantiques existants pour des problèmes d'optimisation dès aujourd'hui.
La prochaine étape naturelle est le passage à l'échelle avec des milliers de qubits et l'amélioration des métriques des qubits. Il serait également intéressant d'explorer les paramètres optimaux de l'échantillonneur et la structure du circuit, ainsi que l'effet du bruit des portes et des mesures. Potentiellement, Qjump pourrait être combiné avec d'autres heuristiques classiques (recherche tabou, méthode de branchement et de coupe) ou utilisé comme module dans un ensemble d'algorithmes.
Les résultats pourraient influencer les domaines où des problèmes NP-difficiles doivent être résolus : logistique, finance, science des matériaux, apprentissage automatique. L'approche hybride pourrait être adaptée à d'autres plateformes quantiques.
Mener des expériences sur des systèmes avec des milliers de qubits et des mesures de précision de portes améliorées. Étudier la mise à l'échelle de la complexité temporelle de Qjump avec la taille du problème.
Dans le domaine du calcul quantique, la question reste ouverte de savoir si les dispositifs quantiques intermédiaires bruyants peuvent offrir un avantage pratique par rapport aux algorithmes classiques pour les problèmes d'optimisation. Ce travail contribue en démontrant un algorithme hybride concret et une preuve expérimentale d'avantage sur 104 qubits, mais une preuve rigoureuse de l'accélération quantique nécessite des recherches supplémentaires.
Cette section s'adresse à l'auteur du travail et à ses collègues. Les travaux voisins ont été trouvés par une recherche sémantique dans notre archive, et non par correspondance de mots. Nous n'évaluons pas : nous montrons le champ autour.
Ce que fait ce travail
L'article propose un algorithme hybride quantique-classique nommé Qjump, qui utilise un échantillonneur quantique pour générer des candidats dans différents bassins d'énergie, et une recherche locale classique pour la descente. Sur un processeur à 104 qubits, l'algorithme a trouvé plus souvent le minimum global que le recuit simulé classique, et a montré une accélération extrapolée de 2,34 fois en temps jusqu'à la solution.
Où est sa force
Le point fort est le schéma hybride concret, où la partie quantique ne s'occupe que des « sauts » entre les bassins, tandis que l'optimisation fine reste classique, ce qui permet d'éviter les problèmes d'optimisation variationnelle et d'utiliser des paramètres de circuit fixes.
Vers où avancer
À essayer
Travaux voisins dans notre archive
L'archive est vide autour de ce travail : l'analyse la plus proche n'est qu'à 0.58, contre 0,64 d'ordinaire. Il semble qu'on ait peu foré à côté.
Pour sélectionner les instances difficiles, les chercheurs ont généré 4000 configurations aléatoires de connexions et de champs, puis n'ont gardé que les 20 sur lesquelles le recuit simulé classique fonctionnait le moins bien. Cela garantit que la comparaison était équitable : l'algorithme quantique a été testé sur les cas les plus difficiles.