Entropía y complejidad computacional

Hay investigadores que muestran que el bit de borrado tiene que consumir energía, ¿hay alguna investigación sobre el consumo promedio de energía del algoritmo con complejidad computacional ? Supongo que la complejidad computacional está correlacionada con el consumo promedio de energía, espero poder obtener alguna respuesta aquí.$F(n)$$F(n)$

Sí, pero la mayor parte del trabajo hasta ahora (excepto muy recientemente, ver más abajo) se ha centrado en convertir los cálculos irreversibles en reversibles, con la esperanza de evitar cualquier generación de entropía. (Nota: existe una diferencia importante entre la energía necesaria para realizar un cálculo y la entropía generada por el cálculo y expulsada al medio ambiente, generalmente en forma de calor).

Basado en el análisis original de Landauer y Bennett de que borrar un poco "debe" generar la entropía (ver a continuación por qué hay comillas de miedo), varios investigadores han seguido varias preguntas en esta línea. Una línea de investigación fue simular máquinas de Turing irreversibles por máquinas reversibles, lo que, se sugirió, no generaría entropía. Hay varios trabajos que muestran compensaciones espacio-tiempo sobre cómo simular TM irreversibles por las reversibles, por ejemplo:$kT \ln(2)$

• Bennett, intercambios tiempo / espacio para computación reversible . SICOMP 1989

• Levine y Sherman. Una nota sobre el intercambio tiempo-espacio de Bennett para la computación reversible . SICOMP 1990.

• Li y Vitanyi. Simulación reversible de computación irreversible . CCC 1996

• Lange, McKenzie y Tapp. El espacio reversible es igual al espacio determinista . JCSS 2000.

Más recientemente,

Demaine, Lynch, Mirano y Tyagi. Algoritmos de eficiencia energética , 2016.

estudió algoritmos parcialmente reversibles, es decir, si está dispuesto a pagar algo de entropía, para las tareas algorítmicas estándar se pueden mejorar las simulaciones generales irreversibles a reversibles mencionadas anteriormente. La informática reversible tiene toda una comunidad de investigadores dedicados a ella, a saber. la conferencia de computación reversible , ahora en su décimo año.

De hecho, se sabe desde hace mucho tiempo, desde Landauer y Bennett, que la relación entre la irreversibilidad computacional y la generación de entropía es más sutil de lo que sugiere el lema "borrar un bit genera entropía". " Sin embargo, en los últimos 20 años, más o menos, la mecánica estadística de no equilibrio ha avanzado hasta el punto de que esta relación más sutil se puede capturar mediante ecuaciones numéricas precisas que involucran no solo la diferencia de entropía, sino también una diferencia de divergencias de KL, ver$\ln(2)$

Kolchinsky y Wolpert, Dependencia de la disipación en la distribución inicial sobre los estados . J. Stat. Mech 2017 ( enlace arXiv )

(y referencias en el mismo).

Organizamos un taller sobre esto en el Instituto Santa Fe en agosto de 2017 (donde puedes ver los nombres de algunos investigadores y hablar de títulos relevantes), y plantea un nuevo conjunto de preguntas tanto en física como en complejidad computacional termodinámica.