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, connu sous le nom de problème du voyageur de commerce (TSP), est un exemple majeur de problème d’optimisation combinatoire.

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

C’est exactement ce que l’équipe du physicien théoricien Prof. Dr. Jens Eisert: a démontré : de tels problèmes peuvent être résolus de façon meilleure et plus rapide 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 au-delà de la portée des ordinateurs conventionnels, y compris les superordinateurs. Malgré leur puissance, les superordinateurs — d’énormes ordinateurs classiques avec des milliers de cœurs CPU et GPU — sont limités par leur dépendance à la technologie transistorielle du XXe siècle lorsqu’ils résolvent des problèmes d’une grande 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 conventionnels qui utilisent des ventilateurs pour le refroidissement, les ordinateurs quantiques nécessitent que leurs processeurs quantiques soient maintenus à des températures extrêmement basses afin de conserver leurs états quantiques. Cela est réalisé grâce à des superfluides ultra-froids. 

Les supraconducteurs sont des matériaux qui présentent un effet quantique critique, permettant aux électrons de circuler sans résistance. Au passage, les électrons se couplent pour transporter une charge à travers les barrières. Lorsque deux supraconducteurs sont placés de part et d’autre d’un isolant, une jonction Josephson se forme, utilisée pour conduire les 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ù les problèmes complexes peuvent être représentés.

Ici, grâce à l’intrication de deux qubits, une modification de l’un peut impacter directement l’autre, tandis que lorsque ces qubits intriqués sont placés dans un état de superposition, de nombreuses probabilités apparaissent. Le calcul sur un ordinateur quantique fonctionne en préparant une superposition de tous les états de calcul possibles et, par interférence, les 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 quant aux capacités de tels ordinateurs.

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

« Il y a beaucoup de mythes à ce sujet, et parfois un certain battage médiatique. Cependant, nous avons abordé la question de manière rigoureuse, en utilisant des méthodes mathématiques, et avons fourni des résultats solides sur le sujet. Avant tout, nous avons clarifié en quel sens il peut y avoir des avantages. »

Le problème critique du voyageur de commerce

Problème d’optimisation, le TSP revêt 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 des tâches, l’allocation des ressources, l’optimisation de portefeuille, et même le repliement des protéines, tous essentiels à divers secteurs.

Compte tenu de l’importance sociale et économique de ces problèmes, ils ont fait l’objet de recherches intenses. Ainsi, trouver la réponse à des problèmes tels que la chaîne d’approvisionnement la plus efficace et le trajet de livraison le moins cher a un impact positif sur notre quotidien.

Cependant, optimiser les itinéraires de livraison pour de multiples destinations tout en prenant en compte diverses contraintes telles que la congestion du trafic, la hausse des coûts opérationnels, les changements d’itinéraire 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 des marchandises, 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 ainsi que l’économie de carburant. Minimiser 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 à la livraison ponctuelle des marchandises et aux réunions à temps 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 aide non seulement les entreprises, mais ces avantages se répercutent également sur les clients, enrichissant l’expérience de tous les acteurs impliqués.

Plusieurs méthodes peuvent être utilisées pour résoudre le problème du TSP. L’une d’elles est l’approche « force brute », qui calcule toutes les permutations possibles afin de trouver le trajet le plus court. Dans la méthode de branchement et de bornes, le problème est décomposé en plusieurs séries de sous-problèmes, chaque solution de stade influençant la solution trouvée aux étapes suivantes.

En 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 on commence par le point de départ puis on se rend au plus proche. Une fois toutes les villes couvertes, on revient au point de départ. Bien que pratique et relativement rapide, cette méthode ne fournit pas toujours un itinéraire efficace.

À mesure que la technologie progresse, la planification et l’optimisation des itinéraires peuvent être effectuées beaucoup plus efficacement. L’intelligence artificielle (IA), en particulier, peut également aider à résoudre le problème en analysant rapidement une quantité massive de données 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 computationnelles considérables par rapport aux ordinateurs classiques. Il a longtemps été suggéré que ces ordinateurs pourraient réellement aider à améliorer les approximations de ces problèmes. 

Utiliser les techniques d’informatique quantique pour résoudre le TSP

Alors que l’informatique quantique suscite un intérêt énorme et fournit des résultats prometteurs pour certains problèmes, l’étendue de cet avantage quantique reste largement inexplorée. 

Ainsi, l’étude a fourni une preuve constructive complète que les ordinateurs quantiques peuvent réellement surpasser les ordinateurs conventionnels pour trouver des approximations aux problèmes d’optimisation combinatoire.

La dernière étude, dirigée par Eisert et son collègue Jean‑Pierre Seifert, a utilisé uniquement des méthodes analytiques pour évaluer dans quelle mesure un ordinateur quantique avec des qubits peut résoudre le problème du TSP. 

« Nous supposons simplement, quelle que soit la réalisation physique, qu’il existe suffisamment de qubits et nous examinons les possibilités d’effectuer des opérations de calcul avec eux », ce qui révèle une ressemblance avec un problème commun en cryptographie, à savoir le chiffrement des données, explique Vincent Ulitzsch, doctorant à l’Université technique de 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. Ainsi, le temps de calcul n’explosera plus à mesure que le nombre de villes augmente. Il n’augmentera que de façon polynomiale, c’est‑à‑dire avec Nx, où x est une constante. De cette manière, la solution obtenue est également qualitativement bien meilleure que celle dérivée de la solution approximative obtenue avec l’algorithme conventionnel.

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 offrent un avantage super‑polynomial par rapport aux ordinateurs classiques dans l’approximation des problèmes d’optimisation combinatoire. » 

L’étude a en outre noté que l’équipe de recherche a réalisé des progrès significatifs sur la question importante de ce que les ordinateurs quantiques potentiels pourraient offrir pour l’approximation de la solution des problèmes d’optimisation combinatoire, qui ont des impacts sociaux et économiques substantiels.

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), le Munich Quantum Valley et le DFG. Le Ministère fédéral de l’Éducation et de la Recherche d’Allemagne a également apporté un soutien financier.

Explorer le potentiel de l’informatique quantique 

Bien que ce soit une grande réussite, ce n’était pas la première fois que l’informatique quantique était utilisée pour résoudre le problème du voyageur de commerce. De nombreuses fois, des passionnés et des chercheurs ont cherché à résoudre le problème en utilisant l’informatique quantique. 

En décembre 2022, un article a proposé un algorithme quantique pour le TSP basé sur la recherche adaptative de Grover (GAS). Dans le cadre du GAS, il existe 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 satisfaire les exigences minimales, limitant l’application des algorithmes quantiques aux problèmes d’optimisation combinatoire. 

Ainsi, l’article a affiné l’oracle de détection de cycle hamiltonien (HCD), qui peut éliminer automatiquement les solutions impraticables pendant l’exécution de l’algorithme. Ils ont également conçu une stratégie « registre d’ancrage » pour économiser l’utilisation des qubits, en tenant pleinement compte de l’exigence de réversibilité de l’informatique quantique et en surmontant la difficulté que les qubits utilisés ne puissent simplement être écrasés ou libérés. Cela a permis à l’étude de ne nécessiter que 31 qubits, et la solution a obtenu un taux de succès de 86,71 %.

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

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

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

L’utilisation de l’informatique quantique pour résoudre le problème du TSP se poursuit depuis un certain temps. 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 l’article, Buckley Hopper de l’Université de l’Alabama a examiné les algorithmes quantiques de Grover et de Shor. Il a noté que l’algorithme de Grover n’offre qu’une amélioration de la racine carrée, ce qui implique qu’il ne peut pas rendre un problème classiquement intractable traitable sur un ordinateur quantique. Quant à l’algorithme de Shor, Hopper a observé que, bien qu’il puisse transformer un problème de factorisation premier supposément intractable en un problème traitable sur la machine quantique, il n’est adapté qu’à un type très spécifique de problème. 

Dans l’ensemble, Hopper « n’a pas trouvé de résultat satisfaisant pour un algorithme permettant de calculer des 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 nettement meilleurs que ceux fournis par les algorithmes génétiques standards.

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

Entreprises travaillant avec l’informatique quantique 

Voyons maintenant quelques noms qui travaillent sur la recherche et le développement de l’informatique quantique:

#1. IBM

International Business Machines Corporation (IBM ) est active dans de nombreux secteurs, notamment l’IA, les services cloud, l’informatique, le financement client et le financement commercial. Le géant technologique est également impliqué dans l’informatique quantique via sa plateforme IBM Quantum, qui offre un accès public et premium à ses services d’informatique quantique basés sur le cloud. Ceux-ci comprennent un ensemble de processeurs quantiques prototypes d’IBM, des tutoriels sur le calcul quantique et un manuel interactif.

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

Fin d’année dernière, l’entreprise a également lancé l’ordinateur quantique appelé Condor, doté de 1 121 qubits supraconducteurs disposés en motif de nid d’abeille. IBM a également présenté IBM Quantum System Two, son premier ordinateur quantique modulaire et son architecture de supercalcul quantique centrée, qui est évolutive et peut donc être mise à jour avec des puces qui seront lancées dans les cinq prochaines années.

Avec une capitalisation boursière de 175 milliards de dollars, les actions d’IBM se négocient à 190,86 $, en hausse de 16,66 % depuis le début de l’année (YTD). IBM a affiché un chiffre d’affaires (TTM) de 61,86 milliards de dollars avec un BPA (TTM) de 8,03, un PER (TTM) de 23,76 et un ROE (TTM) de 33,36 %. L’entreprise verse un rendement de dividende de 3,48 %.

#2. D-Wave Systems

Cette entreprise d’informatique quantique développe et fournit des systèmes, logiciels et services associés. Ses produits comprennent 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 plus encore. 

Plus tôt ce mois-ci, D-Wave a déclaré que les machines quantiques peuvent désormais résoudre des problèmes à applications réelles plus rapidement que tout ordinateur ordinaire. Plus tôt cette année, l’entreprise a annoncé un ordinateur quantique doté de 1 200 qubits, 10 000 coupleurs, et un temps de résolution 20 fois plus rapide sur des problèmes d’optimisation difficiles.

Les actions de la société se négocient actuellement à 1,86 $, en hausse de 138,6 % depuis le début de l’année (YTD), avec une capitalisation boursière de 267 millions de dollars. Elle a déclaré des ventes de 8,247 millions de dollars (TTM), un BPA (TTM) de -0,66, un PER (TTM) de -3,19, et a annoncé une croissance de plus de 20 % des ventes pour son quatrième trimestre et les résultats de fin d’année 2023, tandis que les réservations ont augmenté respectivement de 34 % et 89 %.

Il est intéressant de noter que le PDG de la société, le Dr Alan Baratz, a déclaré que l’élan de l’entreprise était soutenu par le partenariat stratégique pluriannuel avec Zapata AI, l’introduction du prototype Advantage2 de plus de 1 200 qubits, des coentreprises avec NEC Australia et Deloitte Canada, et la nomination de l’ancienne 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 à 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, le transport et la recherche. Après tout, il peut entraîner des bénéfices substantiels, notamment en augmentant la productivité, en réduisant les dépenses et en stimulant l’innovation dans divers secteurs.

Cliquez ici pour la liste des cinq meilleures entreprises d’informatique quantique.