Quel est le lien entre un voyageur de commerce et un ordinateur quantique ?
A priori, il n’y a aucun rapport entre un voyageur de commerce et un ordinateur quantique. Même si on peut imaginer que cette personne ne se déplace jamais sans son ordinateur mais non…
Je vous imagine déjà, derrière votre écran, faire de grands yeux. Non je n’ai pas perdu la tête. Ma question est très sérieuse.
Alors…procédons par ordre, posons quelques bases et tout s’éclairera dans quelques minutes.
Le problème du voyageur de commerce
Personnellement, quand je pense à un voyageur de commerce, je pense à un homme barbu (ne me demandez pas pourquoi barbu, ça m’est venu comme ça) d’un autre temps, un temps « ante digital ». Il parcourt les routes poussiéreuses avec son paletot ou bien, s’il est à l’aise financièrement, avec sa carriole. Il s’arrête dans chaque ville pour vendre appareils ménagers, babioles et autres breloques.
http://www.mbadmb.com/wp-content/uploads/2018/01/Voyageur.jpg
Dans le cas qui nous préoccupe, oui cela a à voir avec des villes! Des villes et des distances… Mais pourquoi un voyageur de commerce me direz-vous ?
Bon allez, assez de suspense. Selon wikipédia, laissez-moi vous présenter le problème du voyageur de commerce.
« En informatique, le problème du voyageur de commerce, ou problème du commis voyageur, est un problème d’optimisation qui, étant donné une liste de villes, et des distances entre toutes les paires de villes, détermine un plus court chemin qui visite chaque ville une et une seule fois et qui termine dans la ville de départ. C’est un problème algorithmique célèbre, qui a généré beaucoup de recherches et qui est souvent utilisé comme introduction à l’algorithmique ou à la théorie de la complexité. Il présente de nombreuses applications que ce soit en planification et en logistique, ou bien dans des domaines plus éloignés comme la génétique (en remplaçant les villes par des gènes et la distance par la similarité). »
Schéma explicatif :
http://www.mbadmb.com/wp-content/uploads/2018/01/Probleme_Voyageur_Commerce.png
Malgré la simplicité de son énoncé, ce problème fait appel à une explosion combinatoire (terme mathématique pour dire qu’en gros les combinaisons explosent, hé oui : bravo !) pour déterminer tous les chemins possibles en fonction du nombre de villes.
Exemple : Pour 71 villes, le nombre de chemins possibles est supérieur à 5 × 1080 qui est environ le nombre d’atomes dans l’univers connu.
Vous imaginez ?
Le nombre de combinaisons est supérieur au nombre d’atomes dans l’univers connu. Moi, ça m’a scotchée sur place.
http://www.mbadmb.com/wp-content/uploads/2018/01/Explosion_Combinatoire.png
A ce jour, aucun algorithme classique n’est capable de trouver une solution exacte et rapide dans tous les cas.
C’est là où notre ordinateur quantique intervient.
Ouf ! vous êtes toujours avec moi ? J’espère car la suite vaut le coup de s’accrocher.
L’ordinateur quantique
Lui seul a la capacité de résoudre de tels problèmes comme le problème du voyageur de commerce.
Et pourquoi un ordinateur classique ne le pourrait-il pas me direz vous ?
Réponse : un ordinateur classique ne possède pas de mémoire de stockage suffisante ni assez de transistors pour traiter cette extraordinaire masse d’information.
Même le plus puissant des ordinateurs, doté de supercalculateurs ne le peut pas. Tout simplement parce qu’il ne fonctionne pas du tout de la même manière qu’un ordinateur quantique.
Binaire, vous avez dit Binaire ?
Un ordinateur classique code l’information de manière binaire c’est-à-dire avec des 0 et des 1. Chaque signe, lettre ou symbole possède son code binaire. Voyez cet exemple avec les simples lettres de l’alphabet.
http://www.mbadmb.com/wp-content/uploads/2018/01/binaire.png
La mémoire d’un ordinateur classique est donc constituée de milliards de cases contenant soit des 0, soit des 1. Et cette case s’appelle un « bit ». Afin d’accéder à ces cases, l’ordinateur contient des composants électroniques qui travaillent ensemble.
Superposition dans un ordinateur quantique – quèsaco ?
Un ordinateur quantique lui sera bien plus performant puisque chacune des cases sera augmentée de ce que l’on appelle la superposition quantique. Cela revient simplement à dire qu’une case ne comprend plus une seule valeur 0 ou 1 mais une superposition de 0 et de 1. L’ordinateur quantique utilise le « bit » quantique, autrement appelé « qbit » ou « qubit ».
Un exemple concret
Revenons au principe de la case.
Selon un très bon article de l’institut pandore de Vincent Rollet*, voici un exemple de traitement comparé entre un ordinateur classique et quantique.
« Utilisez le compteur ci-dessous pour m’afficher tous les nombres qui existent entre 0 et 99999 :
http://www.mbadmb.com/wp-content/uploads/2018/01/compteur0-e1515603589441.png
Vous n’aurez pas d’autres choix que de passer par toutes les combinaisons pour réussir ce défi :
http://www.mbadmb.com/wp-content/uploads/2018/01/Compteur1-e1515603705893.png
C’est exactement comme ça que fonctionne un ordinateur classique pour compter. Il doit traiter chaque information, chaque “nombre” dans notre exemple, une à une.
Un ordinateur quantique va raisonner autrement. Voilà comment un ordinateur quantique réagirait si je le mettais au défi :
http://www.mbadmb.com/wp-content/uploads/2018/01/Superposition-e1515603746231.png
Une case du compteur, autrement dit 1 bit, ne représente plus qu’une seule valeur comme on en a l’habitude, mais une superposition de plusieurs valeurs – 9 dans notre exemple.
Que cet exemple du compteur ne vous trompe pas : en informatique quantique, un ordinateur continue à travailler avec des 0 et des 1. L’ordinateur quantique ne superpose non pas 9 valeurs comme le fait le compteur ci-dessus, mais seulement 2 valeurs (0 et 1).
Ça reste un exploit. Concrètement, cela veut dire qu’un ordinateur quantique peut calculer beaucoup plus rapidement qu’un ordinateur classique, puisqu’il peut traiter tous ses états possibles en même temps (pour reprendre l’analogie du compteur : il a compté en 1 fois au lieu de compter 99999 fois). »
Ouf ! Si vous êtes arrivés jusque-là, je vous tire mon stetson de voyageur de commerce. Et vous n’avez encore rien vu…
Puissance des « qbits »
Pour ce qui est de la puissance, sachez qu’à chaque fois qu’on ajoute un « qbit » on double la puissance d’un ordinateur quantique. Exemple : un ordinateur quantique à 8 qbits va calculer 64 fois plus rapidement qu’un ordinateur classique à 8 bits, et ainsi de suite. On dépasse ainsi clairement la loi de Moore, ne trouvez-vous pas ?
Les applications possibles de l’ordinateur quantique
Bon alors, c’est bien gentil tout ça mais concrètement, pourquoi faire couler autant d’encre si on ne sait pas à quoi tout cela peut bien servir ?
Vous avez raison. Ceci reste quelque peu abstrait mais il fallait en passer par là pour comprendre pourquoi nos chercheurs et nos informaticiens mettent autant d’efforts et d’énergie à travailler sur l’ordinateur quantique.
Je vous propose une vidéo récapitulative et pédagogique qui explique quelles sont les applications possibles en informatique quantique. Très instructif en moins de 4 minutes.
Résumé vidéo :
- Il existe aujourd’hui 10 ordinateurs quantiques dans le monde.
- L’objectif actuel est de pourvoir émuler un ordinateur quantique dans un ordinateur classique afin d’augmenter la capacité de traitement des ordinateurs classiques même si effectivement le temps de traitement sera un peu plus lent.
- Quelques applications de l’ordinateur quantique:
- Services financiers : La Bourse
- Secteur médical : Créer de nouveaux médicaments et de nouvelles molécules
- Centres et laboratoires de recherche scientifiques
- De manière générale, l’ordinateur quantique s’avère être très utile lorsqu’il s’agit d’optimiser un traitement de données massives ou un calcul complexe. Ce qui va de pair avec l’explosion du « Big Data » que nous connaissons aujourd’hui.
- Cependant nous aurons toujours besoin de l’informatique classique « séquentielle ».
Les limites actuelles de l’ordinateur quantique
Tout d’abord, le système doit être complétement isolé car très sensible aux variations thermiques et magnétiques. L’ordinateur quantique doit donc être refroidi à des températures proches du zéro absolu (-273,15°). C’est la température de l’espace. A ce stade, les atomes ne bougent plus apparemment.
Ensuite, il est impossible de réaliser une copie de fichier comme en informatique séquentielle ou binaire. En effet toute copie, procédant d’une mesure sur la base des 0 et des 1, cette dernière effectuée sur un « qbit » détruirait l’essence même de la nature quantique de superposition des 0 et 1 ce qu’on appelle la décohérence quantique.
Et enfin, concernant le cryptage des données et donc la sécurité, un algorithme quantique qui existe déjà (l’algorithme de Shor) et s’il était utilisé sur un ordinateur quantique serait capable de casser les codes de manière ultra-rapide et donc de mettre le cryptage de toutes nos données en péril.
La course au « Graal Quantique »
Malgré tout cela, l’informatique quantique continue d’avancer dans une course à celui qui détiendra les clés de l’industrialisation (hardware, software). Google, Atos, IBM et Microsoft pour ne nommer que les plus grands, investissent depuis des années dans un des secteurs les plus disruptifs de notre temps. La transformation digitale que nous connaissons aujourd’hui n’a qu’à bien se tenir.
A l’heure où vous lisez cet article, IMB vient de lancer le Q Network. Notez plutôt dans lemondeinformatique.fr du 3 Janvier 2018 :
« Le Q Network fournit à ses participants une expertise ainsi qu’un accès cloud aux ressources d’informatique quantique de son système Q, en commençant avec une puissance de 20 qubits. La prochaine génération de système, actuellement au stade de prototype, donnera accès à un processeur de 50 qubits. « En travaillant étroitement avec nos clients, nous pouvons commencer à explorer ensemble les domaines sur lesquels les traitements quantiques, grands et petits, peuvent résoudre des problèmes jusqu’à présent insolubles dans des secteurs tels que les services financiers, l’automobile ou la chimie », a exposé courant décembre Dario Gil, vice-président de l’activité AI et IBM Q au sein d’IBM Research. »
Nous en sommes déjà à 20 qbits. Ce qui veut dire que la puissance équivaut à 400 fois un ordinateur classique de 20 « bits ».
J’espère vous avoir appris quelque chose comme j’ai appris moi-même en m’intéressant à ce sujet. Pour finir et vous détendre (tout est relatif), regardez aussi cette vidéo « The Sounds of IBM » : une plongée très étrange dans l’univers sonore d’un ordinateur quantique « méga géant ».
Note et Pour aller plus loin
*Vincent Rollet est l’auteur de l’excellent livre – La physique quantique (enfin) expliquée simplement – que je recommande à tous ceux qui souhaitent en découdre avec cette mystérieuse discipline.
http://www.mbadmb.com/wp-content/uploads/2018/01/livre-Rollet-1.jpg