La computación reversible es un modelo de computación en el que el proceso de computación es algo reversible . Por ejemplo, en un modelo computacional que usa conjuntos de estados y transiciones entre ellos, una condición necesaria para la reversibilidad de los cálculos es la posibilidad de construir un mapeo inequívoco (inyectivo) de cada estado al siguiente. Para el siglo XX y principios del siglo XXI, la computación reversible generalmente se conoce como modelos de computación no tradicionales.
Hay dos tipos principales de reversibilidad computacional: físicamente reversible y lógicamente reversible . [una]
El proceso es físicamente reversible si, al finalizar, el sistema no ha aumentado su entropía física , es decir, el proceso es isoentrópico . Circuitos físicamente reversibles: lógica de recuperación de carga (lógica de conservación de carga), circuitos adiabáticos , cálculos adiabáticos. En la práctica, un proceso físico no estacionario no puede ser completamente reversible físicamente (isentrópico); sin embargo, para sistemas bien aislados, es posible una aproximación a la reversibilidad completa.
Quizás el mayor incentivo para explorar tecnologías para implementar la computación reversible es que parecen ser la única forma de mejorar la eficiencia energética de la computación más allá de los límites fundamentales predichos por el principio de Neumann-Landauer [2] [3] , según el cual al menos Se libera kT ln(2) de calor (alrededor de 3×10 −21 J a T=300K) por cada operación irreversible en un bit (al borrar un bit de información). A principios del siglo XXI, las computadoras disipaban alrededor de un millón de veces más calor; a principios de la década de 2010, la diferencia se había reducido a varios miles [4] .
Como demostró Rolf Landauer de IBM en 1961 [3] , para que un cálculo sea físicamente reversible, también debe ser lógicamente reversible . En el principio de Landauer , fue el primero en formular la regla según la cual el borrado de N bits de información desconocida siempre está asociado con un aumento en la entropía termodinámica de al menos Nk ln(2). Un proceso de cómputo determinista discreto se llama lógicamente reversible si la función de transición que mapea el estado anterior del sistema al nuevo es inyectiva (cada nuevo estado corresponde únicamente a un estado anterior), es decir, es posible determinar la entrada lógica estado del circuito a partir de información sobre el estado lógico final del circuito.
Para procesos no deterministas (probabilísticos o aleatorios), la reversibilidad física se puede lograr con restricciones menos estrictas, es decir, con la condición de que el conjunto de todos los estados iniciales posibles (en promedio) no disminuya durante el cálculo.
Una de las primeras variantes [5] de la implementación de cálculos reversibles fue propuesta en los trabajos de Charles Bennett, [6] [7] (IBM Research, 1973). Actualmente, muchos científicos han propuesto docenas de conceptos de computación reversible, incluidas puertas lógicas reversibles, circuitos electrónicos, arquitecturas de procesadores, lenguajes de programación, algoritmos [8] [9] .
Para la implementación de esquemas computacionales reversibles y estimaciones de su complejidad y limitaciones, la formalización se utiliza a través de puertas reversibles, análogos de puertas lógicas. Por ejemplo, la puerta inversora NOT (NOT) es reversible, ya que almacena información. Al mismo tiempo, la puerta lógica OR exclusiva (XOR) es irreversible: los valores de sus entradas no se pueden restaurar a partir de un solo valor de salida. Un análogo reversible de XOR puede ser una puerta de negación controlada ( CNOT - NOT controlado).