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 excellent exemple de problème d'optimisation combinatoire.

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

C'est exactement ce que le physicien théoricien L'équipe du professeur Dr. Jens Eisert a démontré: que de tels problèmes peuvent être résolus mieux et plus rapidement avec les 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 hors de portée des superordinateurs conventionnels, y compris les superordinateurs. Malgré leur puissance, les supercalculateurs – des ordinateurs classiques massifs dotés de milliers de cœurs CPU et GPU – sont limités par leur dépendance à la technologie des transistors du XXe siècle pour résoudre des problèmes d’un haut degré de complexité. 

C'est là qu'intervient la physique quantique. Contrairement aux ordinateurs classiques, qui codent les informations 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 froides pour conserver leurs états quantiques. Ceci est réalisé grâce à des superfluides surfondus. 

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

Un qubit est utile pour la tâche importante consistant à placer son information quantique dans un état de superposition, une combinaison de configurations possibles pour un qubit. Des groupes de qubits en superposition sont capables de créer des espaces de calcul multidimensionnels complexes permettant de représenter des problèmes complexes.

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 informatiques possibles, et grâce aux interférences, des solutions sont trouvées.

Bien entendu, construire un ordinateur quantique avec de nombreux qubits est une procédure très complexe, même si plusieurs méthodes sont à l’étude quant à ce que de tels ordinateurs peuvent accomplir. 

Selon Eisert, qui dirige un groupe de recherche commun au Helmholtz-Zentrum Berlin (HZB), un centre de recherche pour la recherche sur 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 dose de vent et de battage médiatique. Cependant, nous avons abordé la question avec rigueur, en utilisant des méthodes mathématiques, et avons livré des résultats solides sur le sujet. Nous avons surtout montré dans quelle mesure 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 supply chain. Il s’inscrit dans la catégorie plus large des problèmes d’optimisation combinatoire, qui incluent également la planification des tâches, l’allocation des ressources, l’optimisation du 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 d’intenses recherches. Ainsi, trouver la réponse à des problèmes tels que la chaîne d’approvisionnement la plus efficace et l’itinéraire de livraison le moins cher a un impact positif sur notre vie quotidienne.

Cependant, optimiser les itinéraires de livraison pour plusieurs destinations tout en tenant compte de diverses contraintes telles que les embouteillages, l'augmentation des coûts opérationnels, les changements soudains d'itinéraire, les rendez-vous professionnels de dernière minute et les demandes des clients rend le TSP encore plus difficile à résoudre. Malgré ces défis, la résolution du TSP est cruciale pour la livraison efficace des marchandises, ce qui garantit un modèle économique viable. 

Il y a de nombreux avantages à résoudre ce problème, notamment la réduction de la distance et des heures parcourues et l’économie de carburant. Minimiser la distance parcourue peut contribuer à 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, la résolution du TSP peut contribuer à la livraison à temps des marchandises et aux réunions ponctuelles avec les clients, ce qui améliore l'expérience client et les activités de service 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 toutes les personnes impliquées.

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

En programmation dynamique, l’accent est mis sur l’évitement des calculs redondants. Le voisin le plus proche, quant à lui, est un algorithme d'approximation dans lequel vous commencez par l'emplacement de départ, puis vous arrêtez à l'emplacement le plus proche. Une fois toutes les villes parcourues, vous revenez 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 contribuer à 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 de calcul considérables par rapport aux ordinateurs classiques. Il a longtemps été suggéré que ces ordinateurs pourraient réellement contribuer à améliorer les approximations de ces problèmes. 

Utiliser des techniques d'informatique quantique pour résoudre le TSP

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

En tant que telle, 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 comment un ordinateur quantique doté de qubits peut résoudre le problème du TSP. 

"Nous supposons simplement, quelle que soit la réalisation physique, qu'il y a suffisamment de qubits et examinons les possibilités d'effectuer des opérations informatiques avec eux", ce qui révèle une ressemblance avec un problème courant en cryptographie, à savoir le cryptage des données, a expliqué Vincent Ulitzsch. , un doctorat. étudiant à l'Université Technique de Berlin. 

L'équipe a ensuite 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 avec l'augmentation du nombre de villes. Il augmentera seulement de manière 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 informatique, l’étude donne « une preuve pleinement constructive que les ordinateurs quantiques présentent 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 savoir quel potentiel les ordinateurs quantiques peuvent offrir pour se rapprocher 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'unité de recherche Einstein, le centre de recherche en mathématiques de Berlin (MATH+ Cluster of Excellence), le BMBF (Hybrid), le BMWK (EniQmA), la Munich Quantum Valley et le DFG. Le ministère fédéral allemand de l’Éducation et de la Recherche a également apporté un soutien financier.

Explorer le potentiel de l'informatique quantique 

Bien qu'il s'agisse d'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 nombreux passionnés et chercheurs ont cherché à résoudre ce problème grâce à l'informatique quantique. 

En décembre 2022, un papier a proposé un algorithme quantique pour le TSP basé sur la recherche adaptative 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 répondre aux exigences minimales, ce qui limite l'application des algorithmes quantiques aux problèmes d'optimisation combinatoire. 

En tant que tel, l’article a peaufiné l’oracle de détection du cycle hamiltonien (HCD), qui peut supprimer automatiquement les solutions peu pratiques pendant l’exécution de l’algorithme. Ils ont également conçu une stratégie de « 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 soient pas simplement écrasés ou libérés. Cela a permis à l'étude de nécessiter seulement 31 qubits et la solution a eu un taux de réussite de 86.71 %.

En 2019, Joseph Cammidge, connaisseur de physique auto-défini écrit sur l'utilisation d'un processeur quantique de recuit, qui lui a permis de résoudre le problème du voyageur de commerce pour sept villes et a le potentiel théorique de le résoudre pour neuf villes une fois les limitations technologiques éliminées. 

Une nouvelle méthode informatique, le recuit quantique, a montré son potentiel pour résoudre les problèmes d'optimisation plus rapidement que les techniques classiques. Sa théorie implique que les qubits atteindront un état optimal de faible énergie lorsqu’ils seront surrefroidis. 

Cependant, en 2021, un étude Financé par Supply Chain Digital & Data Science, Johnson & Johnson a découvert que le recuit quantique ne peut gérer qu'un problème de 8 nœuds ou moins, et que ses performances sont inférieures à la moyenne 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 existe depuis un certain temps déjà. Il y a plus de vingt ans, en 2001, une étude a commencé recherche pour un algorithme quantique pour résoudre le problème.

Dans son article, Buckley Hopper, de l'Université d'Alabama, a examiné les algorithmes de Grover et de Shor pour ordinateurs quantiques. Il a constaté que l'algorithme de Grover n'apporte qu'une amélioration de la racine carrée, ce qui implique qu'il ne peut pas rendre un problème classiquement insoluble résoluble sur ordinateur quantique. Quant à l'algorithme de Shor, Hopper a observé que, s'il peut transformer un problème de facteurs premiers a priori insoluble en un problème résoluble sur machine quantique, il ne convient 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 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) 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 standards.

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

Entreprises travaillant avec l’informatique quantique 

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

# 1. IBM

International Business Machines Corporation est présente dans un large éventail de 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. Ces services comprennent un ensemble de prototypes de processeurs quantiques IBM, des tutoriels sur l'informatique quantique et un manuel interactif.

Plus récemment, les scientifiques d'IBM A déclaré qu'ils sont un pas de plus vers la victoire sur un obstacle qui libère le potentiel révolutionnaire des ordinateurs quantiques. Pour cela, ils ont introduit un nouveau code de correction d’erreurs quantiques, qui, selon eux, est environ dix fois plus efficace que les méthodes précédentes. 

À la fin de l’année dernière, la société a également lancé l’ordinateur quantique appelé Condor, doté de 1,121 XNUMX qubits supraconducteurs disposés en nid d’abeille. IBM a également dévoilé IBM Quantum System Two, son premier ordinateur quantique modulaire et son architecture de supercalcul centrée sur le quantique, qui est évolutive et peut donc être mise à 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, l'action IBM s'échange à 190.86 dollars, en hausse de 16.66 % depuis le début de l'année. IBM a enregistré un chiffre d'affaires (sur les trois derniers mois) de 61.86 milliards de dollars, un BPA (sur les trois derniers mois) de 8.03, un PER (sur les trois derniers mois) de 23.76 et un ROE (sur les trois derniers mois) de 33.36 %. La société verse un rendement du 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 associés. Ses produits comprennent The Leap et The Advantage, et fournissent des applications quantiques pour la planification, la logistique, la découverte de médicaments, les processus de fabrication, etc. 

Plus tôt ce mois-ci, D-Wave a déclaré que les machines quantiques peuvent désormais résoudre les problèmes liés aux applications du 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 doté de 1,200 10,000 qubits, de 20 XNUMX coupleurs et d’un délai de résolution XNUMX fois plus rapide pour les problèmes d’optimisation difficiles.

L'action de la société se négocie 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 annoncé un chiffre d'affaires de 8.247 millions de dollars (TTM), un BPA de -0.66 (TTM) et un PER de -3.19 (TTM), ainsi qu'une croissance de plus de 20 % de son chiffre d'affaires pour le quatrième trimestre et pour fin d'année 4, tandis que les réservations ont augmenté respectivement de 2023 % et 34 %. 

Il est intéressant de noter que le PDG de la société, le Dr Alan Baratz, a déclaré l'élan de l'entreprise, citant le partenariat stratégique pluriannuel de la société avec Zapata AI, l'introduction du prototype Advantage1,200 de plus de 2 XNUMX qubits, les coentreprises avec NEC Australie 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 ramifications pour plusieurs secteurs, tels 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 substantiels, notamment en augmentant la productivité, en réduisant les dépenses et en stimulant l’innovation dans divers secteurs.

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