Des algorithmes pour l'informatique quantique

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.

Partager
Des algorithmes pour l'informatique quantique

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

SUR LE MÊME SUJET

PARCOURIR LE DOSSIER

Tout le dossier

Sujets associés

NEWSLETTER L'hebdo de la techno

Nos journalistes sélectionnent pour vous les articles clés de l'innovation technologique

Votre demande d’inscription a bien été prise en compte.

Votre email est traité par notre titre de presse qui selon le titre appartient, à une des sociétés suivantes...

Votre email est traité par notre titre de presse qui selon le titre appartient, à une des sociétés suivantes du : Groupe Moniteur Nanterre B 403 080 823, IPD Nanterre 490 727 633, Groupe Industrie Service Info (GISI) Nanterre 442 233 417. Cette société ou toutes sociétés du Groupe Infopro Digital pourront l'utiliser afin de vous proposer pour leur compte ou celui de leurs clients, des produits et/ou services utiles à vos activités professionnelles. Pour exercer vos droits, vous y opposer ou pour en savoir plus : Charte des données personnelles.

LES ÉVÉNEMENTS L'USINE NOUVELLE

Tous les événements

LES PODCASTS

A Grasse, un parfum de renouveau

A Grasse, un parfum de renouveau

Dans ce nouvel épisode de La Fabrique, Anne Sophie Bellaiche nous dévoile les coulisses de son reportage dans le berceau français du parfum : Grasse. Elle nous fait découvrir un écosystème résilient, composé essentiellement...

Écouter cet épisode

Les recettes de l'horlogerie suisse

Les recettes de l'horlogerie suisse

Dans ce nouvel épisode de La Fabrique, notre journaliste Gautier Virol nous dévoile les coulisses de son reportage dans le jura suisse au coeur de l'industrie des montres de luxe.

Écouter cet épisode

Le rôle des jeux vidéo dans nos sociétés

Le rôle des jeux vidéo dans nos sociétés

Martin Buthaud est docteur en philosophie à l'Université de Rouen. Il fait partie des rares chercheurs français à se questionner sur le rôle du jeu vidéo dans nos sociétés.

Écouter cet épisode

Les coulisses d'un abattoir qui se robotise

Les coulisses d'un abattoir qui se robotise

Dans ce nouvel épisode de La Fabrique, Nathan Mann nous dévoile les coulisses de son reportage dans l'abattoir Labeyrie de Came, dans les Pyrénées-Atlantiques, qui robotise peu à peu ses installations.

Écouter cet épisode

Tous les podcasts

LES SERVICES DE L'USINE NOUVELLE

Trouvez les entreprises industrielles qui recrutent des talents

Safran

Ingénieur-e Assurance Qualité Matériaux et Procédés Spéciaux

Safran - 19/11/2022 - CDI - Vélizy-Villacoublay

+ 550 offres d’emploi

Tout voir
Proposé par

Accédez à tous les appels d’offres et détectez vos opportunités d’affaires

40 - Landes

Analyses eau et poisson.

DATE DE REPONSE 22/12/2022

+ de 10.000 avis par jour

Tout voir
Proposé par

ARTICLES LES PLUS LUS