Publié le 29 décembre 2025 20h37:00. Des chercheurs de Quantinuum ont développé de nouveaux algorithmes d’optimisation combinatoire, surpassant les méthodes classiques et variationnelles existantes, et ouvrant la voie à des avancées significatives dans la résolution de problèmes complexes nécessitant une puissance de calcul importante.
- Les algorithmes, basés sur des états de produits et de produits matriciels, s’inspirent de la technique de recherche locale itérée (ILS).
- Ils ont démontré une performance supérieure sur des problèmes de coupe maximale impliquant jusqu’à 50 000 variables.
- Une version parallèle de l’algorithme, nommée recherche globale itérative d’inspiration quantique, offre un temps d’exécution quasi indépendant de la taille du problème grâce à l’utilisation de GPU.
L’optimisation combinatoire, qui consiste à trouver la meilleure solution parmi un grand nombre de possibilités, représente un défi majeur pour l’informatique, tant classique que quantique. Guillermo Preisser, Conor Mc Keever et Michael Lubasch, de Quantinuum, ont mis au point une approche novatrice pour relever ce défi. Leur travail combine la minimisation de l’énergie variationnelle avec une technique de recherche locale itérée, donnant naissance à des algorithmes d’inspiration quantique particulièrement performants.
Les chercheurs ont comparé ces nouveaux algorithmes sur des problèmes de coupe maximale, un type de problème d’optimisation combinatoire couramment utilisé comme banc d’essai. Les résultats ont démontré que les algorithmes développés surpassent non seulement les méthodes traditionnelles, mais également la recherche locale itérée classique et d’autres solveurs variationnels d’inspiration quantique. L’équipe a notamment conçu une alternative parallèle à QiILS, baptisée recherche globale itérative d’inspiration quantique, qui exploite les mises à jour de gradient global pour une parallélisation efficace. Des tests menés avec des calculs parallèles basés sur des GPU ont révélé que cette approche permet d’obtenir un temps d’exécution qui évolue très peu avec la taille du problème, ce qui représente un gain de temps considérable pour les instances de grande envergure.
Les performances des algorithmes ont été évaluées à l’aide du rapport d’approximation, une mesure de la qualité de la solution obtenue. Les expériences ont systématiquement montré que l’algorithme développé par l’équipe de Quantinuum fournit des résultats supérieurs sur un graphique de référence. L’étude souligne également l’importance d’une sélection minutieuse des paramètres clés pour maximiser le taux d’amélioration des performances.
Cette recherche met en lumière le potentiel de la combinaison de l’intrication quantique et du hasard pour naviguer efficacement dans l’espace des solutions de problèmes d’optimisation complexes. Une étude récente explore d’ailleurs le lien entre la gravité et l’intrication quantique.