2.1. Algorithmique, preuves, complexité (Michel de Rougemont)

1Un modèle de calcul spécifie des opérations élémentaires, à partir desquelles on définit des algorithmes qui décrivent explicitement leur assemblage. L’entrée d’un problème est une structure finie, par exemple un mot, une liste, un arbre, un graphe ou une structure plus élaborée. Si le résultat est booléen, 0 ou 1, il s’agit d’un problème de décision, alors que si le résultat est une autre structure, c’est un problème de calcul. Dans les deux cas, la complexité s’intéresse au nombre d’opérations élémentaires nécessaires pour résoudre le problème. Différentes mesures peuvent être considérées, en fonction de la taille n d’une entrée x. La complexité dans le pire des cas (worst-case), prend en compte le nombre maximum d’opérations, alors que la complexité en moyenne (average-case) considère le nombre moyen d’opérations, pour les entrées de taille n tirées selon une distribution.

2S’il existe un algorithme qui résout un problème A, et dont le nombre d’étapes élémentaires pour des entrées de taille n, est borné par c.n pour une constante c, on dit que l’algorithme est de complexité O(n) en temps et que le problème est de complexité linéaire ou O(n). Un algorithme efficace pour un problème de décision produit indirectement une preuve du fait que l’entrée x satisfait une propriété, à l’aide d’opérations élémentaires relatives au modèle de calcul. La théorie de la complexité cherche à classifier les problèmes, pour un modèle de calcul donné, et ainsi déterminer pour deux problèmes A et B si A est plus facile que B, A est équivalent à B, ou A est plus difficile que B. Cette théorie a permis depuis les années 1970 une première classification, qui s’est par la suite enrichie de nombreuses notions d’approximation qui la modifient sensiblement. Les données informatiques ne sont pas toujours exactes et les calculs approchés sont souvent plus robustes aux erreurs et donc plus importants en pratique.

3Depuis les années 1970, les deux principales classes de complexité sont P, la classe des problèmes décidables en temps polynomial et NP la classe des problèmes vérifiables en temps polynomial. Cette approche se généralise (Lassaigne, Rougemont, 2004) aux problèmes de calcul, c’est-à-dire au calcul d’une fonction f(x) = y, aux problèmes d’optimisation de type Max f(x) et aux problèmes de comptage, autrement dit, à la détermination du nombre de x tels que f(x) = 1, noté #f(x).

4Lorsque ces problèmes sont difficiles, c’est-à-dire n’admettent pas de solution exacte en temps polynomial, il est possible de trouver une approximation de f(x), de Max f(x) ou de # f(x). Les algorithmes probabilistes sont souvent très adaptés pour approcher ces problèmes avec grande probabilité. Un tel algorithme tire au hasard des valeurs aléatoires, 0 ou 1 avec probabilité ½, et définit un espace probabiliste, où chaque état a une probabilité de (½)ⁿ s’il y a n tirages. Dans le cas d’un problème d’optimisation, on souhaite obtenir une solution A(x, ε) qui approxime le maximum à ε près avec grande probabilité, i. e. telle que la probabilité que A(x, ε) soit dans l’intervalle [(1-ε). Max f(x), (1+ε). Max f(x)] soit plus grande que 1 – δ. Un tel algorithme d’approximation est aussi appelé un estimateur (ε, δ). Un algorithme quantique généralise cette approche lorsque les valeurs aléatoires sont quantiques, c’est-à-dire sont des valeurs complexes sur le cercle unité.

5De tels algorithmes produisent des solutions qui sont garanties par l’analyse probabiliste de l’algorithme, et indirectement des preuves non-constructives. Dans le cas du problème SAT, la satisfaisabilité de m clauses booléennes à n variables, MAXSAT est le problème d’optimisation associé définissant le plus grand nombre de clauses satisfaisables et #SAT le nombre de valuations qui satisfont toutes les clauses. Le problème MAXSAT est approximable alors que le problème #SAT ne l’est pas. Depuis une vingtaine d’années, le développement des algorithmes probabilistes a permis d’éclairer les rapports entre approximation et complexité. Grâce à la complexité descriptive, introduite à partir des années 1980, on comprend mieux les classes de problèmes qui, bien que difficiles, admettent des solutions approximatives pour différentes notions d’approximation, généralisant la notion d’estimateur.

6Les algorithmes probabilistes utilisés en pratique concernent des problèmes difficiles ou des problèmes polynomiaux pour lesquels la solution déterministe est plus complexe que la solution probabiliste, comme le test de primalité. Ces algorithmes se révèlent très utiles et efficaces pour les problèmes de vérification que nous détaillons et pour les problèmes de calcul dans des situations incertaines (Fischer, 2001).

2.1.1. Un exemple simple : la distance d’édition sur les mots

7Considérons deux mots binaires W et W’ de longueur n et n ’. La distance d’édition entre deux mots est le nombre minimum d’insertions et d’effacements de caractères (0 ou 1) qui permettent de transformer W en W’. On peut généraliser cette distance en introduisant une nouvelle opération, le déplacement, qui consiste à sélectionner, dans un mot, un sous-mot de longueur arbitraire et une position, puis de déplacer en une étape le sous-mot vers cette position. On obtient alors un nouveau mot de même longueur. La distance d’édition avec déplacements entre W et W’ est le nombre minimum d’insertions, d’effacements et de déplacements qui permettent de transformer W en W’.

8Un problème fondamental est de calculer cette distance d’édition. C’est un problème P-calculable (calculable en temps polynomial) dans le cas de la distance d’édition et NP-complet dans le cas de la distance d’édition avec déplacements. On pourrait en conclure que le problème de la distance d’édition avec déplacements est plus difficile que celui de la distance d’édition classique. Pourtant, si on cherche à approcher ces distances à ε près, la situation est inverse. On peut approcher la distance d’édition avec déplacements en temps indépendant de n, dépendant uniquement de ε (par exemple O(1/ε³)), c’est-à-dire sans lire complètement les mots W et W^’, mais uniquement en les échantillonnant. Par contre, on ne peut pas approcher la distance d’édition classique en temps indépendant de n. L’algorithme d’approximation est aussi robuste au bruit et nous permet de conclure que la distance d’édition avec déplacements est très facile à calculer.

9Les notions d’approximation dans le cadre de bonnes distances sur les objets informatiques permettent souvent des gains exponentiels en temps de calcul, utilisant la structure des données, mais sans modifier le modèle de calcul. Ces algorithmes efficaces peuvent produire en temps constant une preuve indirecte du résultat, sans lire complètement l’entrée du problème.

2.1.2. La vérification de fonctions

10Pour une fonction unaire f, la vérification consiste à décider étant donné x, y sif(x) = y. Sif est la fonction d’inversion matricielle, la vérification prend en entrée deux matrices carrées A, B et décide si B = A^-1, problème beaucoup plus simple que le problème de calcul. En 1985 est apparu le modèle IP des preuves interactives qui combine choix probabiliste et interaction. On peut dans ce modèle vérifier la fonction Permanent d’une matrice (n, n) après n interactions et tout problème PESPACE admet une preuve interactive de taille polynomiale. Dans un autre modèle, dit PCP (Probabilistic Checkable Proofs), on cherche à vérifier sans interaction une preuve transparente ou holographique qui amplifie les erreurs. Tout problème NP admet ainsi une preuve holographique qui teste un nombre fini de positions dans cette preuve.

11Le test de propriété, introduit par Goldreich et al. (1998), Rubinfeld et Sudan (1996), présenté aussi dans Fischer (2001), est une autre notion de vérification qui introduit deux relaxations, une probabiliste et une autre combinatoire. Étant donné une distance sur les objets considérés (fonctions dans ce cadre), un ε-test pour la propriété accepte tout objet satisfaisant, et refuse, avec grande probabilité, tout objet ε-loin de ceux satisfaisant la propriété. Ces relaxations rendent possible la vérification en temps constant d’une multitude de propriétés, même NP-complètes. Citons pour les graphes, les propriétés de k-coloriabilité, r-clique, r-cut, ou plus généralement du premier ordre de type Σ₂ c’est-à-dire de la forme ∃x₁... ∃x_k.y₁... y₁R(x₁,..., x_k, y₁,..., y₁). Pour d’autres propriétés la vérification n’est pas en temps constant, mais reste plus efficace que le meilleur algorithme (non-relâché) connu. Citons les lois de composition interne, l’associativité ou le fait d’être une loi de groupe.

2.1.3. La vérification de programmes

12La vérification de programmes consiste à décider si un programme P satisfait une propriété Ψ. De nombreuses approches existent et nous considérons uniquement deux techniques : les Testeurs et le Model-Checking. Les testeurs et correcteurs ont été introduits par M. Blum en 1984 en considérant un programme comme une boîte noire et en appliquant le principe d’un ε-testeur. Une classe de programmes résolvant par exemple les problèmes d’algèbre linéaire peut être ainsi vérifiée.

13Le Model-Checking, introduit depuis les années 1990, est une approche logique qui construit une représentation succincte (Automate ou OBDD) du système de transition associé à un programme. La propriété à vérifier peut aussi être représentée par la même structure de donnée. La comparaison de la structure du programme avec la structure de la formule permet la vérification. La définissabilité logique classifie les propriétés qui peuvent être ainsi vérifiées et la complexité de communication montre que de nombreuses propriétés simples de graphes n’admettent pas de telles représentations succinctes. On peut alors considérer un ε-testeur pour la propriété à vérifier du système de transition, qui existe si cette propriété est Σ₂ ou admet un testeur comme la k-coloriabilité. On obtient alors une e-réduction qui permet de vérifier le programme en temps constant avec grande probabilité.

14Ces techniques de vérification probabiliste ne s’appliquent pas directement aux programmes classiques. Pour les utiliser, il faut tout d’abord trouver un testeur pour la propriété, puis trouver l’abstraction probabiliste correspondante. Cette notion de vérification approchée semble particulièrement utile lorsque la vérification exacte est inadaptée. Dans le cas de propriétés de sécurité, on peut ainsi proposer une notion de sécurité approchée.

2.1.4. Applications

15Le développement de l’Internet crée de nouveaux problèmes où les solutions approchées et robustes sont importantes. Nous prenons deux exemples, l’un pour des données XML et l’autre pour des protocoles distribués sur le réseau Internet, considéré comme un nouveau modèle de calcul.

16L’approche du test de propriété permet par exemple de tester en temps constant si un fichier XML suit approximativement une DTD (Data Type Définition) ou un schéma. Dans le cas où un fichier XML est invalide mais ne contient pas trop d’erreurs, on peut aussi le corriger efficacement en le modifiant pour le rendre valide. Cette possibilité permet d’envisager une utilisation robuste du langage XML et permet le développement de codes correcteurs d’erreurs généralisés aux propriétés régulières.

17Le réseau Internet réunit des acteurs dont le comportement suit celui de consommateurs au sein d’une économie. Les modèles économiques comme celui des jeux et mécanismes deviennent importants pour l’informatique. Un protocole informatique utilisé par les clients du réseau peut être modélisé par un jeu à n joueurs et on s’intéresse aux équilibres de Nash approchés, pour ce jeu. Dans ce modèle, on cherche à connaître les propriétés des équilibres que le réseau atteindra, sans pouvoir prévoir à l’avance le temps nécessaire pour approcher l’équilibre.

18On peut aussi décrire une propriété souhaitable des équilibres et trouver le jeu et donc le protocole qui garantira que l’équilibre suivra bien la propriété. Ces protocoles sont appelés mécanismes et permettent d’envisager la régulation du réseau, la création de nouveaux services sécurisés et plus généralement le développement de modèles définissant la valeur de l’information. À titre d’exemple, si l’on souhaite réduire le nombre de courriels non sollicités (Spams), quels sont les mécanismes (protocoles) qu’il faut développer pour tendre vers cet état ?

19La théorie des jeux et la théorie de la complexité ont donné naissance depuis la fin des années 1990 au nouveau domaine de l’algorithmique des jeux et des mécanismes et de nombreuses propriétés comme la régulation du réseau ou sa sécurité peuvent être analysées comme propriétés approchées d’équilibres. Dans ce cadre, on souhaite vérifier de manière approchée une propriété des équilibres d’un programme informatique distribué au sein des acteurs du réseau.

2.1.5. Recherches en France

20Les algorithmes probabilistes d’approximation sont élaborés soit au sein d’équipes d’informatique théorique (INRIA, LIX, LRI), soit dans des disciplines spécifiques comme l’algorithmique géométrique, l’algorithmique des mots (Marne-la-Vallée) ou l’algorithmique des graphes, très développée en France.

21Notons aussi que la théorie de l’apprentissage a permis récemment le développement de nouvelles techniques probabilistes pour la classification, utilisées par exemple dans l’analyse postgénomique.

2.1.6. Références

Références spécialisées

22Fischer E., 2001, « The art of uninformed decisions : a primer to property testing », The Computational Complexity Column of The Bulletin of the Européen Association for Theoretical Computer Science 75, p. 97-126.

23Goldreich O., Goldwasser S., Ron D., 1998, « Property testing and its connection to learning and approximation », Journal of the ACM, 45 (4), p. 653-750.

24Lassaigne R., de Rougemont M., 2004, Logic and Complexity, Springer Verlag.

25Papadimitriou G., 1994, Computational Complexity, Addison-Wesley.

26Rubinfeld R., Sudan M., 1996, « Robust characterizations of polynomials with applications to program », SIAM Journal on Computing, 25 (2), p. 23-32.

2.2. Parallélisme, nouvelles architectures, nouveaux paradigmes de calcul (Denis Trystram)

2.2.1. Introduction

27Le domaine du parallélisme est vaste, il regroupe en France une large communauté de chercheurs dans des laboratoires CNRS, INRIA et à l’université. Il concerne plusieurs disciplines variées, émanant parfois de cultures scientifiques différentes. Historiquement, la cible du parallélisme était principalement le calcul intensif (calcul à haute performance) : aller plus vite, et-ou résoudre des problèmes toujours plus gros. Le domaine s’est développé de façon continue depuis les années 1970 en suivant les évolutions technologiques des processeurs, des composants de routage ou des réseaux. Chaque nouvelle génération de machines parallèles ou distribuées a posé des problèmes spécifiques nouveaux qui ont été étudiés théoriquement, partiellement résolus et intégrés à un niveau ou un autre dans des réalisations pratiques. Gardons toutefois à l’esprit que l’utilisation du parallélisme, sous quelque forme que ce soit, a toujours nécessité (et nécessitera toujours) un effort supplémentaire qui s’est traduit la plupart du temps par un surcoût lors de l’implémentation. Aujourd’hui, on cherche plutôt à utiliser efficacement des ressources distribuées, distantes, variées et dynamiques, de façon transparente pour les utilisateurs. Les applications cibles se sont considérablement diversifiées et éloignées du calcul intensif (fouilles de données, multimédia, réalité virtuelle, bioinformatique, etc.).

28Malgré une place prépondérance des Américains, en partie due à des facteurs économiques et technologiques, globalement la compétitivité des chercheurs français reste bonne. Plusieurs programmes régionaux et nationaux ont été créés et soutenus (GdR ARP, AGI Grid et Masse de Données, etc.). La création récente du réseau d’excellence européen CoreGrid auquel participent de nombreux chercheurs français en témoigne également.

2.2.2. Évolution du domaine ces dernières années

29La crise économique du milieu des années 1990 a eu raison du foisonnement de réalisations pratiques (prototypes académiques ou commerciaux) de machines parallèles et distribuées. Le paysage actuel du parallélisme a évolué vers une certaine stabilité des supports d’exécution dont on distingue quelques grandes classes bien identifiées : les serveurs puissants héritiers des supercalculateurs, les grappes (collections homogènes ou faiblement hétérogènes de centaines d’ordinateurs standard reliés localement par des réseaux rapides), les grilles de calcul (collections de machines très diverses, distantes et bien identifiées, souvent hiérarchiques, qui peuvent regrouper des milliers de machines) et le calcul global (des centaines de milliers de machines, parfois rudimentaires, dont on n’a pas forcément le contrôle). Le relativement faible coût de ce type d’installation a été à l’origine d’une diffusion massive un peu partout dans le monde, et pas seulement dans les pays technologiquement les plus avancés. L’enjeu à terme est d’utiliser ces supports de façon transparente comme si l’on disposait d’une simple machine grâce à des environnements adéquats. Une idée intéressante défendue en France est de travailler sur le concept de « grille légère » (grappes de grappes), comme une étape intermédiaire vers la grille. À l’autre bout du spectre de calcul, les PDA ou téléphones mobiles intègrent de plus en plus de fonctionnalités qui font largement appel à des techniques éprouvées du parallélisme. Bien que de nombreux points soient communs, notamment sur le volet algorithmique, ce domaine des systèmes embarqués possède ses propres problématiques et ne sera pas discuté ici.

30L’idée initiale de la Grille était de pouvoir disposer de la puissance de calcul à la demande, comme l’électricité : chacun disposerait d’un petit terminal qu’il suffirait de brancher sur une prise connectée au réseau (Foster, Kesselman, 2004). Celle qui a présidé au développement du calcul global (ou calcul pair à pair) est de tirer parti de la faible utilisation de la puissance de calcul des ordinateurs connectés sur le réseau. On dispose d’une puissance cumulée quasi illimitée. Ce caractère fortement dynamique et versatile du calcul global est un obstacle pour développer des algorithmes efficaces. L’exploitation passe par le développement d’outils automatiques de découverte, de localisation, d’observation et de mesure. Toutefois, le type d’applications concernées reste limité à des classes particulières simples constituées de tâches relativement indépendantes (fouille de données ou calculs paramétrés). Des gros projets américains comme seti@home pour la recherche de signaux extra-terrestres ou le cassage de grandes clés de cryptographie ont montré la faisabilité de projets de calcul global impliquant des millions d’internautes. Les applications scientifiques traditionnelles dont le grain de calcul reste faible au regard des communications s’exécutent plutôt sur des grappes locales ou des grilles dédiées. Outre l’objectif de performance, des problèmes nouveaux apparaissent liés à la sécurité : détection de calculs non conformes ou attaques malicieuses.

31En France, nous avons perdu le contrôle sur l’architecture matérielle des composants ou des réseaux, principalement pour des raisons économiques. Les recherches se sont déplacées vers le logiciel. Les thèmes de recherche importants actuels sont reliés aux infrastructures et à la mise en œuvre d’une bonne gestion des ressources (Nabrzyski et al., 2004) : intergiciels – middleware – distribués (configuration, découverte de ressources, protection, etc.), à l’algorithmique et la programmation et à la gestion des ressources. Les communautés scientifiques se sont décloisonnées, comme en témoigne l’évolution des thèmes présentés dans les « Rencontres du parallélisme » qui mêlent depuis plusieurs années les domaines de l’Architecture, du Système et du parallélisme (Trystram et al., 2005).

2.2.3. Vision prospective

32Quelques constats simples peuvent être dressés aujourd’hui pour alimenter une vision prospective du domaine. Comme nous l’évoquions, il semble indispensable de décloisonner les couches traditionnelles, de développer une démarche expérimentale pour rendre compte de la complexité des ressources (et de leurs interactions) sans mettre de côté les études fondamentales. Ceci ne pourra être réalisé qu’au sein d’équipes de tailles conséquentes.

33On ne peut plus se restreindre aujourd’hui à une vision couche par couche du domaine. Classiquement, on présentait le parallélisme par strates depuis les utilisateurs-développeurs d’applications jusqu’à la machine (on parle plutôt de supports d’exécution aujourd’hui). Les chercheurs travaillent à l’heure actuelle sur plusieurs couches à la fois, alors que l’on pouvait auparavant se contenter d’interfaces (comprendre les frontières entre les couches successives). Par exemple, les spécialistes du Système ou des intergiciels s’occupent également de gestion de ressources (ordonnancement de tâches, partage de charge, optimisation des communications). Une certaine vision transversale de la recherche devient indispensable, ce qui conduit à des équipes plus pluridisciplinaires (et donc, aussi plus grosses).

34Vu le nombre croissant des paramètres apparaissant dans les nouveaux supports d’exécution (hétérogénéité, dynamicité, hiérarchie, déséquilibre calcul-communications, facteur d’échelle, etc.), il y a nécessité de se tourner vers une démarche plus expérimentale pour pouvoir appréhender la complexité croissante du domaine. À ce titre, le projet national Grid5000 est significatif, il s’agit de créer un « grand instrument » en Informatique à l’image des autres disciplines scientifiques plus anciennes comme la Physique, et le mettre à disposition de la communauté. Les chercheurs en attendent beaucoup. Actuellement, une première plate-forme de quelques milliers de processeurs répartis sur une dizaine de gros centres sur le territoire français est disponible. Bien sûr, il faut accompagner de tels projets par des supports humains pour l’administration système, en évitant l’écueil important de se cantonner à une pure ingénierie, dangereusement coupée d’une recherche plus fondamentale en amont.

35Le renforcement des aspects scientifiques fondamentaux est indispensable pour aborder ces problèmes nouveaux. Les modèles conceptuels de ces nouveaux supports d’exécution ne sont pas encore au point. La matière est changeante et complexe. Par exemple, la communauté française des chercheurs travaillant sur l’ordonnancement a été reconnue il y a une dizaine d’années pour ses contributions théoriques sur des modèles pour tenir compte de l’influence des communications. Aujourd’hui, ces modèles sont obsolètes et d’autres sont à inventer. Il a été montré qu’il est vain d’essayer d’étendre toujours plus loin les modèles existant : il faut imaginer des nouvelles façons d’appréhender les modèles. Un autre aspect important porte sur les critères à optimiser. La diversité des points de vue impose une optimisation multi-critères (T’Kindt et Billaut, 2002). Par exemple, on veut pouvoir obtenir des performances rapides tout en garantissant une certaine équité entre les utilisateurs. De même, face à la complexité des nouveaux supports d’exécution, les données manipulées sont sujettes à des incertitudes. Il faut alors revoir l’analyse des algorithmes d’optimisation pour déterminer de bons compromis, bien fondés théoriquement (Billaut ét al., 2002). L’interaction en France entre chercheurs théoriciens et spécialistes du terrain est une originalité à développer et à renforcer. L’algorithmique doit être repensée pour pouvoir s’adapter aux changements sans dégrader les performances. Pour cela, il faut disposer de mécanismes automatiques pour redistribuer dynamiquement les ressources disponibles et s’adapter à tout moment au contexte d’exécution (données et ressources).

2.2.4. Bilan

36Nous sommes bien placés en France pour répondre aux défis scientifiques et techniques liés au développement rapide et considérable des nouveaux supports d’exécution. La communauté est engagée et reconnue sur de nombreux fronts. Les moyens matériels ne manquent pas, on peut cependant regretter que trop peu de chercheurs aient été recrutés sur ces thèmes pour renforcer certaines équipes ou apporter à d’autres une vision neuve dans des domaines complémentaires. C’est une condition indispensable pour pouvoir aborder les problèmes dans leur globalité et rester compétitifs.

2.2.5. Références

Références générales

37Nabrzyski J., Schopf J., Weglarz J. (ed.), 2004, Grid Resource Management, State of Art and Future Prends, Kluwer Academie Publishers.

38Trystram D., Slimani Y., Jemni M. (dir.), 2005, Informatique répartie, hors série RTSI, Paris, Hermès.

Références spécialisées

39Billaut J.C., Moukrim A., Sanlaville E. (dir.), 2005, Flexibilité et robustesse en ordonnancement, Paris, Hermès.

40Foster L, Kesselman C. (ed.), 2004, The Grid : Blueprint for a New Computing Infrastructure (2nd édition), Morgan Kauffmann.

41T’Kindt V., Billaut J.C., 2002, Multi-Criteria Scheduling : Theory, Models and Algorithmes, Springer Verlag.

2.3. Futur : vers l’ordinateur quantique (Philippe Jorrand)

42Il n’y a d’information qu’inscrite dans la matière. Qu’il s’agisse du boulier chinois, de la machine à calculer conçue par Leibniz au XVII^e siècle, du processeur Pentium 4 d’Intel Corporation, ou de la molécule d’ADN, il n’y a pas d’information qui ne soit incarnée dans l’état d’un support physique ou chimique. Il n’y a pas non plus de traitement de cette information qui ne soit réalisé par une transformation de cet état, au travers de processus physiques ou chimiques qui mettent en jeu de l’énergie. C’est en utilisant des propriétés de la matière qui avaient été cernées par la physique classique, celle de Newton et de Maxwell, que les ordinateurs d’aujourd’hui effectuent des tâches que nous interprétons comme des calculs, du raisonnement ou de la communication. Quand on considère l’information et son traitement sous cet angle, une question se pose : que deviendraient le traitement et la communication de l’information, que perdrait-on, que gagnerait-on, si l’on déracinait l’information de son terrain de toujours en physique classique, pour la replanter ailleurs, dans une autre physique, la physique quantique qui, au siècle dernier, a mis en évidence les propriétés étranges des particules élémentaires ? C’est tout l’objet des recherches sur le traitement et la communication de l’information quantique, lieu d’investigations nouvelles, au confluent de deux courants scientifiques majeurs du XX^e siècle, la physique quantique et les sciences de l’information.

2.3.1. Introduction

43Des phénomènes physiques formulés par la mécanique quantique sont en effet désormais considérés sous l’angle de leur exploitation pour représenter, traiter et communiquer l’information. Dès 1982, Richard Feynman suggère d’utiliser la physique quantique, au lieu de la physique classique, comme support matériel de l’information, afin de traiter des problèmes que leur complexité met hors de portée de l’informatique actuelle. En 1985, David Deutsch (Oxford University) rappelle qu’Alan Turing se référait, au milieu des années 1930, à une notion assez vague de functions which would naturally be regarded as computable, et montre que Turing avait fondé sa machine abstraite sur la physique classique, sans qu’il exprimât nulle part cette option, ni même, probablement, qu’il en fût conscient. En substituant aux fonctions dont parlait Turing la notion de simulation d’un système physique par un autre, Deutsch introduit alors un « principe » de Church-Turing, qui a le même statut épistémologique que d’autres principes fondamentaux de la physique, et qui souligne le nécessaire enracinement de l’information et du calcul dans la matière et les processus physiques. Puis, en conformité avec ce principe, il propose une extension quantique de la classe des machines de Turing, dont il prouve quelques propriétés remarquables car non reproductibles en temps polynomial par les machines classiques.

44C’est au cours des années 1990 que des résultats, théoriques puis expérimentaux, viennent confirmer de manière éclatante l’intuition initiale. En 1993, Charles Bennett (IBM Research), Gilles Brassard (Université de Montréal), Asher Peres (Technion, Haifa) et quelques autres publient les principes théoriques d’un protocole de « téléportation » : l’état d’un système quantique ‘a’ localisé en A peut, après avoir été détruit, être reconstruit sur un autre système quantique ‘b’ localisé en B, sans qu’aucun système ni phénomène physique porteur de l’état de ‘a’ soit transporté sur une trajectoire reliant A et B. Un an plus tard, Peter Shor (AT & T) montre que le calcul quantique permet de factoriser les entiers en un temps polynomial, alors que le meilleur algorithme classique connu est exponentiel. En 1996, Lov Grover (Lucent Technologies) publie un algorithme quantique qui n’a besoin que de sqrt (n) tests d’une propriété f pour trouver l’élément unique qui satisfait f dans une base de données non ordonnée de taille n, là où le calcul classique requiert de l’ordre de n tests de la même propriété. En 1997, Anton Zeilinger (Université de Vienne) réalise la première expérience de téléportation de l’état d’un photon, suivie depuis par beaucoup d’autres dans d’autres laboratoires. De 1999 à 2002, Isaac Chuang (IBM Research) réalise un ordinateur quantique fondé sur la résonance magnétique nucléaire qui, bien que limité à 7 bits, a permis de montrer expérimentalement que les principes algorithmiques théoriques imaginés par Peter Shor et Lov Grover peuvent bien être mis en œuvre par la physique quantique. D’autres projets de ce genre, plus ambitieux, sont actuellement en cours à travers le monde, notamment en Chine et en Inde, mais encore aucun en France.

45Pour tous les problèmes désormais ouverts par les recherches sur le traitement et la communication de l’information quantique, on constate que l’interdisciplinarité est source de créativité. Les avancées les plus significatives ont été et seront accomplies dans un croisement permanent des questions et des résultats apportés par les physiciens, les informaticiens et les mathématiciens. Pour reprendre les termes d’un rapport de la NSF : « We need to ftnd a synergy between abstract models of computation and proposed implémentations. As physicists better understand the limitations of what we can implement, computer scientists can better devise models and algorithms to handle these limitations. Conversely, as computer scientists understand what resources are critical for quantum algorithms to work, physicists can better design implantations to address these issues. » Le chemin vers un éventuel ordinateur quantique sera long, mais on sait d’ores et déjà qu’il traverse un territoire fertile en beaux résultats scientifiques et en innovations technologiques.

2.3.2. Principales questions scientifiques

46Les splendides résultats théoriques des années 1990 sur l’information quantique et son traitement, puis leurs confirmations expérimentales, montrent que des problèmes hors de portée de l’informatique classique pourraient être traités en exploitant ce nouveau paradigme de calcul. Ces travaux ouvrent des perspectives scientifiques et technologiques lointaines, certes, mais immenses. Ils ont donné naissance à un courant de recherche interdisciplinaire aujourd’hui foisonnant où physiciens, informaticiens et mathématiciens apportent des contributions majeures. Des liens profonds ont été établis entre les disciplines jusqu’alors disjointes de la physique quantique, de l’informatique théorique et de la théorie de l’information. La douzaine de pionniers de la fin des années 1980 est devenue une communauté pluridisciplinaire de plusieurs milliers de personnes qui a désormais ses conférences internationales, ses écoles d’été et ses journaux. Cette dynamique est jeune et elle a devant elle de grandes questions, souvent difficiles, mais pleines de promesses.

Algorithmique quantique et complexité

47Pour explorer la puissance du calcul quantique, on pense d’abord au chemin ouvert par Shor et Grover : développer des algorithmes quantiques pour traiter, mieux qu’avec le calcul classique, des problèmes importants de l’algorithmique traditionnelle. C’est évidemment au cœur des recherches en informatique quantique. Même si les chutes de complexité par rapport au calcul classique ne sont pas toujours exponentielles, elles n’en demeurent pas moins pertinentes pour des problèmes de grande taille. Mais il faut encore dégager et mieux comprendre les outils de l’algorithmique quantique, à quels problèmes ils peuvent s’appliquer et la façon dont ils peuvent se composer entre eux. La transformée de Fourier quantique (Shor) et l’amplification d’amplitude (Grover) font déjà partie de ces outils, mais quelle est leur portée, quelles sont leurs limitations ? Les marches aléatoires quantiques sur les graphes en font aussi partie, mais pour quelles classes de problèmes ? Même genre de questions à propos du calcul quantique fondé sur la mesure quantique, façon de conduire un calcul qui semble prometteuse, tant du point de vue de la logique que de celui de la physique. D’autres questions, plus abstraites, sont posées en théorie de la complexité. Quelles sont les relations entre les classes de complexité quantiques et les classes de complexité classiques ? Comment prendre en compte les états quantiques intriqués (notion introduite plus loin), ressource non classique que le calcul quantique consomme, comme il consomme du temps et de l’espace ?

Calcul quantique distribué

48La situation paradigmatique du calcul distribué est celle où deux partenaires A et B doivent calculer f (x, y), alors que seul A connaît x et seul B connaît y. L’objectif de l’algorithmique distribuée est de minimiser le nombre de bits échangés par A et B pour parvenir au résultat. Cela se généralise à un nombre quelconque de partenaires. On sait, pour certaines classes de fonctions, que le nombre de bits quantiques échangés est très inférieur au nombre de bits classiques pour calculer la même fonction de façon distribuée. Beaucoup de questions sont encore sans réponse dans ce domaine de la complexité de communication quantique, même pour des classes de fonctions très simples. On sait aussi que si les partenaires se sont réparti préalablement des bits quantiques dans un état global intriqué, cela permet, pour certaines fonctions, une chute significative du nombre de bits échangés. Mais la compréhension de ce qu’apportent au calcul distribué les états quantiques intriqués ne pourra s’appuyer que sur une analyse de situations où de tels états viennent faciliter la communication, situations qui restent très largement inexplorées.

Modèles abstraits et langages quantiques

49La machine de Turing quantique marque la limite : pour la calculabilité, calcul quantique et calcul classique sont équivalents. Les promesses du calcul quantique sont ailleurs : repousser loin les frontières du raisonnablement calculable. Équivalents à la machine de Turing, les réseaux de portes quantiques sont un autre modèle qui fournit une abstraction plus directe de calculs par transformation de l’état d’un registre de bits quantiques. Il existe d’autres formes du calcul quantique, pour lesquelles d’autres modèles ont dû être imaginés ou sont encore à inventer, comme par exemple le calcul par mesures quantiques, qui consiste à conduire un calcul en effectuant une série de mesures sur un ensemble de bits quantiques mis initialement dans un état globalement intriqué. D’autres formes encore moins traditionnelles méritent d’être explorées, comme le calcul quantique adiabatique, d’inspiration beaucoup plus directement physique, et le calcul quantique topologique, où l’information est codée par des propriétés topologiques d’un système quantique, propriétés voisines de celles qui sont étudiées en théorie des nœuds. Un vaste chantier est ouvert pour étudier et définir des modèles abstraits adéquats pour le calcul quantique : automates quantiques et machines abstraites, modèles fondés sur la logique quantique, sur la logique linéaire, sur la théorie des catégories, lambda-calculs et algèbres de processus quantiques, systèmes de types reflétant les propriétés des données quantiques, etc. Les langages pour formuler les algorithmes quantiques, et surtout les bases nécessaires à la définition de leur sémantique, appellent aussi des recherches nouvelles : prise en compte de la coopération entre calcul quantique et calcul classique, de la mesure quantique, de la communication quantique, du calcul quantique distribué, interprétation des programmes dans le domaine des états mixtes (distributions de probabilités sur plusieurs états), composition, transformation et preuve de programmes et protocoles quantiques.

Cryptographie quantique

50L’algorithme quantique de Shor est une menace pour les systèmes de cryptage les plus utilisés, qui reposent précisément sur la difficulté qu’il y a à factoriser les grands entiers. Mais l’information quantique reconstruit de la main droite, et plus solidement, ce qu’elle risque de démolir de la main gauche. La cryptographie quantique repose sur le principe selon lequel la mesure d’un système quantique perturbe l’état de ce système. Deux partenaires distants qui échangent des bits quantiques pour se mettre d’accord sur une clé secrète en vue de messages ultérieurs qu’ils crypteront avec cette clé, peuvent donc détecter, puis éliminer de la clé, les parties qui en ont été perturbées par un observateur indiscret. La clé obtenue est alors confidentielle. Le protocole BB84 imaginé par Charles Bennett et Gilles Brassard en 1984 reposait sur cette idée. La sécurité de telles communications repose sur la validité de la mécanique quantique, et non plus sur des conjectures, aussi robustes soient-elles, comme P # NP. L’objectif est désormais de cerner la puissance et les limites de solutions quantiques à tous les aspects de la cryptographie : authentification de l’émetteur, signature, partage de secret entre n partenaires (où il faut réunir les informations possédées par k n d’entre eux pour reconstituer une information qui restera secrète s’ils ne sont que k – 1). Il faut ensuite savoir dans quelle mesure ces protocoles, à leur tour, sont vulnérables à des attaques qui feraient usage du calcul quantique. Mais un point est acquis : c’est dans le domaine de la cryptographie que l’information quantique verra rapidement les résultats théoriques donner lieu à des réalisations techniques crédibles et à des produits sur le marché.

Théorie de l’Information quantique

51Le contenu informationnel de n bits quantiques est paradoxal. Bien que, selon les postulats de la mécanique quantique, 2ⁿ nombres complexes soient nécessaires pour spécifier l’état du système constitué par ces n bits quantiques, le théorème de Holevo (1973 !) a pour conséquence qu’ils ne peuvent être utilisés que pour coder au plus n bits classiques d’information. Ce résultat limite les possibilités de communication par le seul transport de bits quantiques. Par contre, mais avec le secours d’états quantiques intriqués, la transmission de deux bits classiques suffit pour reconstruire l’état d’un bit quantique (téléportation) et surtout, symétriquement, un bit quantique suffit pour coder l’état de deux bits classiques (dense coding), compression inatteignable classiquement. Toutefois, il est impossible de recopier à l’identique l’état d’un bit quantique quelconque i (no cloning theorem). La théorie de l’information quantique réexamine l’ensemble des questions qui relèvent de la théorie de l’information classique, née en 1948 avec les travaux de Shannon, à la lumière des propriétés que la physique quantique confère au bit quantique, porteur élémentaire de l’information : comment l’information classique ou quantique est-elle transmise par un canal quantique, bruité ou non bruité ? Dans quelle mesure des états préalablement intriqués peuvent-ils faciliter cette transmission ? À côté de la notion de capacité d’un canal classique, plusieurs formes de capacités des canaux quantiques apparaissent alors : capacité quantique simple (transmission de bits quantiques), capacité classique simple (transmission de bits classiques), capacité quantique assistée par la communication classique, capacité classique assistée par des états intriqués, et d’autres encore. Autant de questions en cours d’investigation.

États quantiques intriqués

52L’état d’un système quantique composé de n sous-systèmes n’est pas, en général, réductible à un n-uplet des états de ses sous-systèmes. Une telle situation, où l’état d’un sous-système n’est pas une partie de l’état global, n’a pas d’équivalent en physique classique : on dit que l’état du système est intriqué (entangled en anglais). Les états intriqués sont le cas général et un état non intriqué est dit séparable. Einstein, Podolsky et Rosen contestaient, en 1935, la réalité de telles situations. À leurs yeux, les liaisons instantanées que cela installait entre états des sous-systèmes étaient porteuses de contradictions avec la théorie de la relativité. Il a fallu près de 50 ans pour montrer, par la théorie puis par l’expérimentation, qu’ils avaient tort. Depuis, les états intriqués sont devenus la ressource essentielle du traitement et de la communication de l’information quantique : bien qu’elle ne permette pas, à elle seule, le transport d’information, la corrélation établie entre sous-systèmes par de tels états est porteuse d’information. De ce fait, les états intriqués méritent une étude pour eux-mêmes. Il y a une question centrale : étant donné l’état d’un système, comment décider s’il est intriqué ou séparable ? Et beaucoup d’autres questions : étant donné deux systèmes, quelle mesure attribuer à leurs états respectifs pour savoir si l’un est « plus » intriqué que l’autre ? Quelles opérations, effectuées localement par des partenaires qui se sont réparti des composants d’un système dans un état intriqué, permettent-elles de faire évoluer ce système vers un autre état intriqué donné ? Etc. Ce sont des questions difficiles et, au-delà de systèmes composés de deux, voire trois sous-sysuèmes, on est encore loin de réponses satisfaisantes et générales, donc d’une bonne compréhension de ce que sont les états intriqués.

Codes quantiques correcteurs d’erreurs

53L’information quantique est fragile. Qu’il s’agisse de la transformer ou de la transporter, elle est sujette à des interactions non souhaitées avec un environnement, et ces interactions la perturbent. C’est le phénomène inévitable de la décohérence. Il faut donc savoir traiter et communiquer l’information quantique de façon fiable malgré l’action perturbatrice de la décohérence. Comme dans le cas classique, les codes quantiques correcteurs d’erreurs protègent l’information en ayant recours à la redondance. Mais la difficulté est ici bien plus grande : on ne peut pas dupliquer (no cloning), il y a un continuum de perturbations possibles sur un même bit quantique, l’observation de l’état détruit l’état. Plusieurs codes correcteurs ont été imaginés et une théorie générale de la correction d’erreurs quantique a été élaborée. Mais beaucoup de questions demeurent. Comment étendre les méthodes existantes pour obtenir des codes efficaces à la fois pour l’information quantique et pour l’information classique ? Où sont les limites des codes quantiques correcteurs d’erreurs ? Un des résultats majeurs est le threshold theorem, selon lequel un algorithme quantique, aussi complexe soit-il, peut être rendu tolérant aux fautes tant que le taux d’erreurs à chaque étape du calcul reste sous un certain seuil constant (estimé actuellement à 10^-4). L’idée est d’effectuer le calcul directement sur des états codés et de faire suivre chaque pas de calcul d’une étape de correction d’erreur. Mais ce théorème fait des hypothèses sur le type d’erreurs qui peuvent survenir et sur l’indépendance entre les erreurs subies par des bits quantiques distincts : on ne sait pas encore quelles pourraient être des hypothèses plus réalistes qui garantiraient cette indispensable tolérance aux fautes.

Vers l’ordinateur quantique

54Last but not least, il faut parvenir à inscrire le bit quantique dans la matière d’une façon exploitable pour faire fonctionner des systèmes physiques destinés à représenter, traiter et communiquer effectivement l’information quantique. C’est un défi scientifique et technologique considérable où la difficulté est grande, insurmontable disent même certains. Bien que le threshold theorem prouve qu’aucun principe physique ne s’oppose à la réalisation d’ordinateurs quantiques, il ne supprime pas la décohérence, obstacle principal mis en travers du chemin par la nature. Il faut satisfaire deux exigences contraires. D’une part le bit quantique doit être aussi isolé que possible de son environnement pour que son état soit maintenu longtemps dans une forme récupérable par des codes correcteurs. D’autre part le bit quantique doit être manipulable à partir de son environnement, car seul cet environnement (classique) est en mesure d’effectuer sur lui les opérations successives correspondant à la conduite d’un calcul. Le problème à résoudre est donc de trouver des systèmes physiques permettant d’établir un bon compromis entre ces exigences. Cinq critères principaux ont été retenus pour évaluer l’intérêt d’un support physique donné (David DiVicenzo, IBM Research) : (i) il faut pouvoir donner au bit quantique un état initial standard, (ii) il faut pouvoir effectuer les opérations élémentaires d’une famille universelle d’opérations, (iii) il faut pouvoir mesurer l’état d’un bit quantique, (iv) le temps de décohérence doit être très supérieur au temps d’une opération élémentaire (d’un facteur estimé à 10⁴), et (v) le support choisi doit permettre le passage à l’échelle, à plusieurs dizaines voire plusieurs centaines de bits quantiques. Beaucoup d’approches sont prises en considération : résonance magnétique nucléaire, ions ou atomes neutres piégés, jonctions de Josephson, spins d’électrons, spins nucléaires, photons polarisés, etc. Quelle que soit l’approche choisie, le chemin sera long avant qu’un support physique satisfaisant ne soit trouvé. Puis il faudra que se précisent, à un plus haut niveau, les questions d’architecture de machines quantiques et la forme de leur nécessaire coopération avec des processeurs classiques, pour qu’enfin soit réalisé un ordinateur quantique permettant de traiter des problèmes réels. C’est un parcours scientifique et technique ardu, qui durera peut-être plusieurs décennies.

2.3.3. L’information quantique dans le monde et en France

55La communauté scientifique internationale engagée dans des recherches sur l’information quantique, son traitement et sa communication comporte environ 85 % de physiciens, théoriciens et expérimentalistes, et 15 % d’informaticiens sur le versant théorique de leur discipline, accompagnés par quelques mathématiciens. Seule la partie informatique sera évoquée ici, en soulignant toutefois que les physiciens français (notamment à Orsay, Grenoble, Toulouse et ENS Ulm) jouent un rôle de premier plan dans la recherche d’un support physique pour le bit quantique et, plus généralement, dans la recherche et la prise en compte de propriétés physiques utiles pour le traitement de l’information quantique.

Dans le monde

56Sur le versant informatique, plusieurs centres de recherche nord-américains ont désormais une place de leaders, au Canada (University of Calgary : Quantum Computing Research Group, University of Waterloo : Institute for Quantum Computing et Perimeter Institute, Université de Montréal : Laboratoire d’Informatique Théorique et Quantique, Université McGill : Laboratoire de Cryptographie et Informatique Quantique, University of Ottawa : Department of Mathematics and Statistics), et aux États-Unis (University of California, Berkeley : Computer Science Division, MIT : Center for Bits and Atoms, IBM Research Yorktown : Quantum Information and Information Physics, Caltech : Institute for Quantum Information).

57En Europe, l’étude de questions informatiques liées au traitement et à la communication de l’information quantique est particulièrement active au Royaume-Uni (University of Bristol : Quantum Computation and Information, University of Cambridge : Centre for Quantum Computation, University of Oxford : Centre for Quantum Computation et Computing Laboratory), et en Allemagne (Max Planck Institut für Quantenoptik Garching : Theory Division, Technical University of Braunschweig : Quantum Information Group, Universitat Potsdam : Quantum Information), mais aussi en Autriche (University of Innsbruck : Institute of Theoretical Physics), en Belgique (Université Libre de Bruxelles : Centre for Quantum Information and Communication, Katoliek Universiteit Leuven : Quantum Computing), aux Pays-Bas (University of Amsterdam : CWI), en Suisse (Université de Genève : Group of Applied Physics) et dans quelques autres pays (Italie, Pologne, Portugal et Slovaquie notamment).

58La plupart des grands pays industrialisés ont mis en place des programmes nationaux qui soutiennent des projets de recherche, parfois ambitieux et souvent interdisciplinaires, en information quantique. La priorité IST (Information Society Technologies) du 5^e puis du 6^e programmes cadres de l’Union européenne a lancé une initiative FET (Future and Emerging Technologies) intitulée QIPC (Quantum Information Processing and Communication), qui a soutenu ou soutient encore une trentaine de projets, dont le réseau d’excellence QUIPROCONE (Quantum Information Processing and Communication Network of Excellence) qui a permis, jusqu’en 2003, d’établir quelques bases nécessaires à l’existence d’une communauté de recherche sur l’information quantique en Europe.

En France

59En France, dans le domaine de l’information quantique, le poids de la recherche en informatique par rapport à la recherche en physique est bien moindre que dans le reste du monde. En considérant toutes les équipes qui participent au Groupement de Recherches (GdR) « Information et Communication Quantiques » du CNRS, qui regroupent l’essentiel de la communauté française dans ce domaine, on peut estimer ce rapport à 5 % d’informaticiens pour 95 % de physiciens. Ce GdR, seule action nationale française en information quantique, permet à l’ensemble de cette communauté d’organiser un colloque annuel et quelques rencontres entre chercheurs.

60Le versant informatique de l’information quantique française est représenté par deux petites équipes, l’une au LRI, à Orsay, fondée à la fin des années 1990, l’autre à l’IMAG, à Grenoble, fondée en 2001, et par quelques chercheurs dans des groupes d’informatique théorique (notamment au Laboratoire PPS à Paris, et au Laboratoire LIP à l’ENS de Lyon). Malgré sa petite taille, cette communauté française de l’informatique quantique est bien insérée dans la recherche mondiale, notamment sur les questions d’algorithmique, de complexité, de modèles abstraits, de langages et de sémantique. Mais elle rencontre encore des difficultés à se faire une place au sein des disciplines traditionnelles en France, en informatique « classique » notamment. Chez nos voisins européens, petits et grands, des politiques scientifiques audacieuses ont permis à des groupes analogues de franchir ces obstacles, comme le montre le nombre d’universités qui affichent désormais des groupes et des enseignements officiellement constitués en quantum computation ou quantum information.

61Pour conclure, il faut aussi mettre en lumière la force exceptionnelle que pourraient représenter des campus comme Orsay ou comme Grenoble, qui rassemblent chacun toutes les compétences requises, en informatique et en physique, pour oser lancer en France un grand projet interdisciplinaire ambitieux, très visible et à long terme, qui viserait la conception et la réalisation expérimentale d’un ordinateur quantique.

2.3.4. Références

Références générales

62Rieffel E., Polak W., 2000, An Introduction to Quantum Computing for Non-Physicists. ACM Computing Surveys, Vol. 32, No 3, Sept. 2000, p. 300-335. Également accessible en ligne : http://arxiv.org/abs.quant-ph/9809016.

Références spécialisées

63ARDA (Advanced Research and Development Activity), 2004, A Quantum Information Science and Technology Roadmap, April 2004, accessible en ligne : http://qist.lanl.gov.

64Kitaev A. Yu., Shen A.H., Hyalyi M.N., 2002, Classical and Quantum Computing, Graduate Studies in Mathematics, Vol. 47, American Mathematical Society.

65Nlelsen M.A., Chuang I.L., 2000, Quantum Computation and Quantum Information, Cambridge University Press.