L'informatique quantique et l'avenir du calculable

En 2007, un spot publicitaire a été diffusé en Australie. On y voyait deux mannequins discuter de mécanique quantique dans leur loge. Ce qui est intéressant, selon elles, c'est que contrairement à ce qui se passe habituellement en physique, elle ne parle pas de matière, d'énergie ou d'ondes, mais d'information, de probabilités et de grandeurs d'observation.

Ce qui est remarquable dans ce film publicitaire, ce n'est pas que deux mannequins discutent d'une théorie de la physique, mais plut?t que le film présente la mécanique quantique non seulement comme une perspective de recherche intéressante pour la physique, mais aussi pour l'informatique. Cette position scientifique n'était pas aussi répandue il y a douze ans qu'elle ne l'est aujourd'hui, car l'informatique quantique se développe rapidement et se trouve également à l'ETH Zurich. en dehors de la physique..

Depuis, une série d'expériences, dont certaines menées par des chercheurs de l'ETH, ont pu démontrer que la construction d'ordinateurs fonctionnant selon les principes de la mécanique quantique est en principe possible - il existe différentes technologies à cet effet et, depuis quelque temps, il y a une véritable compétition pour savoir qui pourra construire le premier ordinateur quantique (voir Globe 2/2018).

Précurseurs et gardiens de zoo des complexités

Scott Aaronson, professeur d'informatique et directeur fondateur du Quantum Information Center de l'Université du Texas à Austin, est un informaticien qui ne cesse de présenter des arguments originaux sur la manière dont les ordinateurs quantiques pourraient un jour résoudre des problèmes trop complexes pour les ordinateurs actuels. Le dialogue des modèles est donc une seule citation littérale, que l'on peut lire dans son livre "Le calcul quantique depuis Démocrite".

"Ce qui est typique de Scott Aaronson, c'est qu'il réfléchit au-delà du modèle informatique classique et se demande, de manière très fondamentale, quels types d'ordinateurs sont probablement capables de résoudre plus de problèmes que les ordinateurs actuels", explique le professeur de l'ETH Renato Renner. Le physicien est un spécialiste de la théorie de l'information quantique. Il a lui-même déjà débattu intensivement avec Aaronson sur son blog (cf. c?té externeDiscussion sous "Responses"). De son c?té, Aaronson a déjà été invité par le passé à l'ETH Zurich, par exemple au Colloque de physique de Zurich 2009.

On a déjà donné à Scott Aaronson un "c?té externeComplexonautesAaronson a été surnommé "l'expert en informatique" parce qu'il s'est aventuré jusqu'aux problèmes les plus complexes pour explorer les possibilités et les limites de principe des ordinateurs, qu'il s'agisse d'ordinateurs tels que nous les connaissons aujourd'hui, d'ordinateurs quantiques ou de types d'ordinateurs tout à fait différents que l'on ne peut presque pas encore imaginer aujourd'hui. Dans son fameux "c?té externeZoo des complexités"il regroupe différentes classes de problèmes de manière à ce que l'on puisse voir à quel point les ordinateurs sont respectivement capables de calculer et de résoudre ces problèmes.

Quoi qu'il en soit, Scott Aaronson est un chercheur qui aime se poser des questions importantes et fondamentales. Ainsi, à Zurich, où il se produira dans le cadre des Bernays Lectures 2019, il discutera de trois questions clés de l'informatique théorique et de la physique.

1. Que peuvent calculer les ordinateurs en général et dans quelle mesure les nouvelles découvertes de la physique quantique étendent-elles les capacités de calcul des ordinateurs ?
2. Existe-t-il des problèmes que les nouveaux types d'ordinateurs, comme les ordinateurs quantiques, calculent plus rapidement et plus efficacement que les ordinateurs actuels ? Existe-t-il même certains problèmes particulièrement complexes que seuls les ordinateurs quantiques ou d'autres ordinateurs futurs pourront résoudre ?
3. Est-il possible de fabriquer des ordinateurs quantiques utiles, et quel est l'état actuel des différentes approches pour construire un ordinateur quantique ?

Les réflexions d'Aaronson commencent par les bases théoriques et la "thèse de Church-Turing". Cette thèse centrale de la science informatique remonte aux mathématiques et aux pionniers de l'informatique Alonzo Church (1903-1995) et Alan Turing (1912-1954). En simplifiant à l'extrême, elle stipule que tous les problèmes pour lesquels on peut intuitivement imaginer et formuler une solution sont également calculables sur un ordinateur. Ainsi, tous les problèmes que les modèles informatiques actuels sont en principe capables de calculer peuvent en principe être résolus par les ordinateurs actuels.

Les ordinateurs quantiques résolvent-ils davantage de problèmes ?

Tout le monde ? Pas tout à fait. Il existe aussi des problèmes qui peuvent en principe être calculés et résolus, mais qui prendraient beaucoup trop de temps à un ordinateur pour les calculer. Les informaticiens qualifient d'inefficaces les problèmes que les ordinateurs ne peuvent pas résoudre dans un délai raisonnable.

Typiquement, de nombreux phénomènes de la physique quantique ne peuvent pas être calculés efficacement aujourd'hui. C'est pourquoi tant les physiciens que les informaticiens cherchent à savoir si les ordinateurs quantiques pourraient résoudre efficacement plus de problèmes que les ordinateurs conventionnels. "En l'état actuel des connaissances, presque tout le monde s'accorde à dire que les ordinateurs quantiques calculent plus vite que les ordinateurs classiques. Mais personne n'a encore pu le prouver. C'est pourquoi cette hypothèse fait partie des grandes questions de la science informatique", explique Renato Renner, qui présentera Scott Aaronson aux Paul Bernays Lectures.

Il existe des contre-arguments : La thèse de Church-Turing affirme que tous les problèmes solubles peuvent être résolus sur un ordinateur classique. Son extension affirme que tous les problèmes pouvant être résolus efficacement le sont également sur un ordinateur classique. On sait qu'un ordinateur classique peut simuler un ordinateur quantique - mais pas de manière efficace.

Si l'on parvient à simuler efficacement un ordinateur quantique sur un ordinateur classique, alors un ordinateur classique pourrait résoudre les mêmes problèmes qu'un ordinateur quantique - et alors, inversement, aucun ordinateur quantique ne pourrait résoudre des problèmes fondamentalement différents de ceux d'un ordinateur classique. Aaronson lui-même argumente dans l'autre sens.

Cryptage et gravitation

Un exemple bien connu, pour lequel on ne conna?t aujourd'hui aucun algorithme capable de le calculer efficacement pour les ordinateurs classiques, concerne la factorisation, c'est-à-dire la décomposition d'un grand nombre composé en différents diviseurs. "Dans le cas de la factorisation, il existe toutefois des algorithmes qui peuvent résoudre efficacement ce problème. Mais ceux-ci ne fonctionnent que sur un ordinateur quantique", explique Renner. ?tant donné que les techniques actuelles de cryptage et de sécurité sur Internet reposent sur le problème de la factorisation, Aaronson mène également des recherches sur les aspects liés à la sécurité. c?té externeImplications des ordinateurs quantiques.

En ce qui concerne l'avenir de l'ordinateur, Aaronson et Renner voient encore plus loin : peut-être y aura-t-il un jour des ordinateurs tout à fait différents, qui utiliseront d'autres phénomènes physiques que la mécanique quantique ? La théorie de la gravitation par exemple. On pourrait alors peut-être même résoudre des problèmes que même les ordinateurs quantiques ne peuvent pas résoudre efficacement ?