Computadoras análogas y la tesis de Church-Turing

Quisiera citar a Nielsen & Chuang, Computación Cuántica e Información Cuántica, edición del décimo aniversario, página 5 (énfasis mío):

Una clase de desafíos para la fuerte tesis de Iglesia-Turing proviene del campo de la computación analógica. En los años posteriores a Turing, muchos equipos diferentes de investigadores han notado que ciertos tipos de computadoras analógicas pueden resolver eficientemente problemas que se cree que no tienen una solución eficiente en una máquina Turing. A primera vista, estas computadoras analógicas parecen violar la fuerte forma de la tesis de la Iglesia-Turing. Desafortunadamente para la computación analógica, resulta que cuando se hacen suposiciones realistas sobre la presencia de ruido en las computadoras analógicas, su potencia desaparece en todos los casos conocidos; no pueden resolver eficientemente problemas que no pueden resolverse eficientemente en una máquina Turing.Esta lección, que los efectos del ruido realista deben tenerse en cuenta al evaluar la eficiencia de un modelo computacional, fue uno de los grandes desafíos iniciales de la computación cuántica y la información cuántica, un desafío que se logró con éxito mediante el desarrollo de una teoría del error cuántico. -códigos de corrección y computación cuántica tolerante a fallas. Por lo tanto, a diferencia del cómputo analógico, el cómputo cuántico puede tolerar en principio una cantidad finita de ruido y aún conservar sus ventajas computacionales.

¿Es esta una afirmación de que el ruido escala más rápido que alguna potencia del tamaño del problema, o alguien puede señalarme en la dirección correcta para que pueda obtener más información sobre si estos límites de escala son fundamentales o simplemente un "problema de ingeniería"?

Para ser claros, estoy preguntando si las computadoras analógicas no pueden vencer a las máquinas Turing en eficiencia debido al ruido.

En primer lugar, los autores parecen confundir dos tesis diferentes: la tesis de Church-Turing y la tesis de Cook-Karp. El primero se refiere a lo que es computable, y el segundo se refiere a lo que es computable de manera eficiente .

De acuerdo con la tesis de Cook-Karp, todos los modelos computacionales "fuertes" razonables son polinomialmente equivalentes, en el sentido de que todos simulan polinomialmente entre sí. De manera equivalente, cada modelo computacional razonable puede ser simulado polinomialmente por una máquina Turing. Las computadoras cuánticas son un contraejemplo de esta tesis, ya que parecen ser exponencialmente más eficientes que las computadoras clásicas. Sin embargo, no son un contraejemplo de la tesis de la Iglesia-Turing, es decir, usando computadoras cuánticas no puedes calcular nada que no puedas calcular con una máquina de Turing. También podemos formular una tesis actualizada de Cook-Karp, declarando que todos los modelos computacionales físicamente realizables son simulados polinomialmente por computadoras cuánticas.

Se han propuesto varios modelos físicos de cómputos que desafían estas tesis, pero bajo escrutinio, todos parecen no violar la tesis de la Iglesia-Turing, o no ser más poderosos que el cómputo cuántico. Scott Aaronson propone considerar esta situación como una "ley de la naturaleza". Sin embargo, hasta donde yo sé, no hay argumentos teóricos que respalden estas tesis más que el argumento inductivo de que todos los modelos que se han propuesto han demostrado ajustarse a ellos.

ese pasaje (escrito hace más de una década) es realmente clave e invoca bastante conocimiento previo y anticipa muy bien algunas direcciones de investigación futuras. Está aludiendo al campo de la hipercomputación que a veces está al margen de TCS, porque estudia modelos de computación que supuestamente son "más potentes" que las máquinas de Turing. El punto interesante acerca de las máquinas de Turing aquí es que tienen cero ruido, por lo que, en cierto sentido, la informática se basa en esta idealización que, en algunos aspectos, es físicamente poco realista. y los sistemas electrónicos imitan esta falta de ruido como un principio de diseño, siempre está presente en la dinámica de chip de bajo nivel, pero se abstrae de manera muy efectiva en los diseños de nivel superior que restringen todas las señales eléctricas a 0/1 bits ideales. re esto:

Esta lección, que los efectos del ruido realista deben tenerse en cuenta al evaluar la eficiencia de un modelo computacional, fue uno de los grandes desafíos iniciales de la computación cuántica y la información cuántica, un desafío que se logró con éxito mediante el desarrollo de una teoría del error cuántico. -códigos de corrección y computación cuántica tolerante a fallas.

parecería que algunas de sus afirmaciones se ven bastante prematuramente optimistas en retrospectiva. Es cierto que se han ideado grandes cantidades de teoría en los códigos de corrección de errores de QM. Sin embargo, muy poco ha sido probado y verificado experimentalmente. Hay algunos científicos / expertos que sospechan / plantean la hipótesis de que pueden existir leyes físicas que requieren que el ruido se escale de una manera "mala" para los sistemas cuánticos de n bits más grandes. Es un área de investigación activa y cierta controversia. de hecho, esta es un área clave de disputa para dos diseños / enfoques de computación QM líderes, uno por los sistemas DWave y el otro por el grupo Martinis UCSB / Google .

Para ser claros, estoy preguntando si las computadoras analógicas no pueden vencer a las máquinas Turing en eficiencia debido al ruido.

esa es la gran pregunta no? Para tratar de responder eso, considere que hay sistemas analógicos clásicos y los sistemas cuánticos considerados más recientemente . Para los sistemas clásicos, el consenso general es tal como lo describe Nielsen / Chuang, de que existen modelos teóricos que "parecen" más potentes pero que, cuando el ruido se tiene en cuenta correctamente, esta "ventaja" teórica "desaparece". en otras palabras, proponer la existencia de sistemas de computación analógica "fundamentalmente teóricamente más rápidos" que los sistemas electrónicos ya construidos parece violar las leyes de la física / termodinámica.

sin embargo, la pregunta para la computación QM es una pregunta mucho más abierta y depende (como anticipan algo) de la naturaleza del ruido QM y si realmente puede ser experimentalmente / controlado como se ha planteado como hipótesis y está bajo investigación activa.

Hay un análisis más profundo de estos problemas en el documento de Aaronsons NP-complete Problems and Physical Reality . La visión general escéptica se puede encontrar en Perspectivas de Dyakonov para la computación cuántica: extremadamente dudoso .