Parcours Etranges

Un calcul (du latin calculus, “caillou” utilisé pour compter), est la représentation abstraite d’un processus physique en termes d’états, et de transitions entre états ou événements.

La définition des états et événements possibles est formulée dans un modèle de calcul, comme la machine de Turing ou l’automate fini. Par exemple, l’état d’une machine de Turing est la séquence complète de symboles sur son ruban plus la position de la tête et son symbole interne, et un événement est le mouvement entre deux états successifs, défini déterministiquement en termes des mouvements élémentaires de lecture, écriture, déplacement à gauche, déplacement à droite.

Afin d’effectuer un calcul, une correspondance dotée d’une certaine robustesse est d’abord établie entre un modèle de calcul et un système physique, ce qui signifie que les états et les événements dans le modèle sont utilisés pour identifier des états et des événements observés dans le système, et que la correspondance choisie est suffisamment stable à l’égard de divers types de perturbation.

Le système est ensuite préparé dans un état initial et laissé évoluer au travers d’un parcours d’événements dans l’espace des états, jusqu’à ce qu’il parvienne à un état marqué comme final. La dynamique discrète de l’espace de calcul peut être représentée par un graphe orienté, où les sommets sont des états possibles du système et les arcs sont des événements transformant un état dans un autre.

Dynamique de calculs irréversibles Cliquer l’image pour agrandir1

Réversibilité logique

Une fonction est dite réversible (du latin revertere, ‘retourner’) si, étant donné un état d’arrivée, il est toujours possible de déterminer l’état de départ, ce qui est le cas s’il y a une relation bijective entre états de départ et d’arrivée. Si l’espace des états est fini, une telle fonction est une permutation. La réversibilité logique implique la conservation de l’information.

Lorsque plusieurs états de départ correspondent à un même état d’arrivée, alors la fonction est irréversible, car il est impossible connaissant seulement l’état d’arrivée de déterminer quel était l’état de départ. En algèbre de Boole, NOT est réversible, alors que SET TO ONE est irréversible. Les fonctions booléennes à deux variables comme AND, OR, XOR sont aussi irréversibles, car elles mettent en correspondance 2² états de départ avec 2¹ états d’arrivée, ainsi de l’information est perdue dans la fusion des chemins, comme montré dans le graphe suivant d’un calcul NAND dont l’évolution inverse n’est plus déterministe.

Le côté droit essaie de représenter la correspondance inverse du côté gauche

Réversibilité physique

Les lois physiques connues sont réversibles. Ceci est le cas aussi bien pour la mécanique classique, basée sur la dynamique lagrangienne/hamiltonienne, et pour la mécanique quantique standard, où les systèmes fermés évoluent selon des transformations unitaires, qui sont bijectives et inversibles. En conséquence, lorsqu’un système physique effectue un calcul irréversible, la correspondance avec le modèle de calcul indique que le système ne peut rester fermé.

Plus précisément, puisqu’un calcul irréversible réduit l’espace des états physiques porteurs d’information, leur entropie doit diminuer en augmentant l’entropie des états non porteurs d’information, représentant la partie thérmique du système.

En 1961 Landauer étudia cet argument thérmodynamique, et proposa le principe suivant : si un système physique effectue un calcul classique logiquement irréversible, il doit augmenter l’entropie de l’environnement avec une quantité minimum de chaleur dégagée de kT x ln(2) par bit perdu (où k est la constante de Boltzmann et T la température, c’est à dire environ 3 x 10^-21 joules à température ambiante),² ce qui met l’accent sur deux faits :

• l’irréversibilité logique d’un calcul implique l’irréversibilité physique du système qui l’effectue (”l’information est physique”);
• les calculs logiquement réversibles peuvent être au moins en principe intrinsiquement non dissipatifs (ce qui est en relation avec le théorème de Carnot sur les moteurs thérmiques, montrant que les moteurs les plus efficaces sont réversibles, et le théorème de Clausius, attribuant un changement d’entropie nul aux processus réversibles).

Inclusion réversible de calculs irréversibles

Landauer remarqua également que tout calcul irréversible peut être transformé en un calcul réversible par son inclusion dans un calcul plus étendu dans lequel aucune information n’est perdue, c’est à dire en reproduisant chaque sortie dans l’entrée (ajout de sources) et chaque entrée dans la sortie (ajout de puits).

Par exemple, la fonction irréversible NAND vue plus haut peut être incorporée dans la bijection suivante, également connue comme porte de Toffoli³ (la fonction d’origine est marquée en rouge) :

Les bits d’information supplémentaires, tels des fils d’Ariane, assurent la possibilité d’inverser tout parcours de calcul : ils sont les déchets de la voie avant et le programme de la voie arrière. Au lieu de les perdre dans l’environnement, ils sont maintenus dans l’espace contrôlé de calcul.

Les portes de Toffoli sont des fonctions primitives réversibles et universelles, ce qui signifie que toute fonction réversible peut être construite en termes de portes de Toffoli. La porte de Fredkin est un autre exemple de primitive réversible et universelle. Elle échange ses deux entrées en fonction de l’état d’une troisième entrée de contrôle, permettant ainsi d’incorporer tout calcul dans un routage conditionnel transportant des signaux conservés.

Certains aiguillages de voies ferrées sont réversibles

Modèles de calcul réversible

Le modèle balistique, inventé par Fredkin et Toffoli,⁴ a été l’un des premiers modèles de calcul visant la mise en oeuvre avec des composants physiques réversibles. Basé sur les lois de la mécanique classique, il est équivalent au formalisme de la théorie cinétique des gaz parfaits. La présence de sphères rigides en mouvement à des points spécifiés est définie comme 1, leur absence comme 0. Des interactions par collision à angle droit permettent la construction de différentes fonctions primitives, comme par exemple cette porte universelle à 2 entrées et 3 sorties introduite par Feynman,⁵ qui proposa également avec Ressler une version balistique de la porte de Fredkin.

Porte de Feynman

Dans la pratique, un calcul effectué par ces sphères serait très peu fiable, car l’instabilité résultante des plus petites perturbations générerait rapidement des écarts chaotiques, produisant une sortie saturée d’erreurs. Les erreurs peuvent être corrigés (par exemple, par l’ajout de potentiels pour stabiliser les chemins), toutefois le processus de correction des erreurs est lui même irréversible et dissipatif - car il doit effacer l’information erronée. Par conséquent, la correction des erreurs semble être le seul aspect du calcul définissant une limite inférieure à la dissipation d’énergie.

Une approche plus stable est celle du modèle de calcul Brownien,⁶ où le bruit thermique est au contraire autorisé à interagir librement avec un système de calcul proche de l’équilibre. Des barrières d’énergie potentielle définissent les chemins d’un espace de calcul, dans lequel le système se promène au hasard jusqu’à atteindre un état final. L’ARN polymerase, l’enzyme impliqué dans la transcription de l’ADN, est un exemple de machine brownienne effectuant une “copie de ruban” de manière logiquement réversible. Le processus de réplication de l’ADN suit également un mécanisme similaire, mais ajoute une logique irréversible de correction d’erreurs.

Renversement de Lecerf-Bennett

La méthode d’inclusion est cependant insuffisante pour construire un ordinateur universel physiquement réversible, puisque la quantité croissante d’information devant être reproduite pour chaque événement saturerait toute mémoire finie. Ensuite, le calcul prendrait fin - à moins que la mémoire ne soit irréversiblement effacée, mais alors la dissipation serait simplement reportée, et non pas évitée.

Cela semblait exclure la possibilité de construire des ordinateurs réversibles, jusqu’à que Bennett ⁷ ne trouve une solution remarquable (un travail antérieur de Lecerf⁸ avait anticipé sa méthode formelle), montrant qu’il est possible au moins en principe d’effectuer une quantité illimitée de calculs sans aucune dissipation d’énergie.

Le système réversible doit calculer la fonction inclusive deux fois : la première fois “en avant” pour obtenir et sauvegarder le résultat du calcul, et la deuxième fois “en arrière”, comme un calcul image-miroir de la fonction inverse, de-calculant la première étape et retournant le système fermé dans son état initial.

M. C. Escher, Cygnes (1956).
Toutes les oeuvres de M.C. Escher (c) 2007 The M.C. Escher Company - the Netherlands.
Tous droits réservés. Reproduit avec permission. www.mcescher.com
Cliquer l’image pour agrandir

L’irréversibilité logique et le démon de Maxwell

En 1867 Maxwell proposa une expérience de pensée au sujet d’un “démon” fini et microscopique, capable d’observer le mouvement individuel des molécules. Ce démon surveille une petite porte qui sépare deux conteneurs remplis de gaz à la même température. Quand une molécule approche, le démon vérifie sa vitesse et ouvre ou ferme la porte, de manière à envoyer les molécules lentes dans un conteneur (qui se refroidit), et les molécules rapides dans l’autre conteneur (qui se chauffe), en violation apparente de la 2ème loi de la thérmodynamique.

Une première étape importante vers la solution de ce paradoxe controversé fut franchie en 1929 par Szilard⁹ qui, après avoir évité tout piège dualiste en substituant le démon intelligent par une simple machine, suggéra que la comptabilisation correcte de l’entropie est restaurée dans le processus de mesure de la position des molécules. Cette explication est devenue standard jusqu’en 1981, lorsque Bennett montra⁶ que l’étape fondamentalement dissipative n’est étonnamment pas la mesure (qui peut être effectuée réversiblement) mais l’étape logiquement irréversible de l’effacement de la mémoire du démon, pour faire de la place aux mesures suivantes.

Réversibilité dans le calcul quantique

Le calcul quantique profite des effets physiques de superposition et d’enchevêtrement, qui conduisent à un paradigme de calcul qualitativement nouveau.¹⁰ Dans les modèles de calcul quantique, tous les événements se produisent par des transformations unitaires, ainsi toutes les portes logiques quantiques sont réversibles.

Les systèmes quantiques sont moins sensibles à certains types d’erreur affectant les calculs classiques, car leur spectre discret interdit les trajectoires chaotiques. Par exemple un modèle balistique quantique est plus fiable que sa contrepartie classique.

Toutefois, les systèmes quantiques sont affectés par de nouvelles sources d’erreur, conséquence des interactions avec l’environnement, tels que la perte de cohérence quantique. Il est possible de corriger des erreurs quantiques génériques jusqu’à une limite,¹¹ de manière à reconstruire un état quantique exempt d’erreur, au prix de l’accomplissement d’un effacement quantique irréversible de l’information quantique erronée.

Je remercie Charles H. Bennett pour ses commentaires stimulants sur le manuscrit.

1. A. Wuensche, M. Lesser, “The global dynamics of cellular automata“, Ref Vol. I of the Santa Fe Institute Studies in the Sciences of Complexity. Addison-Wesley (1992) [Images de graphes d’états d’automates cellulaires]. [↩]
2. R. Landauer, “Irreversibility and heat generation in the computing process“, IBM Journal of Res. and Dev., 5:3, 183 (1961) [Irréversibilité logique, principe de Landauer]. [↩]
3. T. Toffoli, “Reversible computing“, Tech. Memo MIT/LCS/TM-151, Mit Lab. for Comp. Sci. (1980) [Porte de Toffoli, automate réversible]. [↩]
4. E. Fredkin, T. Toffoli, “Conservative logic“, International Journal of Theoretical Physics, 21:3-4, 219-253 (1982) [Modèle de calcul balistique]. [↩]
5. R. P. Feynman, “Feynman lectures on computation (1984-1986)”, Perseus Books (2000) [↩]
6. C. H. Bennett, “The thermodynamics of computation - a review“, International Journal of Theoretical Physics, 21:12, 905-940 (1982) [Modèle de calcul Brownien; irréversibilité logique et démon de Maxwell]. [↩]
7. C. H. Bennett, “Logical reversibility of computation“, IBM Journal of Res. and Dev., 17:6 525 (1973). [Dans ce papier, lié au problème de la connexion entre calcul et génération de chaleur explorée par Landauer, Bennett proposa la méthode de “sauvegarde du résultat et renversement” et prouva que tout calcul irréversible peut être simulé réversiblement]. [↩]
8. Y. Lecerf, “Machines de Turing réversibles“, Comptes Rendus Hebdomadaires des Séances de L’académie des Sciences 257:2597-2600 (1963). [Dans ce papier mathématique, sans lien avec la question de l’irréversibilité physique, Lecerf a cherché à concevoir une machine de Turing réversible. C’est le premier ouvrage proposant la méthode de sauvegarde de l’histoire du calcul pour ensuite la “décalculer”, bien qu’il ait eu initialement peu d’impact et qu’il fut ‘découvert’ seulement après les résultats de Bennett, peut être car il ne fut pas publié en anglais et qu’il ne fut pas très appuyé par Lecerf. Il a une faille mineure, c’est à dire l’inverse d’un quintuple read-write-shift est un quintuple de type différent, à savoir shift-read-write]. [↩]
9. L. Szilard, “Über die Entropieverminderung in einem thermodynamischen System bei Eingriffen intelligenter Wesen“, Journal Zeitschrift für Physik, 53, 840-856 (1929); trad. anglaise “On the decrease of entropy in a thermodynamic system by the intervention of intelligent beings” in Behavioral Science, 9:4, 301-310 (1964). [↩]
10. D. Deutsch, “Quantum Theory, the Church-Turing Principle, and the Universal Quantum Computer“, Proc. Roy. Soc. Lond., A400, 97–117 (1985). [Fondation du modèle de calcul quantique, machine de Turing quantique universelle] [↩]
11. A. R. Calderbank, P. W. Shor, “Good quantum error-correcting codes exist“, Phys. Rev. A 54, 1098-1105 (1996). [↩]