La résolution de problèmes complexes de combinaison et d’optimisation représente un enjeu majeur dans de nombreux domaines économiques et scientifiques. Une équipe berlinoise, dirigée par le physicien théoricien Prof. Dr. Jens Eisert de la Freie Universität Berlin et du HZB, vient de démontrer l’efficacité supérieure des ordinateurs quantiques dans la résolution d’une classe spécifique de ces problèmes, par rapport aux méthodes conventionnelles.
Le problème du voyageur de commerce est un cas d’école en matière d’optimisation combinatoire. Il consiste à déterminer le chemin le plus court permettant à un voyageur de visiter une série de villes avant de revenir à son point de départ. Si le concept est aisément compréhensible, la complexité du problème s’accroît de manière exponentielle avec l’ajout de villes, rendant les calculs traditionnels extrêmement gourmands en temps.
Ce problème emblématique représente toute une catégorie de défis d’optimisation qui revêtent une importance économique considérable, qu’il s’agisse de réseaux ferroviaires, de logistique ou d’optimisation des ressources. Des solutions suffisamment précises peuvent être trouvées grâce à des méthodes d’approximation.
Les qubits : une nouvelle approche de calcul
Les ordinateurs quantiques utilisent des qubits, qui, contrairement aux circuits logiques classiques ne se limitent pas à des valeurs de zéro ou un, mais peuvent adopter n’importe quelle valeur intermédiaire. Ces qubits sont réalisés à l’aide d’atomes fortement refroidis, d’ions ou de circuits supraconducteurs, et construire un ordinateur quantique avec un grand nombre de qubits reste un défi technique majeur.
Cependant, des méthodes mathématiques permettent d’ores et déjà d’explorer les performances potentielles des ordinateurs quantiques tolérants aux fautes.
« Nous avons abordé la question de manière rigoureuse, en utilisant des méthodes mathématiques, et avons obtenu des résultats solides sur le sujet. Nous avons surtout clarifié dans quel sens des avantages peuvent être obtenus, » déclare le Prof. Dr. Jens Eisert, qui dirige un groupe de recherche conjoint à la Freie Universität Berlin et au Helmholtz-Zentrum Berlin.
Une avancée significative grâce à l’analyse mathématique
L’équipe de Jens Eisert et de son collègue Jean-Pierre Seifert a utilisé des méthodes analytiques pures pour évaluer comment un ordinateur quantique équipé de qubits pourrait résoudre cette classe de problèmes. Il s’agit d’une expérience de pensée classique, menée avec papier et crayon et une grande expertise.
« Nous supposons simplement, indépendamment de la réalisation physique, qu’il y a suffisamment de qubits et nous examinons les possibilités d’opérations de calcul avec ceux-ci, » explique Vincent Ulitzsch, doctorant à l’Université Technique de Berlin.
En procédant ainsi, ils ont découvert des similitudes avec un problème bien connu en cryptographie, c’est-à-dire le chiffrement des données.
« Nous avons réalisé que nous pourrions utiliser l’algorithme de Shor pour résoudre une sous-classe de ces problèmes d’optimisation, » ajoute Vincent Ulitzsch. Cela signifie que le temps de calcul n’augmente plus de manière exponentielle avec le nombre de villes (2N), mais croît seulement de manière polynomiale (Nx, où x est une constante). La solution obtenue de cette manière est également qualitativement bien meilleure que la solution approximative obtenue avec l’algorithme conventionnel.
« Nous avons démontré que, pour une classe spécifique mais très importante et pratiquement pertinente de problèmes d’optimisation combinatoire, les ordinateurs quantiques présentent un avantage fondamental par rapport aux ordinateurs classiques pour certaines instances du problème, » conclut Jens Eisert.
Légende illustration : Le problème du voyageur de commerce est un classique des mathématiques. Un voyageur doit visiter N villes par le chemin le plus court et revenir à son point de départ. Lorsque le nombre N augmente, le nombre d’itinéraires possibles explose. Ce problème peut alors être résolu à l’aide de méthodes d’approximation. Les ordinateurs quantiques pourraient fournir plus rapidement des solutions nettement meilleures. HZB
Article : « An in-principle super-polynomial quantum advantage for approximating combinatorial optimization problems via computational learning theory » – DOI: 10.1126/sciadv.adj5170
