Fin octobre 2018, une vingtaine de projets ont été sélectionnés dans le cadre du grand programme européen de recherche sur l’ordinateur quantique. Parmi ces projets, qui se partageront un budget de 132 millions d’euros, deux ont pour ambition de construire un ordinateur quantique. Mais, aujourd’hui encore, la supériorité d’un ordinateur quantique vis-à-vis de son alter ego classique est loin d’être évidente. Robert König, de l’université technique de Munich, et deux collègues du centre de recherche IBM, à New York, viennent d’établir la première preuve formelle de la supériorité d’un ordinateur quantique, dans une configuration bien particulière. Sean Bailly Pour la Science, janvier 2019.
Vue d’artiste d’un ordinateur quantique. Shutterstock.com/plotplot
L’idée de l’ordinateur quantique est d’exploiter certains principes fondamentaux de la physique quantique, notamment la superposition des états. Ainsi, tandis qu’un bit d’information classique ne peut prendre que la valeur 0 ou 1, un bit quantique, ou qubit, est dans une superposition de l’état 0 et 1. Les propriétés de ce type d’état laissent penser qu’il est possible d’augmenter les capacités et la vitesse de traitement de l’information. L’inconvénient est que ces états superposés sont fragiles et sont détruits par la moindre interaction avec leur environnement. Leur maîtrise technique est encore un immense défi.
Mais, plus surprenant, la démonstration de la supériorité de l’ordinateur quantique sur l’ordinateur classique pour résoudre des problèmes réels n’est pas non plus formellement établie, même si certains arguments le suggèrent. Par exemple, l’algorithme quantique de Shor pour factoriser les nombres en nombres premiers est plus efficace que tous les algorithmes classiques connus. Cependant, cet argument repose sur une hypothèse forte et non démontrée : on pense qu’il n’est pas possible de concevoir un algorithme de factorisation classique dont le temps de calcul augmenterait comme une fonction polynomiale de la longueur du nombre à factoriser. Si un tel algorithme polynomial existait, il serait aussi performant que la version quantique de Shor. Or cette hypothèse pourrait un jour être contredite.
Il existe une autre classe d’algorithmes quantiques, fondés sur un « oracle », une sorte de boîte noire, et notamment utilisés dans la recherche d’éléments au sein d’une liste, comme par exemple l’algorithme de Grover. En théorie, l’utilisation des effets de superposition quantique accélère la recherche, mais il n’est pas prouvé qu’une implémentation physique concrète d’un tel algorithme soit effectivement plus rapide qu’un algorithme classique.
Pour mettre en évidence l’avantage des algorithmes quantiques, Robert König et ses collègues ont étudié un algorithme particulier qui effectue des opérations sur une chaîne de bits classiques pour résoudre certains problèmes d’algèbre linéaire. Le temps d’exécution de cet algorithme dans un ordinateur quantique ne dépend pas de la taille de la chaîne de données en entrée. On parle dans ce cas de « circuit quantique à profondeur constante », la profondeur définissant d’une certaine façon le nombre d’étapes de calcul dans l’algorithme.
Les trois chercheurs ont alors démontré qu’il est impossible de résoudre les mêmes problèmes avec un ordinateur classique, car ce dernier requiert une profondeur croissante si la quantité de données en entrée augmente.
Pour Benoît Valiron, du laboratoire de recherche en informatique, à Orsay, et spécialiste de l’informatique quantique, « ce résultat est intéressant même s’il est très théorique et sans applications pratiques, du moins dans l’immédiat ». En effet, les circuits classiques à profondeur constante ont peu d’utilité en pratique, si ce n’est comme outil pour caractériser la complexité d’un algorithme. Le chercheur ajoute cependant que « là où ce résultat entre en résonance avec des choses éventuellement plus concrètes, c’est dans le fait que les circuits à profondeur constante (et faible) seront probablement les premiers systèmes que l’on sera capable de réaliser sur des processeurs quantiques. Or, mettre au point des algorithmes à implémenter dans un ordinateur quantique et valider leur caractère quantique est un domaine de recherche actif. Ce résultat peut fournir une piste dans cette direction.
Commentaires récents