¿Qué se sabe sobre la efectividad de la informática confiable?

¿Qué tan bien se ha investigado el siguiente problema en TCS? (¡Pido disculpas si la declaración del problema suena vaga!)

Dado un modelo de computación MC (máquina de Turing, autómatas celulares, máquina Kolmogorov-Uspenskii ... etc.) y un modelo de ruido que podría afectar la computación de MC, ¿hay alguna forma de recuperarse de los errores causados ​​por este ruido en una manera efectiva ? Por ejemplo, supongamos que algún tipo de ruido afecta a una máquina de Turing M, ¿podría uno idear una máquina de Turing M 'que simule M sin un costo importante y sea confiable (lo que significa que M' es tolerante a este ruido)?

Parece que algunos modelos de cálculos son mejores que otros para hacer esto: Autómatas celulares, por ejemplo. ¿Algún resultado si el ruido es reemplazado por un modelo adversario?

Perdón por la etiqueta! No tengo suficiente reputación para poner una etiqueta adecuada (computación confiable, computación tolerante a fallas ... etc.)

Si bien hay algunas técnicas que se pueden aplicar a la tolerancia a fallas para todos los modelos, la resistencia de un modelo computacional a la tolerancia a fallas depende del modelo. Por ejemplo, Peter Gacs ha investigado bastante con tolerancia a fallas en autómatas celulares, y muestra que (con mucho trabajo) puede construir autómatas celulares tolerantes a fallas.

Von Neumann demostró que al usar la redundancia, se podía construir una computadora confiable a partir de componentes poco confiables usando solo una sobrecarga logarítmica.

Para el cómputo cuántico, los circuitos cuánticos pueden ser tolerantes a fallas con sobrecarga pollogarítmica ( sobrecarga, donde encontrar el valor correcto de c todavía está abierto). Otra pregunta abierta para la computación cuántica es si la computación cuántica adiabática puede ser tolerante a fallas de una manera físicamente razonable (físicamente razonable significa que es posible que el método conduzca a una computadora cuántica adiabática escalable; por ejemplo, no está permitido tomar el temperatura a 0 a medida que aumenta el tamaño del cálculo).$\log^c n$$c$

Creo que el trabajo relacionado con la autoestabilización está cerca del espíritu de su pregunta.

Un sistema autoestabilizador se recupera de cualquier corrupción de la RAM.

La pregunta que se hace es "¿Hay alguna forma de recuperarse de los errores causados ​​por el ruido [cuántico] de manera efectiva?" y la respuesta de Peter Shor admirablemente cubre una forma efectiva de responder a esta pregunta, es decir, diseñando computadoras cuánticas tolerantes a fallas.

Una forma efectiva alternativa se encuentra muy comúnmente en la práctica de la ingeniería. Razonamos "Si el ruido es lo suficientemente grande como para que no sea factible el cálculo cuántico, entonces quizás la dinámica del sistema pueda simularse con recursos clásicos en P."

En otras palabras, a menudo podemos "recuperarnos de manera efectiva" del ruido al reconocer que el ruido nos proporciona un servicio importante, al reducir exponencialmente la complejidad computacional de la simulación de los sistemas clásicos y cuánticos.

La literatura sobre enfoques centrados en el ruido para la simulación dinámica es grande y creciente; Una referencia reciente cuyos teoremas están motivados físicamente y son rigurosamente agradables, y que incluye muchas referencias a la literatura más amplia, son los límites superiores de Plenio y Virmani en los umbrales de tolerancia a fallas de las computadoras cuánticas ruidosas basadas en Clifford (arXiv: 0810.4340v1).

Los dinámicos dinámicos usan un lenguaje muy diferente en el que los mecanismos de ruido se denominan técnicos como termostatos ; Simulación molecular de Frenkel y Smit : de algoritmos a aplicaciones (1996) proporciona una introducción matemática básica.

Cuando transcribimos termostatos clásicos y cuánticos al lenguaje de la dinámica geométrica, encontramos (como era de esperar) que los métodos clásicos y cuánticos para explotar el ruido para aumentar la eficiencia de la simulación son esencialmente idénticos; que sus publicaciones respectivas con poca frecuencia se refieren entre sí es en gran medida un accidente de la historia que ha sido sostenido por obstrucciones notacionales.

De manera menos rigurosa pero más general, los resultados anteriores iluminan los orígenes de la teoría de la información cuántica de una regla heurística ampliamente aceptada por químicos, físicos y biólogos, de que cualquier sistema clásico o cuántico que esté en contacto dinámico con un baño termal probablemente probar simulable con recursos computacionales en P para todos los fines prácticos (FAPP).

Las excepciones a esta heurística, tanto clásica como cuántica, representan importantes problemas abiertos. Su número disminuye notablemente año tras año; La evaluación crítica bienal de predicción de estructura (CASP) proporciona una medida objetiva de esta mejora.

Los límites fundamentales para este progreso impulsado por el ruido, de muchas décadas "Más que Moore" en la capacidad de simulación son actualmente imperfectamente conocidos. Huelga decir que, a la larga, nuestra comprensión constante de estos límites nos acercará a la construcción de computadoras cuánticas, mientras que a corto plazo, este conocimiento nos ayuda enormemente a simular de manera eficiente sistemas que no son computadoras cuánticas. De cualquier manera, son buenas noticias.

Parece que Gacs está en camino de construir una máquina de Turing tolerante a fallas. Echa un vistazo a esto: http://arxiv.org/abs/1203.1335

Los modelos de computación cuántica abordan explícitamente el ruido y las formas de hacer que los cálculos sean resistentes a los errores introducidos a través de este vector. La computación cuántica, curiosamente, se puede hacer hacia adelante y hacia atrás (por la naturaleza de las transformaciones de QM Hadamard y la independencia temporal del hamiltoniano): "no computar" es una técnica utilizada para detener la marea de tales errores.

En computadoras 'reales' - servidores empresariales - existe una pequeña pero factible posibilidad de que se lea incorrectamente un poco de RAM. La teoría de los códigos de detección y corrección de errores se puede aplicar a nivel de palabra de máquina para detectar y corregir dichos errores de 1 bit (sin demasiada sobrecarga). Y, de hecho, muchos servidores Enterprise que tienen operaciones críticas invitan a un pequeño bit de paridad en cada palabra de RAM.

Aunque lejos de ser una prueba, me parece que los esquemas de codificación de corrección de errores estándar podrían funcionar con casi cualquier autómata teórico (los autómatas celulares son sospechosos) con solo una desaceleración polinómica (¿de hecho lineal?).

Se trabaja en estructuras y algoritmos de datos llamados "resistentes" (árboles de búsqueda, contadores, diccionario). El modelo es el de una RAM con la suposición de que hasta$k$Los bits pueden ser modificados por un adversario en cualquier momento. Constantemente muchos registros no pueden ser modificados por el adversario. Dependiendo del parámetro$k$, puede obtener algoritmos que aún funcionan correctamente y cuya dependencia del tiempo de ejecución en $k$ es mejor que correr $k$copias independientes de un algoritmo. Una reciente charla invitada de G. Italiano debería dar una visión general: Algoritmos resilientes y estructuras de datos (acabo de encontrar este artículo y aún no lo leí, pero estoy seguro de que es un buen indicador).