«Pour les problèmes de très petite taille, un ordinateur classique est plus rapide»

Les ordinateurs quantiques promettent d'être capables de résoudre certains problèmes de calcul beaucoup plus rapidement que les ordinateurs classiques. Dans quelle mesure cela est-il vrai, ou du moins réaliste ?
Torsten Hoefler : En général, cette affirmation est vraie. Les ordinateurs quantiques peuvent en effet résoudre certains problèmes de calcul beaucoup plus rapidement que les ordinateurs classiques. Je dirais qu'ils sont réellement capables de réduire le temps de calcul de décennies ou d'années à des heures, voire à des minutes. Bien que cela soit vrai, ce n'est pas réaliste pour tous les problèmes de calcul.

Pour quels problèmes les ordinateurs quantiques ne sont-ils pas plus rapides ?
Par exemple, si nous voulons accélérer les prévisions météorologiques ou les simulations climatiques, je ne saurais pas aujourd'hui comment accélérer considérablement ces applications avec un ordinateur quantique. De la même manière, je ne saurais pas comment accélérer considérablement l'apprentissage automatique avec un ordinateur quantique aujourd'hui. De même, pour la dynamique des fluides dans les régimes turbulents, nous ne parviendrons probablement pas à obtenir des avantages pratiques avec les algorithmes quantiques actuels dans un avenir prévisible.

Voyez-vous des domaines d'application dans la recherche fondamentale ou dans l'industrie où les ordinateurs quantiques pourraient présenter leurs avantages dans un avenir proche ?
Jusqu'à présent, nous savons avec certitude que l'informatique quantique est extrêmement pertinente pour un large éventail de recherches et de développements. Je pense à des problèmes tels que la rupture des schémas cryptographiques connus basés sur la factorisation des nombres premiers. Ou encore, lorsqu'il s'agit de simuler des systèmes chimiques avec une très grande précision, l'informatique quantique a un potentiel d'impact incroyable.
En outre, l'informatique quantique est très prometteuse pour des domaines de recherche tels que la simulation des propriétés des matériaux dues aux effets quantiques, les nouveaux médicaments du futur, l'invention de nouveaux engrais ou la compréhension du fonctionnement des systèmes biologiques. Dans tous ces domaines, les ordinateurs quantiques peuvent jouer un rôle crucial en accélérant les temps de calcul.

Mais il s'agit encore d'une vision d'avenir ?
Oui, mais même si l'informatique quantique n'est pas encore applicable à toutes les questions ouvertes dans ces domaines, nous voyons clairement une voie vers une meilleure exploitation du potentiel des ordinateurs quantiques. Mais ce n'est pas vrai pour tous les algorithmes. Il ne suffit pas de prendre n'importe quel algorithme, de l'exécuter sur un ordinateur quantique pour que les calculs deviennent automatiquement plus rapides. En principe, les ordinateurs quantiques peuvent résoudre n'importe quel problème de calcul, mais la question décisive pour leur application est de savoir quels problèmes ils peuvent pratiquement résoudre plus rapidement ou à moindre coût que les ordinateurs classiques.

Dans quelle mesure révisez-vous l'hypothèse selon laquelle les ordinateurs quantiques sont toujours plus rapides que les ordinateurs classiques ?
Certaines et certains pensent que les ordinateurs quantiques sont fondamentalement plus rapides parce qu'ils sont capables de résoudre de nombreux problèmes en un nombre d'étapes quadratiquement inférieur. Mais une seule étape de calcul quantique est beaucoup plus lente qu'une étape classique. En raison des principes de la mécanique quantique tels que la superposition, l'interférence ou l'enchevêtrement, moins d'étapes de calcul sont nécessaires pour résoudre un problème donné. C'est la raison pour laquelle les ordinateurs quantiques promettent de résoudre certains problèmes plus rapidement que les ordinateurs classiques. Néanmoins, il serait faux de croire que les ordinateurs quantiques peuvent résoudre n'importe quel problème beaucoup plus rapidement que les ordinateurs classiques.

Pourquoi ?
Compte tenu de la conception actuelle de l'informatique quantique, chaque étape de calcul sera plus lente que l'étape classique correspondante. Cela est dû à la grande complexité de la correction d'erreurs et d'autres effets de système dans l'informatique quantique actuelle. En outre, dans l'informatique classique, l'industrie a fait évoluer les technologies depuis 60 ans au point qu'elles sont devenues extrêmement rapides. Aujourd'hui, un ordinateur classique peut exécuter des millions, voire des milliards d'étapes par seconde. Un ordinateur quantique, quant à lui, ne peut exécuter que des centaines de milliers, voire des millions d'étapes par seconde. C'est pourquoi l'informatique quantique n'est pas intrinsèquement supérieure dans tous les cas. C'est cette idée fausse d'une suprématie quantique globale que nous essayons de dissiper. Néanmoins, je suis très optimiste quant à la construction d'ordinateurs quantiques fiables.

Quelles conclusions scientifiques avez-vous tirées de votre étude ? Pour quels types de problèmes les ordinateurs quantiques ont-ils le plus de chances d'être plus rapides ?
Nous avons comparé les performances d'une puce classique leader sur le marché à celles d'une puce quantique conçue de manière optimiste, chacune pour le même problème. De cette manière, nous sommes les premiers à avoir identifié ce qui est exactement nécessaire pour que les ordinateurs quantiques obtiennent un réel avantage en termes de vitesse. Notre analyse montre que pour pratiquement tous les algorithmes, l'ordinateur classique est plus rapide pour les problèmes de très petite taille et l'ordinateur quantique est plus rapide pour les problèmes de très grande taille.

En effet, le temps nécessaire pour résoudre certains problèmes sur un ordinateur quantique croît plus lentement avec la taille des problèmes que sur les ordinateurs classiques. C'est ce que nous appelons l'accélération quantique. Nous constatons également qu'en général, les ordinateurs quantiques sont comparativement plus rapides et plus pratiques pour les problèmes de gros calculs sur de petites données, mais qu'ils ne sont pas pratiques pour les problèmes de grosses données.

En raison des limitations de la bande passante d'entrée et de sortie, les ordinateurs classiques calculent plus rapidement les données volumineuses. En outre, les ordinateurs classiques résolvent également un problème de recherche dans une base de données plus rapidement qu'un ordinateur quantique. C'est pourquoi l'informatique quantique a fait l'objet d'une fausse publicité dans le contexte du big data.

L'une de vos conclusions est que la vitesse quadratique n'est pas suffisante pour que les ordinateurs quantiques tirent réellement parti de leurs avantages potentiels en termes de vitesse.
Dans notre étude, nous montrons que les accélérations quadratiques, qui réduisent le temps de calcul en prenant la racine carrée du temps d'exécution d'un algorithme, sont insuffisantes pour obtenir un avantage quantique pratique dans un avenir prévisible. Nous constatons que si seule une accélération quadratique est mise en œuvre, pour de nombreux problèmes, le calcul quantique prendra encore plusieurs mois, ce qui serait trop lent et trop coûteux dans la pratique.

Nous en déduisons qu'il faut au moins des accélérations cubiques ou quartiques basées sur les troisième et quatrième racines, car ce n'est qu'à ce moment-là que des milliers ou des millions d'opérations de calcul sont possibles. Mais même les accélérations cubiques ou quartiques ne représentent que l'exigence la plus basse. Il est nécessaire de se concentrer sur les accélérations exponentielles, où le temps d'exécution de l'algorithme quantique est le logarithme du temps d'exécution de l'algorithme classique. Par conséquent, les candidats les plus prometteurs pour obtenir de réels avantages quantiques pratiques sont les problèmes à petites données avec une accélération exponentielle.

Que faut-il faire différemment pour parvenir à une véritable informatique quantique à grande vitesse ?
Des algorithmes quantiques plus novateurs constituent une clé décisive pour atteindre la vitesse quantique. Sans améliorations algorithmiques significatives, il est peu probable qu'un large éventail d'applications souvent citées se traduise par un avantage quantique pratique. D'un point de vue pratique, la plupart des algorithmes quantiques dont nous disposons aujourd'hui ne permettent pas de véritables accélérations quantiques.

Même si nous savons que les algorithmes cubiques, quartiques ou exponentiels entraînent des accélérations quantiques plus importantes que les algorithmes quadratiques, la situation réelle est qu'aujourd'hui, nous ne connaissons tout simplement pas beaucoup d'algorithmes d'accélération cubiques ou quartiques. Actuellement, de nombreux algorithmes d'accélération quantique reposent sur l'accélération quantique quadratique, basée sur le célèbre algorithme de Grover.

Nous pensons qu'il ne suffit pas de concevoir davantage d'algorithmes de type Grover. Pour développer de nouveaux algorithmes quantiques qui fassent vraiment la différence, la recherche algorithmique doit se concentrer sur des algorithmes qui permettent une accélération quantique élevée dans la pratique. Sinon, les ordinateurs quantiques pourraient ne pas surpasser les dispositifs les plus rapides des ordinateurs classiques.

Qu'attend-on des infortmaticiennes et informaticiens pour obtenir une véritable accélération quantique ?
Nous devons inventer de nouveaux algorithmes quantiques à grande vitesse. Le grand défi est que nous ne disposons aujourd'hui que d'une poignée d'algorithmes quantiques fondamentaux, comme l'algorithme de Grover ou l'algorithme de Shor, qui sont largement utilisés en chimie ou en cryptographie. Il est évidemment très difficile de développer de nouveaux algorithmes fondamentaux. La mécanique quantique étant un concept mathématique complexe, comprendre comment la traduire en algorithmes quantiques utiles est une véritable entreprise. En règle générale, un algorithme fondamental est développé tous les dix ans environ.

Quelles sont les prochaines étapes dans la conception d'algorithmes quantiques, en particulier à l'ETH Zurich ?
Nous avons besoin de plus d'informaticiens et informaticiennes et de mathématiciennes mathématiciens pour rechercher de nouveaux algorithmes quantiques. Jusqu'à présent, il est très difficile de trouver d'excellents scientifiques spécialisé·es dans les algorithmes quantiques. Une grande opportunité consiste à combiner ce besoin avec la mission d'enseignement de l'ETH Zurich et à encourager la prochaine génération de scientifiques à se plonger dans la conception d'algorithmes quantiques. Et le fait de disposer d'un Quantum Center nous permet de regrouper naturellement des mathématiciens et mathématiciennes, des informaticiennes et informaticiens autour de physiciens et physiciennes et d'ingénieur·es pour collaborer sur les ordinateurs quantiques. C'est une opportunité pour l'ETH Zurich.