Computación reversible

La computación reversible es cualquier modelo de computación en el que cada paso del proceso es reversible en el tiempo . Esto significa que, dado el resultado de una computación, es posible reconstruir perfectamente la entrada. En sistemas que progresan determinísticamente de un estado a otro, un requisito clave para la reversibilidad es una correspondencia biunívoca entre cada estado y su sucesor. La computación reversible se considera un enfoque no convencional de la computación y está estrechamente vinculada a la computación cuántica , donde los principios de la mecánica cuántica garantizan inherentemente la reversibilidad (siempre que los estados cuánticos no se midan ni se " colapsen "). ^{[ 1 ]}

Hay dos tipos principales de reversibilidad, estrechamente relacionados, que son de particular interés para este propósito: la reversibilidad física y la reversibilidad lógica . ^{[ 2 ]}

Se dice que un proceso es físicamente reversible si no produce un aumento de la entropía física ; es decir, es isentrópico . Existe un estilo de diseño de circuitos que idealmente exhibe esta propiedad, conocido como lógica de recuperación de carga , circuitos adiabáticos o computación adiabática (véase proceso adiabático ). Si bien en la práctica ningún proceso físico no estacionario puede ser exactamente físicamente reversible o isentrópico, no se conoce ningún límite a la proximidad con la que podemos aproximarnos a la reversibilidad perfecta en sistemas suficientemente aislados de interacciones con entornos externos desconocidos, cuando se conocen con precisión las leyes de la física que describen la evolución del sistema.

Una motivación para el estudio de tecnologías destinadas a implementar la computación reversible es que ofrecen lo que se predice que es la única forma potencial de mejorar la eficiencia energética computacional (es decir, operaciones útiles realizadas por unidad de energía disipada) de las computadoras más allá del límite fundamental de von Neumann-Landauer ^{[ 3 ] [ 4 ]} de kT ln(2) energía disipada por operación de bit irreversible .

El límite de Landauer fue millones de veces inferior al consumo energético de los ordenadores en la década de 2000 y miles de veces menor en la década de 2010. ^{[ 5 ]} Los defensores de la computación reversible argumentan que una parte significativa de este consumo energético se debe a los costes generales de la arquitectura. Estos costes generales son los costes energéticos asociados a las partes no computacionales del sistema, como los cables, los transistores y la memoria, que son necesarios para que un ordenador funcione. Creen que esto dificulta que la tecnología actual logre una mayor eficiencia energética sin adoptar los principios de la computación reversible. ^{[ 6 ]}

Como argumentó por primera vez Rolf Landauer mientras trabajaba en IBM , ^{[ 7 ]} para que un proceso computacional sea físicamente reversible, también debe ser lógicamente reversible . El principio de Landauer es la observación de que el borrado inconsciente de n bits de información conocida siempre debe incurrir en un costo de nkT ln(2) en entropía termodinámica . Se dice que un proceso computacional discreto y determinista es lógicamente reversible si la función de transición que mapea los estados computacionales antiguos a los nuevos es una función biyectiva ; es decir, los estados lógicos de salida determinan de forma única los estados lógicos de entrada de la operación computacional.

Para los procesos computacionales que no son deterministas (en el sentido de ser probabilísticos o aleatorios), la relación entre los estados antiguos y nuevos no es una función unívoca , y el requisito necesario para obtener reversibilidad física se convierte en una condición ligeramente más débil, a saber, que el tamaño de un conjunto dado de posibles estados computacionales iniciales no disminuya, en promedio, a medida que avanza el cálculo.

El principio de Landauer (y, de hecho, la segunda ley de la termodinámica ) también puede entenderse como una consecuencia lógica directa de la reversibilidad subyacente de la física , tal como se refleja en la formulación hamiltoniana general de la mecánica y, más específicamente, en el operador unitario de evolución temporal de la mecánica cuántica . ^{[ 8 ]}

La implementación de la computación reversible consiste, por lo tanto, en aprender a caracterizar y controlar la dinámica física de los mecanismos para llevar a cabo las operaciones computacionales deseadas con tal precisión que el experimento acumule una incertidumbre total insignificante respecto al estado físico completo del mecanismo, por cada operación lógica realizada. En otras palabras, se trata de rastrear con precisión el estado de la energía activa involucrada en la ejecución de las operaciones computacionales dentro de la máquina, y diseñar la máquina de manera que la mayor parte de esta energía se recupere de forma organizada y pueda reutilizarse en operaciones posteriores, en lugar de permitir que se disipe en forma de calor.

Si bien lograr este objetivo representa un desafío significativo para el diseño, la fabricación y la caracterización de nuevos mecanismos físicos ultraprecisos para la computación , actualmente no existe ninguna razón fundamental para pensar que este objetivo no pueda alcanzarse eventualmente, permitiendo algún día construir computadoras que generen mucho menos del valor de 1 bit de entropía física (y disipen mucho menos de kT ln 2 de energía en forma de calor) por cada operación lógica útil que realicen internamente.

Actualmente, este campo cuenta con una amplia bibliografía académica. Físicos, ingenieros eléctricos e informáticos han diseñado y analizado una gran variedad de conceptos de dispositivos reversibles, puertas lógicas , circuitos electrónicos , arquitecturas de procesadores , lenguajes de programación y algoritmos de aplicación.

Este campo de investigación aguarda el desarrollo detallado de una tecnología de dispositivos lógicos de alta calidad, rentable y prácticamente reversible , que incluya mecanismos de sincronización y reloj de alta eficiencia energética , o que evite la necesidad de estos mediante un diseño asíncrono. Este tipo de progreso de ingeniería sólido será necesario antes de que el amplio conjunto de investigaciones teóricas sobre computación reversible pueda encontrar una aplicación práctica que permita a la tecnología informática real sortear las diversas barreras a corto plazo para su eficiencia energética, incluido el límite de von Neumann-Landauer. Esto solo puede sortearse mediante el uso de computación lógicamente reversible, debido a la segunda ley de la termodinámica . ^{[ 9 ]}

Para que una operación computacional sea lógicamente reversible, su salida (o estado final) puede calcularse a partir de su entrada (o estado inicial), y viceversa. Las funciones reversibles deben ser inyectivas . Esto significa que las compuertas reversibles (y los circuitos , es decir, las composiciones de múltiples compuertas) generalmente tienen el mismo número de bits de entrada que de salida (suponiendo que todos los bits de entrada son utilizados por la operación).

Una puerta inversora (NOT) es lógicamente reversible porque su operación puede deshacerse . Sin embargo, dependiendo de su implementación, la puerta NOT puede no ser físicamente reversible.

La compuerta XOR ( o exclusiva ) es irreversible porque sus dos entradas no pueden reconstruirse inequívocamente a partir de su única salida, o bien, porque el borrado de información no es reversible. Sin embargo, se puede definir una versión reversible de la compuerta XOR —la compuerta NOT controlada (CNOT)— conservando una de las entradas como segunda salida. La variante de tres entradas de la compuerta CNOT se denomina compuerta Toffoli . Conserva dos de sus entradas a,b y reemplaza la tercera c por${\displaystyle c\oplus (a\cdot b)}$. Con${\displaystyle c=0}$, esto da la función AND, y con${\displaystyle a\cdot b=1}$Esto da como resultado la función NOT. Dado que AND y NOT juntas forman un conjunto funcionalmente completo , la puerta lógica Toffoli es universal y puede implementar cualquier función booleana (si se le proporcionan suficientes bits auxiliares inicializados ).

Se encuentran disponibles estudios sobre circuitos reversibles, su construcción y optimización , así como los desafíos de investigación recientes. ^{[ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ]}

La máquina de Turing reversible (MTR) es un modelo fundamental en la computación reversible. Una MTR se define como una máquina de Turing cuya función de transición es invertible, lo que garantiza que cada configuración de la máquina (estado y contenido de la cinta) tenga como máximo una configuración predecesora. Esto garantiza el determinismo hacia atrás, lo que permite rastrear de forma unívoca el historial de computación. ^{[ 15 ]}

Las definiciones formales de RTM han evolucionado en las últimas décadas. Si bien las primeras definiciones se centraban en funciones de transición invertibles, las formulaciones más generales permiten un movimiento de cabeza limitado y la modificación de celdas por paso. Esta generalización garantiza que el conjunto de RTM sea cerrado bajo composición (ejecutando RTM${\displaystyle A}$seguido de la ejecución de RTM${\displaystyle B}$da como resultado una nueva RTM) e inversión (la inversa de una RTM también es una RTM), formando una estructura de grupo para cálculos reversibles. Esto contrasta con algunas definiciones clásicas de TM donde la composición podría no producir una máquina de la misma clase. ^{[ 16 ]} La dinámica de una RTM se puede describir mediante una función de transición global que asigna configuraciones basadas en una regla local. ^{[ 17 ]}

Yves Lecerf propuso una máquina de Turing reversible en un artículo de 1963, ^{[ 18 ]} pero aparentemente desconocía el principio de Landauer, no profundizó en el tema y dedicó la mayor parte del resto de su carrera a la etnolingüística.

Un resultado trascendental de Charles H. Bennett en 1973 demostró que cualquier máquina de Turing estándar puede ser simulada por una reversible. ^{[ 19 ]} La construcción de Bennett implica aumentar la TM con una "cinta de historial" auxiliar. La simulación procede en tres etapas: ^{[ 20 ]}

1. Cálculo: Se simula el cálculo de la máquina de Turing original y se escribe en la cinta de historial un registro de cada regla de transición aplicada.
2. Copia de salida: El resultado final de la cinta de trabajo se copia a una cinta de salida separada, inicialmente en blanco. Esta operación de copia debe realizarse de forma reversible (por ejemplo, utilizando compuertas CNOT).
3. Descomputación: La simulación se ejecuta en sentido inverso, utilizando la cinta de historial para deshacer cada paso del cálculo directo. Este proceso borra la cinta de trabajo y la cinta de historial, devolviéndolas a su estado inicial en blanco, dejando únicamente la entrada original (conservada en su cinta) y la salida final en la cinta de salida.

Esta construcción demuestra que las RTM son computacionalmente equivalentes a las TM estándar en términos de las funciones que pueden calcular, estableciendo que la reversibilidad no limita la potencia computacional en este sentido. ^{[ 20 ]} Sin embargo, esta técnica de simulación estándar tiene un costo. La cinta de historial puede crecer linealmente con el tiempo de cálculo, lo que conlleva una sobrecarga de espacio potencialmente grande, a menudo expresada como${\displaystyle S'(n)=O(S(n)T(n))}$dónde${\displaystyle S}$y${\displaystyle T}$son el espacio y el tiempo del cálculo original. ^{[ 19 ]} Además, los enfoques basados ​​en el historial presentan desafíos con la composicionalidad local; combinar dos cálculos reversibles independientemente utilizando este método no es sencillo. Esto indica que, si bien es teóricamente potente, la construcción original de Bennett no es necesariamente la forma más práctica o eficiente de lograr un cálculo reversible, lo que motiva la búsqueda de métodos que eviten acumular grandes cantidades de historial "basura". ^{[ 20 ]}

Las RTM calculan con precisión el conjunto de funciones computables inyectivas (uno a uno). No son estrictamente universales en el sentido clásico porque no pueden calcular directamente funciones no inyectivas (que inherentemente pierden información). Sin embargo, poseen una forma de universalidad denominada "universalidad RTM" y son capaces de autointerpretarse. ^{[ 15 ]}

La empresa Vaire Computing, con sede en Londres , está desarrollando un prototipo de chip en 2025, para su lanzamiento en 2027. ^{[ 21 ]}

• Frank, Michael P. (2017). "El futuro de la computación depende de hacerla reversible" (web) / "Invertir la computación" (impreso). IEEE Spectrum . 54 (9): 32–37. doi:10.1109/MSPEC.2017.8012237 .
• Denning, Peter; Lewis, Ted (2017). "Computadoras que pueden funcionar al revés". American Scientist . 105 (5): 270. doi : 10.1511/2017.105.5.270 . hdl : 10945/59278 . S2CID 125446656 . 
• Glück, Robert; Yokoyama, Tetsuo (2023). "Computación reversible desde la perspectiva de un lenguaje de programación" . Theoretical Computer Science . 953 113429. doi : 10.1016/j.tcs.2022.06.010 .
• Lange, Klaus-Jörn; McKenzie, Pierre; Tapp, Alain (abril de 2000). "El espacio reversible es igual al espacio determinista" . Journal of Computer and System Sciences . 60 (2): 354– 367. doi : 10.1006/jcss.1999.1672 .
• Perumalla KS (2014), Introducción a la computación reversible , CRC Press .
• Vitányi, Paul (2005). «Tiempo, espacio y energía en la computación reversible». Actas de la 2.ª conferencia sobre fronteras de la computación – CF '05 . pp. 435–444 . arXiv : cs/0504088 . doi : 10.1145/1062261.1062335 . ISBN  1-59593-019-1. S2CID 5252384 . 

• Artículo introductorio sobre computación reversible
• Primer Taller Internacional sobre Computación Reversible
• Publicaciones de Michael P. Frank: Sandia (2015-) , FSU (2004-'15) , UF (1999-2004) , MIT (1996-'99 ).
• Ciclo de talleres/conferencias sobre computación reversible
• Taller de la CCC sobre cuestiones de física e ingeniería en computación clásica adiabática/reversible.
• Kit de herramientas de código abierto para el diseño de circuitos reversibles