Nous suivre Industrie Techno

Des algorithmes pour l'informatique quantique

Des algorithmes pour l'informatique quantique

© dr

L'acquisition par la Nasa et Google de l'ordinateur quantique D-Wave a braqué les projecteurs sur l'informatique quantique. Dans son dossier d'octobre, dédié aux matériaux qui font de la concurrence au silicium pour l'électronique, Industrie & Technologies évoque les matériaux capables de coder des qubits. Mais une fois l'état quantique stocké, encore faut-il pouvoir l'exploiter. C'est ce que permettent les algorithmes quantiques.

A quoi sert un ordinateur quantique ? « L’idée de l’ordinateur quantique est de remplacer un bit classique par un qubit. Un qubit peut avoir une “infinité de valeurs” qui, par analogie, pourrait être représentée par un point sur un cercle », décrypte Michael Monerau, jeune ingénieur du corps des Mines et auteur d’un article Algorithme quantique, de l’exponentiel au polynomial, écrit dans le cadre de ses études de mathématiques et d’informatique à l’ENS. Un qubit permet d’exprimer plus d’informations. « Au lieu d’avoir une valeur 0 ou 1, un qubit est un vecteur à deux composantes complexes, ainsi il peut prendre une infinité de valeur selon la valeur de chaque composante. » L’état quantique de n qubit (par exemple, un ensemble de particules intriquées de spin haut ou bas) est une superposition des 2n états de base. Ainsi pour 10 qubits, on a 210 amplitudes, soit 210 nombres complexes codés. Les chercheurs ont réussi à stocker des bits quantiques dans des vecteurs tels que l’électron, le photon ou les molécules, mais pour exploiter l’état quantique de ces bits, il faut aussi des algorithmes. Mais si une fois mesurée, le qubit ne prend qu’un des 210 états possibles, quel est l’avantage d’un qubit sur un bit classique ? C’est là que l’algorithme quantique entre en jeu.

Augmenter la probabilité de sélectionner la bonne réponse

La puissance additionnelle de l’ordinateur quantique est d’avoir une infinité de nuances intriquées entre les 2n axes de la base de calcul, au lieu de rester sur des composantes (0 ou 1) de l’ordinateur classique. « Le calcul balade le vecteur du qubit dans l’espace, et tant que dure le calcul, on ne peut pas connaître où se situe le point, c’est-à-dire la valeur. Quand on lit le résultat, la valeur est projetée sur un des axes de la base de calcul. La difficulté du calcul quantique, c’est qu’on ne peut pas lire la variable sans en modifier la valeur. Lorsqu'on veut la lire, on obtient nécessairement un seul des axes (ie. un vecteur avec 1 sur une composante et 0 sur toutes les autres). Le rôle de l’algorithme quantique est de faire circuler le point dans l’espace en le faisant converger assez proche d’un axe (valeur de réponse) afin de maîtriser la projection », continue Michael Monerau.

Il existe plusieurs algorithmes quantiques, dont les plus célèbres sont l’algorithme de Shor pour la factorisation et l’algorithme de Grover pour la recherche d’information. « L’algorithme de Grover amplifie la coordonnée pour qu’il y ait 99,9999% de chance d’obtenir la bonne réponse ». Pour la recherche d’une solution dans une liste non-triée, l’algorithme de Grover prend en compte la possibilité de tester toutes les solutions dans une superposition quantique. Tandis qu’un algorithme classique doit passer par s/2 (s, le nombre de solution possible) étapes, la méthode de Grover ne passe que par √s, – il s'agit de la compléxité "en moyenne"–. S’il y a 10000 solutions possibles, l’algorithme fera 100 étapes de calcul au lieu de 5000 avec un algorithme d’exécution linéaire.

Résolution des problèmes d’optimisation

Parmi les problèmes que pourraient résoudre l’informatique quantique, on compte les problèmes NP-Difficiles (polynomiale non-déterministe). L’exemple le plus connu de problème NP-Difficile est celui du voyageur du commerce, qui doit trouver l’itinéraire le plus court pour rejoindre chaque ville. Le temps de résolution augmentant avec le nombre de villes à visiter. L’algorithme quantique de Grover apporte une optimisation quadratique à ce type de problème.

Sophie Eustache

Bienvenue !

Vous êtes désormais inscrits. Vous recevrez prochainement notre newsletter hebdomadaire Industrie & Technologies

Nous vous recommandons

Bertin Nahum veut conquérir le monde avec ses robots chirurgicaux

Bertin Nahum veut conquérir le monde avec ses robots chirurgicaux

Portrait du PDG de Quantum Surgical, Bertin Nahum, qui prépare l’arrivée sur le marché de son prochain robot[…]

« En Europe, la difficulté n’est pas tant la création d’entreprises que leur croissance », selon Chahab Nastar, chef de l’innovation d’EIT Digital

Interview

« En Europe, la difficulté n’est pas tant la création d’entreprises que leur croissance », selon Chahab Nastar, chef de l’innovation d’EIT Digital

La maintenance à distance d’Oculavis récompensée à l’EIT Digital Challenge 2019

La maintenance à distance d’Oculavis récompensée à l’EIT Digital Challenge 2019

Pour bien commencer la semaine : L’étage supérieur d’Ariane 6 a son usine 4.0

Pour bien commencer la semaine : L’étage supérieur d’Ariane 6 a son usine 4.0

Plus d'articles