¿Qué tiene de malo el método de "guardar la entrada" de la computación reversible?

Soy un estudiante universitario que recién comienza a leer sobre informática reversible. Sé que, debido al principio de Landauer, los cálculos irreversibles disipan el calor (y los reversibles no). Lo mencioné con mi profesor, que nunca antes había oído hablar de la computación reversible, y estaba teniendo dificultades para entender por qué la teoría de la computación reversible no era trivial.

Su punto era que siempre puede guardar la entrada, es decir, para cualquier función que desee hacer reversible, defina una nueva función f r e v e r s i b l e : { 0 , 1 } n → { 0 , 1 } 2 n (o { 0 , 1 } 2 $f: \{ 0, 1 \}^n \rightarrow \{ 0, 1 \}^n$$f_{reversible}: \{ 0, 1 \}^n \rightarrow \{0, 1 \}^{2n}$ y solo pone 0 s para los últimos n bits de la entrada) que devuelve la salida en los primeros n bits y la entrada en los otros n bits. Luego, para invertir f r e v e r s i b l e , simplemente descarte la salida y devuelva la entrada que guardó.$\{ 0, 1 \}^{2n} \rightarrow \{0, 1 \}^{2n}$$0$$n$$n$$n$$f_{reversible}$

Mi objeción inmediata fue que esto requiere más memoria que la función original, aunque solo por un factor constante. Sin embargo, restringir la salida a bits parecería restablecer el interés del problema. ¿Es esto lo que generalmente se entiende por computación reversible?$n$

Otra objeción parecía ser que cuando descartamos la salida, estamos haciendo algo irreversible que va a disipar el calor. Pero recuperamos correctamente el estado inicial, entonces, ¿cómo podría ser irreversible? No sé lo suficiente de física para entender si lo importante con calor es que todo el cálculo sea reversible, o si cada paso también debe ser reversible, o si esta idea está en el árbol equivocado .

Hay dos características importantes de la computación reversible que faltan en su discusión sobre la computación reversible:

1. Una función reversible tiene que ser una biyección, y
2. La reversibilidad se define en el nivel de las puertas locales, no solo en el nivel global.

En particular, para su extensión de en { 0 , 1 } 2 n → { 0 , 1 } 2 n al copiar, no garantiza la biyección porque no explique qué sucede cuando los últimos n bits de entrada para su función no son 0 n .$\{0,1\}^n \rightarrow \{0,1\}^n$$\{0,1\}^{2n} \rightarrow \{0,1\}^{2n}$$n$$0^n$

En cuanto al segundo punto, esa es realmente la parte esencial de la computación reversible desde la perspectiva de la física. El proceso físico no puede simplemente "deshacer" el calentamiento a nivel global, por lo tanto, cada puerta debe ser reversible para que el circuito sea reversible en el sentido relevante para la física.

Finalmente, la teoría de la computación reversible no es irrazonablemente complicada, pero definitivamente no es trivial. En particular, hay algunos circuitos que pueden implementarse con estrictamente menos registros / cables de manera no reversible de lo que pueden ser reversiblemente. Sin embargo, el estallido al pasar de no reversible a reversible no es tan malo.

En general, rara vez escucho computación reversible en los cursos clásicos de CS, porque rara vez es relevante para la computación clásica. Sin embargo, es un tema importante en la computación cuántica porque todos los circuitos cuánticos son reversibles y porque uno tiene que manejar con cuidado lo que está en sus cables 'basura' para evitar enredos innecesarios.