Depuis le développement du numérique, les scientifiques cherchent à décupler sans cesse la puissance de calcul des ordinateurs. Après des années de recherche, une solution semble sortir du lot, l’informatique quantique.
Promettant une capacité de traitement hors du commun, cette révolution est signe de grand changement. Mais pour réaliser l’ampleur de ce changement, il est important de revenir aux concepts de bases et de comprendre ce qu’est un algorithme quantique.
Qu’est-ce qu’un algorithme ?
Le terme « algorithme » dérive du nom du grand mathématicien perse Al Khwarizmi, qui a vécu vers l’an 820. Essentiels en informatique, on les retrouve notamment en Data Science et dans le Machine Learning.Un algorithme est en fait une procédure par étapes. C’est un ensemble de règles à suivre pour accomplir une tâche ou résoudre un problème.
Bien avant l’émergence de l’informatique, les humains utilisaient en fait déjà les algorithmes. On peut considérer que les recettes de cuisine, les opérations mathématiques ou même la notice pour monter un meuble sont des algorithmes.
Dans le domaine de la programmation informatique, les algorithmes sont des ensembles de règles qui indiquent à l’ordinateur comment effectuer une tâche. En réalité, un programme informatique est un algorithme indiquant à l’ordinateur quelles étapes exécuter et dans quel ordre pour accomplir une tâche spécifique. Ils sont écrits à l’aide d’un langage de programmation.
On peut regrouper les algorithmes en 3 familles :
- Fondamentaux : ils ont des tâches bien définies, dont le résultat est facilement vérifiable.
- Optimisation : ils cherchent à identifier des paramètres ou une configuration qui maximise ou minimise une valeur (exemple : la meilleure recette de cuisine pour un plat).
- Cryptographiques : ils sont destinés à garantir la sécurité des communications et des transactions.
Qu’est-ce que l’informatique quantique ?
Tout d’abord, revoyons ce qu’est l’informatique classique. Cette pratique est basée sur le traitement de signaux binaires, un interrupteur à un traitement d’un bit en mémoire, soit 0 soit 1 : un registre de n bits équivaut donc à n valeurs. L’informatique classique traite chacune de ces valeurs de façon linéaire, les unes à la suite des autres, et donc plus le nombre de valeurs est grand, plus le temps de traitement est long.
En mécanique quantique, la manière de faire change profondément. Trois aspects de la mécanique quantique offrent la possibilité de faire de l’informatique quantique : la dualité onde-corpuscule, la superposition d’états et l’intrication.
De par leur nature onde-corpuscule, les particules quantiques sont décrites par des probabilités qui évoluent dans le temps et dans l’espace. Elles ont aussi la capacité de se trouver dans un état qu’on appelle « superposé » : un peu 0 et un peu 1. Ainsi, un qubit, la version quantique du bit traditionnel, possède deux états « d’existence », nommés |0> et |1>, prononcés : ket 0 et ket 1. Alors qu’un bit classique est numérique et a toujours pour valeur soit 0 soit 1, l’état d’un qubit est une superposition quantique linéaire de ses deux états de base, il vaut en même temps |0> et |1>. Néanmoins, si on cherche à l’observer, on va alors trouver soit un 0 ou un 1 : l’observation aura changé l’état de la particule en choisissant entre les deux. Un qubit observé se conduit alors comme un bit classique. Enfin, par l’intrication, on peut faire vivre en « couple » deux particules quantiques et rendre leur état quantique interdépendant. Cela est très utile pour tenter de suivre et comprendre l’évolution d’un qubit.
Avec un registre de n qubits, on a donc en même temps 2n valeurs, qui peuvent toutes être stockées simultanément (là où l’informatique classique ne peut stocker qu’une valeur à la fois). Si on arrive à faire des calculs avec de tels supports, on arrive en quelque sorte à faire tous les calculs en même temps, comme si on réalisait 2n calculs « en parallèle ». Par exemple, si n=3, un ordinateur quantique aura la possibilité de traiter 8 états quantiques différents, et donc 8 calculs en même temps. Si chaque calcul durait une seconde, un ordinateur quantique n’aurait donc besoin que de 1 seconde pour les réaliser, là où un ordinateur classique aurait eu besoin de 8 secondes, puisqu’il aurait dû traiter chaque calcul l’un après l’autre.
À la fin, il se peut qu’il n’y ait qu’un seul de ces calculs qui ait réussi, et c’est son résultat qui nous intéresse. La difficulté, c’est de l’isoler. C’est précisément le rôle des algorithmes quantiques : effacer de façon judicieuse tous les calculs qui n’ont pas abouti.
Comment fonctionne un algorithme quantique ?
Comme nous l’avons vu en informatique classique, un algorithme est un programme qui suit une suite logique d’instructions. En informatique quantique, la nature du traitement des instructions est changée, elle devient aussi quantique.
Comme la lecture du registre ne fournit qu’une valeur 0 ou 1 pour chaque bit (pour rappel, un qubit observé se fige dans un état donné et se comporte comme un bit classique), soit un des états de base du registre, tout l’art de l’algorithmique quantique consiste à concentrer l’évolution vers les états qui donnent la solution au problème étudié.
Un ordinateur quantique n’est donc pas une machine qui résoudrait tous les problèmes plus rapidement qu’un ordinateur conventionnel. Il s’agit plutôt d’une machine capable de résoudre efficacement certains problèmes hors de portée des machines conventionnelles. L’exercice consiste donc à comparer la complexité d’un problème d’un point de vue classique et d’un point de vue quantique. Si un algorithme peut être résolu de manière classique avec une complexité bien définie, il peut aussi l’être dans le modèle quantique avec une complexité équivalente ou moindre.
Les capacités de l’algorithmique quantique sont reliées au nombre de qubits, mais augmenter leur nombre ne sert que si « l’environnement » quantique est maintenu malgré les inévitables processus de décohérence. Une autre particularité du qubit par rapport à un bit classique est qu’il ne peut pas être dupliqué en raison des lois de la physique quantique.
Quel est l’intérêt de créer un algorithme quantique ?
Les algorithmes quantiques ont le potentiel de révolutionner de nombreux domaines, dont la cryptographie, la chimie computationnelle, la recherche opérationnelle et même l’intelligence artificielle. L’un des exemples les plus marquants est l’algorithme de factorisation de Shor, qui menace les systèmes de cryptographie à base de factorisation et met en lumière la nécessité de développer des méthodes de chiffrement quantique plus robustes.
En ce qui concerne la Data Science, les algorithmes quantiques représentent un grand potentiel dans ce domaine. Ils pourraient accélérer des tâches complexes telles que l’optimisation, l’apprentissage automatique et la simulation moléculaire. De plus, ils pourraient améliorer la sécurité des données grâce à la cryptographie quantique. Cependant, leur utilisation en data science est encore en développement en raison des défis technologiques actuels. Malgré cela, leur capacité à résoudre des problèmes difficiles rapidement offre des opportunités prometteuses pour l’avenir de l’analyse de données.
