MATHÉMATIQUES
Le calcul quantique à l'assaut des équations linéaires
mathématiques - par Propos recueillis par Mathieu Nowak dans mensuel n°437 daté janvier 2010 à la page 18 (542 mots) | Gratuit
L'ordinateur quantique n'existe pas encore mais il apprend à faire de plus en plus de choses : des scientifiques viennent d'inventer un nouvel algorithme qui lui permettra de résoudre des grands systèmes d'équations linéaires. Pour Julia Kempe, il s'agit d'une nouvelle piste sur un terrain encore inexploré.
Des scientifiques anglo-saxons ont dévoilé un algorithme quantique pour résoudre des systèmes d'équations linéaires [1]. Est-ce une première dans le domaine du calcul quantique ?
J.K. Oui, c'est la première fois que l'on trouve un algorithme qui permettra à un ordinateur quantique de s'attaquer à la résolution d'équations linéaires. Cette publication a eu un grand retentissement car on rencontre des équations linéaires dans beaucoup de domaines, par exemple dans le traitement d'images, en météorologie, en biologie, etc. Les auteurs ont montré que leur approche peut conduire dans certains cas à des temps de calcul beaucoup plus courts que ceux nécessaires en faisant appel à des méthodes classiques de résolution de systèmes d'équations linéaires.
Comment obtiennent-ils ce gain ?
J.K. De la même façon que Peter Shor a obtenu en 1994 un algorithme quantique pour factoriser un nombre. Dans un algorithme quantique, l'information n'est pas codée avec des « 0 » et des « 1 » comme en informatique classique, mais avec des bits quantiques, ou qubits, qui peuvent prendre simultanément ces deux valeurs. Ensuite, l'idée développée ici est que, dans la pratique, il n'est pas toujours nécessaire d'avoir des solutions complètes aux problèmes. Pour résoudre des équations linéaires à N inconnues, la durée du calcul est ainsi ramenée à une valeur environ proportionnelle au logarithme de N, alors qu'avec les méthodes classiques il est proportionnel à N . C'est une prouesse car on obtient le résultat avec moins d'opérations qu'il ne faut pour écrire l'ensemble des paramètres ! La contrepartie est que cet algorithme ne permet pas de décrire le système en intégralité.
Comment ces limitations se traduisent-elles concrètement ?
J.K. Pour faire les calculs, on manipule des matrices et des vecteurs. Il faut d'abord que le vecteur soit donné comme un état quantique lire l'encadré « Le vecteur quantique ». Ensuite, on ne s'intéresse pas au vecteur entier mais à une approximation de certaines de ses propriétés, comme la somme de ses valeurs. Enfin, la matrice doit être d'un type particulier, avec beaucoup de valeurs nulles. Les auteurs appliquent alors une combinaison originale de méthodes déjà éprouvées dans le calcul quantique.
Dans quel contexte ce résultat s'inscrit-il ?
J.K. Les algorithmes dédiés au calcul quantique restent peu nombreux. Le plus célèbre est celui de Peter Shor, car il a remis en question toutes les méthodes actuelles de cryptographie - et il a déjà plus de 15 ans. En parallèle, d'autres chercheurs travaillent sur ce qu'on appelle la théorie de la complexité : ils cherchent à mettre en évidence ce qu'un ordinateur quantique ne saura jamais faire. Leurs travaux permettront de déterminer les bonnes approches en matière de sécurité pour la cryptographie.
On a besoin de nouveaux algorithmes. Plusieurs équipes tentent d'en mettre au point. Celui-ci, pour la résolution d'équations linéaires, n'est certes pas directement applicable en l'état mais il ouvre une porte pour des recherches à venir. Cela dit, quand on parle de calcul quantique, il faut avant tout garder à l'esprit que l'ordinateur quantique n'existe pas encore !
Par Propos recueillis par Mathieu Nowak
