Les ordinateurs quantiques, utilisant des qubits polyvalents, sont à l’avant-garde de la résolution de problèmes d’optimisation complexes comme le dilemme du voyageur de commerce, traditionnellement en proie à l’inefficacité informatique. Grâce à une analyse mathématique rigoureuse, les chercheurs ont démontré que l’informatique quantique peut transformer fondamentalement la résolution de problèmes, en offrant une augmentation polynomiale plus efficace du temps de calcul par rapport aux méthodes classiques et en produisant des solutions supérieures.
Le problème du voyageur de commerce est considéré comme un excellent exemple de problème d’optimisation combinatoire. Aujourd'hui, une équipe berlinoise dirigée par le physicien théoricien, le professeur Jens Eisert de la Freie Universität Berlin et de la HZB, a montré qu'une certaine classe de problèmes de ce type peut en réalité être résolue mieux et beaucoup plus rapidement avec des ordinateurs quantiques qu'avec des méthodes conventionnelles.
Les ordinateurs quantiques utilisent ce qu'on appelle des qubits, qui ne valent ni zéro ni un comme dans les circuits logiques conventionnels, mais peuvent prendre n'importe quelle valeur intermédiaire. Ces qubits sont réalisés par des atomes, des ions ou des circuits supraconducteurs hautement refroidis, et il est encore physiquement très complexe de construire un ordinateur quantique avec de nombreux qubits. Cependant, les méthodes mathématiques peuvent déjà être utilisées pour explorer ce que les ordinateurs quantiques tolérants aux pannes pourraient réaliser à l’avenir.
« Il y a beaucoup de mythes à ce sujet, et parfois une certaine dose de vent et de battage médiatique. Mais nous avons abordé la question avec rigueur, en utilisant des méthodes mathématiques, et avons livré des résultats solides sur le sujet. Surtout, nous avons clarifié dans quel sens il peut y avoir des avantages », déclare le professeur Jens Eisert, qui dirige un groupe de recherche commun à la Freie Universität Berlin et au Helmholtz-Zentrum Berlin.
Le problème du voyageur de commerce est un classique des mathématiques. Un voyageur doit visiter N villes par l’itinéraire le plus court et revenir au point de départ. À mesure que le nombre N augmente, le nombre d’itinéraires possibles explose. Ce problème peut ensuite être résolu en utilisant des méthodes d'approximation. Les ordinateurs quantiques pourraient fournir plus rapidement des solutions bien meilleures. Crédit : HZB
Résoudre des problèmes complexes
Le problème bien connu du voyageur de commerce en est un parfait exemple : un voyageur doit visiter plusieurs villes puis retourner dans sa ville natale. Quel est le chemin le plus court ? Bien que ce problème soit facile à comprendre, il devient de plus en plus complexe à mesure que le nombre de villes augmente et que les temps de calcul explosent.
Le problème du voyageur de commerce représente un groupe de problèmes d'optimisation qui revêtent une importance économique énorme, qu'ils concernent les réseaux ferroviaires, la logistique ou l'optimisation des ressources. Des solutions suffisamment bonnes peuvent être trouvées en utilisant des méthodes d’approximation.
Le présent travail (flèche) montre qu’une certaine partie des problèmes combinatoires peut être bien mieux résolue avec des ordinateurs quantiques, voire même exactement. Crédit : HZB/Eisert
Solutions et avancées quantiques
L'équipe dirigée par Jens Eisert et son collègue Jean-Pierre Seifert a désormais utilisé des méthodes purement analytiques pour évaluer comment un ordinateur quantique doté de qubits pourrait résoudre cette classe de problèmes. Une expérience de pensée classique avec un stylo et du papier et beaucoup d'expertise.
« Nous supposons simplement, quelle que soit la réalité physique, qu'il existe suffisamment de qubits et étudions les possibilités d'effectuer des opérations informatiques avec eux », explique Vincent Ulitzsch, doctorant à l'Université technique de Berlin. Ce faisant, ils ont dévoilé des similitudes avec un problème bien connu de la cryptographie, à savoir le cryptage des données. « Nous avons réalisé que nous pouvions utiliser l'algorithme de Shor pour résoudre une sous-classe de ces problèmes d'optimisation », explique Ulitzsch.
Cela signifie que le temps de calcul n'explose plus avec le nombre de villes (exponentiel, 2N), mais n'augmente que de manière polynomiale, c'est-à-dire avec NX, où x est une constante. La solution obtenue de cette manière est également qualitativement bien meilleure que la solution approchée utilisant l’algorithme conventionnel.
« Nous avons montré que pour une classe spécifique mais très importante et pertinente de problèmes d'optimisation combinatoire, les ordinateurs quantiques ont un avantage fondamental sur les ordinateurs classiques dans certains cas du problème », explique Eisert.
