Les travaux de l'équipe sont publiés dans la revue Science Advances .

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 publicitaire. 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 précisé dans quel sens il peut y avoir de nombreux avantages", déclare le professeur Dr. Eisert, qui dirige un groupe de recherche commun à la Freie Universität Berlin et au Helmholtz-Zentrum Berlin.

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'il s'agisse des réseaux ferroviaires, de la logistique ou de l'optimisation des ressources. Des solutions suffisamment bonnes peuvent être trouvées en utilisant des méthodes d'approximation.

L'équipe dirigée par Eisert et son collègue Jean-Pierre Seifert a maintenant 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éalisation physique, qu'il existe suffisamment de qubits et étudions les possibilités d'effectuer des opérations informatiques avec eux", explique Vincent Ulitzsch, docteur en sciences. étudiant à l'Université Technique de Berlin.

Ce faisant, l'équipe a 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, 2 ^N ), mais n'augmente que de manière polynomiale, c'est-à-dire avec N ^x , où x est une constante. La solution obtenue de cette manière est également qualitativement bien meilleure que la solution approximative 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 certaines instances du problème", explique Eisert.