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 del mapeo 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 y cuando 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 (ver Proceso adiabático ). Aunque en la práctica ningún proceso físico no estacionario puede ser exactamente reversible o isentrópico, no existe un límite conocido en cuanto a la cercanía con la que podemos aproximarnos a la reversibilidad perfecta, en sistemas que están suficientemente aislados de las interacciones con entornos externos desconocidos, cuando las leyes de la física Se conocen con precisión los datos 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 será 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á de los principios fundamentales de von Neumann. Límite de Landauer [3] [4] de kT ln(2) energía disipada por operación de bit irreversible . Aunque el límite de Landauer estaba millones de veces por debajo del consumo de energía de las computadoras en la década de 2000 y miles de veces menos en la década de 2010, [5] los defensores de la computación reversible argumentan que esto puede atribuirse en gran medida a los gastos generales arquitectónicos que efectivamente magnifican el impacto del límite de Landauer. límite en los diseños de circuitos prácticos, por lo que puede resultar difícil que la tecnología práctica avance mucho más allá de los niveles actuales de eficiencia energética si no se utilizan principios de 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 generar 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 estados computacionales antiguos a otros nuevos es una función uno a uno ; 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 son no 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 un solo valor , y el requisito necesario para obtener la 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 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 , como se refleja en la formulación general hamiltoniana de la mecánica y en el operador unitario de evolución temporal de la física cuántica . mecánica más específicamente. [8]
Por lo tanto, la implementación de la computación reversible equivale a aprender a caracterizar y controlar la dinámica física de los mecanismos para llevar a cabo las operaciones computacionales deseadas con tanta precisión 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 realiza. En otras palabras, rastrear con precisión el estado de la energía activa involucrada en la realización de 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 una forma organizada que pueda reutilizarse para operaciones posteriores, en lugar de que permitir que se disipe en forma de calor.
Si bien lograr este objetivo presenta un desafío importante 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 disipan mucho menos de kT ln 2 de energía para calentar) por cada operación lógica útil que llevan a cabo internamente.
Hoy en día, el campo cuenta con un cuerpo sustancial de literatura académica. Físicos , ingenieros eléctricos e 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 dispositivo lógico casi reversible, rentable y de alta calidad, que incluya mecanismos de sincronización y sincronización altamente eficientes energéticamente , o que evite la necesidad de estos mediante un diseño asincrónico. Este tipo de progreso sólido en ingeniería será necesario antes de que el gran conjunto de investigaciones teóricas sobre la 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 sólo puede evitarse mediante el uso de computación lógicamente reversible, debido a la segunda ley de la termodinámica . [9]
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, 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 puerta inversora (NO) es lógicamente reversible porque se puede deshacer . Sin embargo, es posible que la puerta NOT no sea físicamente reversible, dependiendo de su implementación.
La puerta exclusiva o (XOR) es irreversible porque sus dos entradas no pueden reconstruirse sin ambigüedades 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 puerta XOR, la puerta NOT controlada (CNOT), preservando una de las entradas como segunda salida. La variante de tres entradas de la puerta CNOT se llama puerta de Toffoli . Conserva dos de sus entradas a,b y reemplaza la tercera c por . Con esto se da la función AND, y con esto se da la función NOT. Debido a que AND y NOT juntos son un conjunto funcionalmente completo , la puerta de Toffoli es universal y puede implementar cualquier función booleana (si se le proporcionan suficientes bits ancilla inicializados ).
De manera similar, en el modelo de cálculo 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 aparentemente inconsciente del principio de Landauer, no prosiguió con 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 podría hacerse reversible tanto lógica como termodinámicamente [11] y, por lo tanto, capaz en principio de realizar un número arbitrariamente grande de pasos de cálculo por unidad de energía física disipada. si se opera con suficiente lentitud. Las computadoras termodinámicamente reversibles podrían realizar cálculos útiles a una velocidad útil, mientras disipan 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 una 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ó estas " Paradigmas browniano" y "balístico" para la computación 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 por 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 de 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 otro lugar como un efecto de calentamiento, suministrando 0,6931 kT por bit restaurado al entorno.
