Résoudre ‘Le Problème du Voyageur de Commerce’ Grâce à l’Informatique Quantique

Un problème algorithmique classique dans le domaine de l’informatique appelé le Problème du Voyageur de Commerce (TSP) est un exemple parfait de problème d’optimisation combinatoire.

Qu’est-ce que le TSP ? Ce classique des mathématiques consiste à trouver la route la plus courte possible pour visiter un nombre N de villes exactement une fois avant de retourner à la ville d’origine. Cependant, à mesure que le nombre de villes augmente, augmentent également les routes possibles et le temps de calcul pour trouver la solution optimale. Bien que ce problème puisse être résolu à l’aide de méthodes d’approximation, les ordinateurs quantiques pourraient fournir de meilleures solutions et beaucoup plus rapidement.

C’est exactement ce que l’équipe du physicien théoricien Prof. Dr. Jens Eisert a démontré : que de tels problèmes peuvent être résolus mieux et plus rapidement avec des ordinateurs quantiques.

L’informatique quantique utilise du matériel et des algorithmes qui exploitent la mécanique quantique pour résoudre des problèmes complexes qui dépassent les capacités des ordinateurs classiques, y compris les supercalculateurs. Malgré leur puissance, les supercalculateurs – des ordinateurs classiques massifs avec des milliers de cœurs CPU et GPU – sont limités par leur dépendance à la technologie des transistors du 20e siècle lors de la résolution de problèmes présentant un haut degré de complexité.

C’est là que la physique quantique intervient. Contrairement aux ordinateurs classiques, qui codent l’information en bits binaires (0 et 1), les ordinateurs quantiques utilisent des bits quantiques ou qubits pour exécuter des algorithmes quantiques multidimensionnels.

De plus, contrairement aux ordinateurs classiques, qui utilisent des ventilateurs pour refroidir, les ordinateurs quantiques nécessitent que leurs processeurs quantiques soient maintenus à des températures extrêmement froides pour conserver leurs états quantiques. Cela est réalisé grâce à des superfluides refroidis.

Les supraconducteurs sont des matériaux qui présentent un effet quantique critique, permettant aux électrons de les traverser sans résistance. Lorsque les électrons passent à travers, ils se regroupent pour transporter une charge à travers les barrières. Lorsque deux supraconducteurs sont placés de chaque côté d’un isolant, une jonction Josephson est formée, qui est utilisée pour conduire des qubits supraconducteurs.

Un qubit est utile pour la tâche importante de placer son information quantique dans un état de superposition, une combinaison des configurations possibles du qubit. Des groupes de qubits en superposition sont capables de créer des espaces de calcul complexes et multidimensionnels où des problèmes complexes peuvent être représentés.

Ici, par l’intrication de deux qubits, les modifications apportées à l’un peuvent avoir un impact direct sur l’autre, tandis que lorsque ces qubits intriqués sont placés dans un état de superposition, nous obtenons de nombreuses probabilités. Le calcul sur un ordinateur quantique fonctionne en préparant une superposition de tous les états de calcul possibles, et grâce à l’interférence, des solutions sont trouvées.

Bien sûr, construire un ordinateur quantique avec de nombreux qubits est une procédure très complexe, bien que plusieurs méthodes soient explorées pour savoir ce que de tels ordinateurs peuvent accomplir.

Selon Eisert, qui dirige un groupe de recherche conjoint au Helmholtz-Zentrum Berlin (HZB), un centre de recherche pour les matériaux énergétiques, et l’université de recherche publique Freie Universität Berlin :

“Il y a beaucoup de mythes à ce sujet, et parfois une certaine quantité d’air chaud et d’hypothèses. Cependant, nous avons abordé la question de manière rigoureuse, en utilisant des méthodes mathématiques, et fourni des résultats solides sur le sujet. Avant tout, nous avons clarifié dans quel sens il peut y avoir des avantages.

Le Problème Critique du Voyageur de Commerce

Un problème d’optimisation, le TSP est d’une grande importance économique dans l’industrie de la logistique et de la chaîne d’approvisionnement. Il fait partie de la catégorie plus large des problèmes d’optimisation combinatoire, qui comprend également la planification de tâches, l’allocation de ressources, l’optimisation de portefeuille et même le repliement de protéines, tous critiques pour divers secteurs.

Compte tenu de l’importance sociale et économique de ces problèmes, ils ont fait l’objet d’une recherche intense. Ainsi, trouver la réponse à des problèmes tels que la chaîne d’approvisionnement la plus efficace et la route de livraison la moins chère a un impact positif sur notre vie quotidienne.

Cependant, optimiser les routes de livraison pour plusieurs destinations tout en considérant diverses contraintes telles que les embouteillages, les coûts opérationnels croissants, les changements de route soudains, les rendez-vous d’affaires de dernière minute et les demandes des clients rend le TSP encore plus difficile à résoudre. Malgré ces défis, résoudre le TSP est crucial pour la livraison efficace de biens, ce qui assure un modèle commercial viable.

Il existe de nombreux avantages à résoudre ce problème, notamment la réduction de la distance et des heures de trajet et l’économie de carburant. La minimisation de la distance parcourue peut aider à réduire considérablement l’empreinte carbone, ce qui se traduit par une meilleure qualité de l’air, un ralentissement du changement climatique et une croissance économique. De plus, résoudre le TSP peut aider à assurer la livraison à temps des biens et les réunions avec les clients, ce qui améliore l’expérience client et les entreprises de services sur le terrain.

Comme nous l’avons vu, résoudre le problème ne profite pas seulement aux entreprises, mais ces avantages profitent également aux clients, enrichissant l’expérience pour tous les acteurs impliqués.

Plusieurs méthodes peuvent être utilisées pour résoudre le problème du TSP. L’une de ces méthodes est l’approche « Brute-Force », qui calcule toutes les permutations possibles pour trouver la route la plus courte. Dans la méthode de branch-and-bound, le problème est décomposé en plusieurs sous-problèmes, avec chaque solution de phase influençant la solution trouvée aux phases suivantes.

Dans la programmation dynamique, l’accent est mis sur l’évitement des calculs redondants. Le plus proche voisin, quant à lui, est un algorithme d’approximation dans lequel vous commencez par l’emplacement de départ et vous arrêtez ensuite au plus proche. Une fois que toutes les villes sont couvertes, vous revenez au point de départ. Bien que pratique et relativement rapide, cette méthode ne fournit pas toujours une route efficace.

À mesure que la technologie avance, la planification et l’optimisation des routes peuvent être effectuées de manière beaucoup plus efficace. L’intelligence artificielle (IA), en particulier, peut également aider à résoudre le problème en analysant une grande quantité de données rapidement pour aider de nombreuses entreprises modernes à prendre des décisions opérationnelles et stratégiques.

Les ordinateurs quantiques sont également étudiés pour résoudre le problème ; après tout, ils offrent des accélérations de calcul considérables par rapport aux ordinateurs classiques. On a longtemps suggéré que ces ordinateurs pourraient en fait aider à améliorer les approximations de ces problèmes.

Utilisation de Techniques d’Informatique Quantique pour Résoudre le TSP

Bien que l’informatique quantique suscite un intérêt énorme et fournisse des résultats prometteurs pour certains problèmes, l’étendue de cet avantage quantique reste en grande partie inexplorée.

Ainsi, l’étude a fourni une preuve constructive complète que les ordinateurs quantiques peuvent en fait surpasser les ordinateurs classiques pour trouver des approximations de problèmes d’optimisation combinatoire.

L’étude la plus récente, menée par Eisert et son collègue Jean-Pierre Seifert, a utilisé uniquement des méthodes analytiques pour évaluer comment un ordinateur quantique avec des qubits peut résoudre le problème du TSP.

“Nous supposons simplement, indépendamment de la réalisation physique, qu’il y a suffisamment de qubits et examinons les possibilités d’effectuer des opérations de calcul avec eux”, ce qui ressemble à un problème courant en cryptographie, c’est-à-dire le cryptage des données, a expliqué Vincent Ulitzsch, un étudiant en doctorat à la Technical University of Berlin.

Ensuite, l’équipe a utilisé l’algorithme de Shor, un algorithme quantique, pour trouver les facteurs premiers d’un entier et résoudre une sous-classe de ces problèmes d’optimisation. Avec cela, le temps de calcul ne va plus exploser à mesure que le nombre de villes augmente. Il ne va augmenter que de manière polynomial, c’est-à-dire avec Nx, où x est une constante. De cette façon, la solution obtenue est également qualitativement beaucoup meilleure que celle dérivée de la solution approximative à l’aide de l’algorithme classique.

En utilisant des concepts cryptographiques et la théorie de l’apprentissage computationnel, l’étude fournit une “preuve constructive complète que les ordinateurs quantiques présentent un avantage super-polynomial par rapport aux ordinateurs classiques pour approximer les problèmes d’optimisation combinatoire.”

L’étude a également noté que l’équipe de recherche a réalisé des progrès importants sur la question cruciale de ce que les ordinateurs quantiques peuvent offrir pour approximer la solution des problèmes d’optimisation combinatoire, qui ont des impacts sociaux et économiques importants.

L’étude a été financée par l’Einstein Research Unit, le Berlin Mathematics Research Center (MATH+ Cluster of Excellence), le BMBF (Hybrid), le BMWK (EniQmA), la vallée quantique de Munich et la DFG. Le ministère fédéral de l’Éducation et de la Recherche d’Allemagne a également fourni un soutien financier.

Exploration du Potentiel de l’Informatique Quantique

Bien que cela soit une grande réalisation, ce n’était pas la première fois que l’informatique quantique a été utilisée pour résoudre le problème du voyageur de commerce. Il y a eu de nombreux cas d’enthousiastes et de chercheurs qui ont examiné la résolution du problème en utilisant l’informatique quantique.

En décembre 2022, un document a proposé un algorithme quantique pour le TSP basé sur la recherche adaptative de Grover (GAS). Dans le cadre du GAS, il y a au moins deux difficultés fondamentales – les solutions peuvent ne pas être réalisables, et le nombre de qubits des ordinateurs quantiques actuels est très limité et ne peut pas répondre aux exigences minimales, ce qui restreint l’application des algorithmes quantiques pour les problèmes d’optimisation combinatoire.

Ainsi, le document a affiné l’oracle de détection du cycle hamiltonien (HCD), qui peut supprimer automatiquement les solutions non réalisables pendant l’exécution de l’algorithme. Ils ont également conçu une stratégie d'”enregistrement d’ancrage” pour économiser l’utilisation de qubits, en tenant pleinement compte de l’exigence de réversibilité de l’informatique quantique et en surmontant la difficulté des qubits utilisés qui ne peuvent pas être simplement écrasés ou libérés. Cela a permis à l’étude de ne nécessiter que 31 qubits, et la solution avait un taux de réussite de 86,71 %.

En 2019, le physicien autoproclamé Joseph Cammidge a écrit à propos de l’utilisation d’un processeur d’annealing quantique, qui lui a permis de résoudre le problème du voyageur de commerce pour sept villes et a le potentiel théorique de résoudre pour neuf villes une fois que les limitations technologiques sont éliminées.

Une nouvelle méthode de calcul, l’annealing quantique, a montré le potentiel de résoudre des problèmes d’optimisation plus rapidement que les techniques classiques. Sa théorie implique que les qubits atteindront un état d’énergie faible optimal lorsqu’ils sont refroidis.

Cependant, en 2021, une étude financée par Supply Chain Digital & Data Science, Johnson & Johnson a constaté que l’annealeur quantique ne peut gérer qu’une taille de problème de 8 nœuds ou moins, et ses performances sont inférieures en termes de temps et de précision par rapport au solveur classique.

L’utilisation de l’informatique quantique pour résoudre le problème du TSP est en cours depuis un certain temps maintenant. Il y a plus de deux décennies, en 2001, une étude a commencé à rechercher un algorithme quantique pour résoudre le problème.

Dans le document, Buckley Hopper de l’Université de l’Alabama a examiné les algorithmes quantiques de Grover et Shor. Il a noté que l’algorithme de Grover ne fournit qu’une amélioration de la racine carrée, ce qui implique qu’il ne peut pas rendre un problème classiquement inabordable abordable sur un ordinateur quantique. En ce qui concerne l’algorithme de Shor, Hopper a observé que, même s’il peut convertir un problème de factorisation première présumé inabordable en un problème abordable sur la machine quantique, il n’est adapté qu’à un type de problème très spécifique.

Dans l’ensemble, Hopper “n’a pas trouvé de résultat satisfaisant pour un algorithme de calcul de solutions approximatives au problème du voyageur de commerce”.

Quelques années plus tard, l’Institute of Electrical and Electronics Engineers (IEEE) a présenté un nouvel algorithme pour résoudre le problème, inspiré à la fois des algorithmes génétiques et de l’informatique quantique. L’IEEE a constaté que les résultats de l’application de l’algorithme proposé sur certaines instances du problème du voyageur de commerce sont considérablement meilleurs que ceux fournis par les algorithmes génétiques standard.

Cliquez ici pour en savoir plus sur l’état actuel de l’informatique quantique.

Entreprises Travaillant avec l’Informatique Quantique

Maintenant, regardons quelques noms qui travaillent sur la recherche et le développement de l’informatique quantique :

#1. IBM

International Business Machines Corporation est engagé dans une large gamme de secteurs, notamment l’IA, les services cloud, l’informatique, le financement client et le financement commercial. Le géant de la technologie est également impliqué dans l’informatique quantique via sa plate-forme IBM Quantum, qui offre un accès public et premium à ses services d’informatique quantique basés sur le cloud. Cela inclut un ensemble de processeurs quantiques prototype d’IBM, des didacticiels sur le calcul quantique et un manuel interactif.

Récemment, les scientifiques d’IBM ont déclaré qu’ils sont un pas de plus pour surmonter un obstacle qui débloque le potentiel révolutionnaire des ordinateurs quantiques. Pour cela, ils ont introduit un nouveau code de correction d’erreur quantique, qu’ils disent être environ dix fois plus efficace que les méthodes précédentes.

Plus tard l’année dernière, la société a également lancé l’ordinateur quantique appelé Condor, avec 1 121 qubits supraconducteurs disposés en motif en nid d’abeille. IBM a également présenté le système quantique IBM Two, son premier ordinateur quantique modulaire et son architecture de supercalcul quantique, qui est évolutif et peut donc être mis à niveau avec des puces qui seront lancées au cours des cinq prochaines années.

Avec une capitalisation boursière de 175 milliards de dollars, les actions d’IBM sont cotées à 190,86 dollars, en hausse de 16,66 % depuis le début de l’année. IBM a affiché un chiffre d’affaires (TTM) de 61,86 milliards de dollars, un BPA (TTM) de 8,03, un ratio cours/bénéfice (TTM) de 23,76 et un ROE (TTM) de 33,36 %. La société verse un dividende de 3,48 %.

#2. D-Wave Systems

Cette société d’informatique quantique développe et fournit des systèmes, des logiciels et des services connexes. Ses produits incluent The Leap et The Advantage, et elle propose des applications quantiques pour la planification, la logistique, la découverte de médicaments, les processus de fabrication et bien plus encore.

Plus tôt ce mois, D-Wave a déclaré que les machines quantiques peuvent désormais résoudre des problèmes avec des applications dans le monde réel plus rapidement que n’importe quel ordinateur ordinaire. Plus tôt cette année, la société a annoncé un ordinateur quantique avec 1 200 qubits, 10 000 couplages et une résolution de problèmes d’optimisation difficile 20 fois plus rapide.

Les actions de la société sont actuellement cotées à 1,86 dollar, en hausse de 138,6 % depuis le début de l’année, avec une capitalisation boursière de 267 millions de dollars. Elle a rapporté 8,247 millions de dollars de ventes (TTM), un BPA (TTM) de -0,66 et un ratio cours/bénéfice (TTM) de -3,19, et a annoncé une croissance de plus de 20 % de ses ventes pour son quatrième trimestre et son exercice 2023, tandis que les commandes ont augmenté de 34 % et 89 %, respectivement.

Intéressant, le PDG de la société, le Dr Alan Baratz, a déclaré que l’entreprise a du momentum, en citant le partenariat stratégique pluriannuel avec Zapata AI, l’introduction du prototype Advantage2 de plus de 1 200 qubits, les joint-ventures avec NEC Australia et Deloitte Canada, et la nomination de l’ancien secrétaire à la Sécurité intérieure Kirstjen Nielsen au conseil d’administration.

Conclusion

Le marché de l’informatique quantique devrait atteindre 6,5 milliards de dollars en 2028, et son potentiel pour résoudre le problème du voyageur de commerce (TSP) a des répercussions pour plusieurs industries, telles que la fabrication, la logistique, la gestion de la chaîne d’approvisionnement, le commerce électronique, les transports et la recherche. Après tout, cela peut entraîner des avantages considérables, notamment en améliorant la productivité, en réduisant les coûts et en stimulant l’innovation dans divers secteurs.

Cliquez ici pour obtenir la liste des cinq meilleures sociétés d’informatique quantique.