La computación reversible es cualquier modelo de computación en el que el proceso computacional , hasta cierto punto, es reversible en el tiempo . En un modelo de computación que utiliza transiciones deterministas de un estado de la máquina abstracta a otro, una condición necesaria para la reversibilidad es que la relación de la aplicación de los estados a sus sucesores debe ser uno a uno . La computación reversible es una forma de computación no convencional .
Debido a la unitaridad de la mecánica cuántica , los circuitos cuánticos son reversibles, siempre que no “ colapsen ” los estados cuánticos sobre los que operan. [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 ningún aumento de la entropía física ; es isentrópico . Existe un estilo de diseño de circuitos que exhibe idealmente esta propiedad y que se conoce como lógica de recuperación de carga , circuitos adiabáticos o computación adiabática (véase Proceso adiabático ). Aunque en la práctica ningún proceso físico no estacionario puede ser exactamente reversible físicamente o isentrópico, no se conoce ningún límite a la proximidad con la que podemos aproximarnos a la reversibilidad perfecta, en sistemas que están suficientemente bien aislados de las interacciones con entornos externos desconocidos, cuando las leyes de la física que describen la evolución del sistema se conocen con precisión.
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 . Aunque el límite de Landauer era millones de veces menor que el consumo de energía de las computadoras 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 esto se puede atribuir en gran medida a los costos generales de arquitectura que efectivamente magnifican el impacto del límite de Landauer en los diseños de circuitos prácticos, de modo que puede resultar difícil para la tecnología práctica progresar mucho más allá de los niveles actuales de eficiencia energética si no se utilizan los principios de computación reversible. [6]
Como lo 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 asigna los estados computacionales antiguos a los nuevos es una función uno a uno ; es decir, los estados lógicos de salida determinan de manera ú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 de valor único , 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 disminuye, en promedio, a medida que el cálculo avanza.
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 , 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 equivale, por tanto, a aprender a caracterizar y controlar la dinámica física de los mecanismos para llevar a cabo las operaciones computacionales deseadas de forma tan precisa que el experimento acumule una cantidad total insignificante de incertidumbre con respecto al estado físico completo del mecanismo, por cada operación lógica que se realice. En otras palabras, rastrear con precisión el estado de la energía activa que interviene en la realización de las operaciones computacionales dentro de la máquina y diseñar la máquina de forma que la mayor parte de esta energía se recupere en una forma organizada que pueda reutilizarse para operaciones posteriores, en lugar de permitir que se disipe en forma de calor.
Aunque alcanzar este objetivo presenta 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 , en la actualidad no hay ninguna razón fundamental para pensar que este objetivo no pueda lograrse eventualmente, permitiendo algún día construir computadoras que generen mucho menos de 1 bit de entropía física (y disipen mucho menos de kT ln 2 de energía en calor) por cada operación lógica útil que realicen internamente.
En la actualidad, el campo cuenta con un importante volumen de literatura académica. Físicos , ingenieros eléctricos y científicos informáticos han diseñado y analizado una amplia 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 espera el desarrollo detallado de una tecnología de dispositivos lógicos casi reversibles, de alta calidad y rentable, que incluya mecanismos de sincronización y reloj de alta eficiencia energética o que evite la necesidad de estos mediante un diseño asincrónico. Este tipo de sólido progreso de ingeniería será necesario antes de que el gran cuerpo de investigación teórica 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 se puede sortear 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 significa que la salida (o estado final) de la operación se puede calcular a partir de la entrada (o estado inicial), y viceversa. Las funciones reversibles son biyectivas . Esto significa que las puertas reversibles (y los circuitos , es decir, las composiciones de múltiples puertas) generalmente tienen el mismo número de bits de entrada que de bits de salida (asumiendo que todos los bits de entrada son consumidos por la operación y que todos los estados de entrada/salida son posibles).
Una compuerta inversora (NOT) es lógicamente reversible porque se puede deshacer . Sin embargo, la compuerta NOT puede no ser físicamente reversible, dependiendo de su implementación.
La compuerta exclusiva o (XOR) es irreversible porque sus dos entradas no se pueden reconstruir de forma inequívoca a partir de su única salida o, alternativamente, 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 o 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 . Con , esto da la función AND, y con esto da la función NOT. Debido a que AND y NOT juntos son un conjunto funcionalmente completo , la compuerta Toffoli es universal y puede implementar cualquier función booleana (si se le dan suficientes bits ancilla inicializados ).
De manera similar, en el modelo de computación de la máquina de Turing , una máquina de Turing reversible es aquella cuya función de transición es invertible, de modo que cada estado de la máquina tiene como máximo un predecesor.
Yves Lecerf propuso una máquina de Turing reversible en un artículo de 1963, [10] pero, al parecer, al no conocer el principio de Landauer, no profundizó en el tema y dedicó la mayor parte del resto de su carrera a la etnolingüística. En 1973, Charles H. Bennett , de IBM Research, demostró que una máquina de Turing universal podía ser reversible tanto lógica como termodinámicamente, [11] y, por lo tanto, capaz en principio de realizar una cantidad arbitrariamente grande de pasos de cálculo por unidad de energía física disipada, si se operaba con la suficiente lentitud. Las computadoras termodinámicamente reversibles podrían realizar cálculos útiles a una velocidad útil, mientras que disipaban considerablemente menos de kT de energía por paso lógico. En 1982, Edward Fredkin y Tommaso Toffoli propusieron la computadora de bolas de billar , un mecanismo que utiliza esferas duras clásicas para realizar cálculos reversibles a velocidad finita con disipación cero, pero que requiere una alineación inicial perfecta de las trayectorias de las bolas, y la revisión de Bennett [12] comparó estos paradigmas "browniano" y "balístico" para el cálculo reversible. Aparte de la motivación de la computación energéticamente eficiente, las puertas lógicas reversibles ofrecieron mejoras prácticas de las transformaciones de manipulación de bits en criptografía y gráficos de computadora. Desde la década de 1980, los circuitos reversibles han atraído interés como componentes de algoritmos cuánticos y, más recientemente, en tecnologías fotónicas y de nanocomputación donde algunos dispositivos de conmutación no ofrecen ganancia de señal .
Se encuentran disponibles estudios sobre circuitos reversibles, su construcción y optimización, así como desafíos de investigación recientes. [13] [14] [15] [16] [17]
La entropía de un sistema cerrado, por ejemplo, una computadora con sus propias baterías, no puede disminuir; por lo tanto, esta entropía debe aparecer en otra parte como un efecto de calentamiento, suministrando 0,6931 kT por bit restaurado al entorno.
