Esta es una pregunta muy interesante. Hay algunas conexiones profundas entre la física teórica y la informática que pueden ayudarnos a comprender un poco mejor la naturaleza.
Una forma es a través de la teoría de la computabilidad. La invención de la máquina de Turing fue una herramienta para analizar formalmente qué funciones son o no computables. Por ejemplo, decir que los números reales comprenden un conjunto infinito incontable es más o menos equivalente a decir que hay números reales que no son computables (para que un número sea computable requiere un algoritmo para calcular sus dígitos de alguna manera) [1]. También hay otros paralelismos con los problemas clásicos, el más famoso es la equivalencia de los teoremas de incompletitud de Goedel y el problema de la detención. Luego tenemos la tesis de Church-Turing que dice que cualquier cosa que puedas calcular también es una función computable para una máquina de Turing. Tenga en cuenta que la tesis de Church-Turing es en realidad un hecho empírico sobre la computación, no lógico (y no es probable que alguna vez lo sea).
Este podría ser un lugar interesante para comenzar desde una perspectiva física. Una cosa que podría intentar decir es que cualquier sistema físico podría ser calculado por una máquina universal de Turing. La física clásica supone que el universo es continuo, lo que obviamente es incompatible con las máquinas de Turing. La teoría cuántica es discreta, pero no estamos fuera de peligro aquí porque la mecánica cuántica permite violaciones de la tesis de Church-Turing [2]. Es una pregunta abierta si las versiones cuánticas de las máquinas de Turing pueden simular cualquier sistema físico arbitrario [3], aunque se ha realizado algún trabajo en la simulación de teorías de campo cuántico, ver Freedman, 2000 y Jordan, 2011 (esto es realmente muy significativo si asumimos AdS / La correspondencia CFT es verdadera porque simular un QFT es como un cálculo “dual” para sistemas de gravedad cuántica también). En cualquier caso, una declaración como esta nunca se puede probar matemáticamente porque se basa en nuestro conocimiento de la ley física [verdadera], para lo cual no podemos expresar una certeza completa.
- ¿Por qué es P vs NP un problema importante para resolver?
- ¿Cómo fueron procesadas las tiras de cinta por modelos posteriores de la Máquina Turing y por qué usar cinta?
- ¿Qué es un punto flotante?
- ¿Por qué 0.8 * 3 devuelve 2.4000000000000004 en lugar de 2.4?
- ¿Cuáles son las similitudes y diferencias entre recursividad e iteración?
Podemos pasar a la teoría de la complejidad, que amplía la computabilidad para hablar sobre el tiempo de ejecución y los recursos de memoria de clases particulares de algoritmos. Probablemente haya escuchado sobre el problema [matemática] \ text {P} [/ matemática] vs. [matemática] \ text {NP} [/ matemática]. Una pregunta interesante es si la naturaleza puede encontrar el estado fundamental de un sistema físico arbitrario en un tiempo sub-exponencial en promedio (ejemplos de problemas incluyen plegamiento de proteínas y configuraciones de vidrio giratorio de energía mínima) [4]. Dado que la naturaleza es fundamentalmente cuántica, podemos preguntarnos si una computadora cuántica universal (equivalente a una máquina cuántica de Turing) es capaz de darnos un aumento significativo en la eficiencia para estos problemas difíciles [5]. Para introducir un poco de lenguaje teórico de la complejidad, descubriendo la relación entre [matemáticas] \ text {NP} [/ matemáticas] y [matemáticas] \ texto {BQP} [/ matemáticas], la clase de algoritmos cuánticos eficientes (también hay [math] \ text {QMA} [/ math], el análogo cuántico de [math] \ text {NP} [/ math]), sería un buen paso hacia las respuestas a algunas preguntas interesantes, como si el universo está realizando cálculos en el sentido de Turing (el cómputo de funciones no computables se llama hipercomputación) o si alguna vez podríamos verificar experimentalmente el espacio de Hilbert exponencialmente grande en el que viven los estados cuánticos (si la aceleración teórica dada por el algoritmo de Shor se mantiene, entonces tenemos algunas pruebas muy profundas y convincentes que la mecánica cuántica es de hecho cierta). La creencia actual es que [math] \ text {BQP} [/ math] es un superconjunto de [math] \ text {P} [/ math] (ya que tenemos algoritmos cuánticos para hacer cosas mucho más rápido que los puramente clásicos caso, como la factorización de enteros) y tiene una superposición significativa con problemas en [math] \ text {NP} [/ math].
Una cosa que vale la pena considerar es el límite de Holevo, que simplemente expresa el hecho de que su computadora cuántica está haciendo cálculos en un espacio de estado con un tamaño [matemático] 2 ^ n [/ matemático] (donde [matemático] n [/ matemático] es el número de qubits) pero solo permite que se extraigan [math] n [/ math] bits de ese cálculo (una sola medición del estado qubit representa una muestra de la distribución de posibles estados superpuestos). Entonces, por alguna razón, la naturaleza puede usar una cantidad exponencial de datos, pero nosotros no. En cierto sentido, tenemos un número infinito de estados posibles porque los coeficientes para los estados base se encuentran en la recta numérica real.
Cualquier discusión sobre las ideas sobre el funcionamiento del universo es incompleta sin mencionar los agujeros negros. En este caso, son muy relevantes en términos de la paradoja de la información del agujero negro, donde se pensaba que arrojar materia en un agujero negro daría como resultado la pérdida de información. Esta es una clara violación de la mecánica cuántica porque la teoría se basa en el supuesto de que las evoluciones del estado cuántico son unitarias (es decir, reversibles y, por lo tanto, conservadoras de información). Un desarrollo más reciente son los cortafuegos, que intentan resolver un problema más específico con el enredo entre qubits salientes, entrantes y radiantes dentro o alrededor de un agujero negro. Esta publicación de blog es un buen lugar para leer más.
Otro pensamiento divertido proviene de [5], donde las curvas cerradas en forma de tiempo (viaje en el tiempo) pueden explotarse para el cálculo. En pocas palabras, puede realizar un cálculo, obtener la respuesta y luego retroceder en el tiempo para leerlo a su antiguo yo sin realizar el cálculo todavía. Esto daría una complejidad [de tiempo] de [math] \ mathcal {O} (1) [/ math] para cualquier algoritmo.
Al cambiar de marcha, podemos ver las cosas desde una perspectiva de comunicación. Claude Shannon pudo articular un concepto matemático de información que era independiente de la forma en que eligió implementar la comunicación. Esto fue naturalmente bastante útil, pero en última instancia falló en el contexto de la física cuántica [6]. Un resultado interesante que muestra esto con bastante claridad está dado por la codificación súper densa, donde si tiene dos partes comunicantes que comparten un qubit entrelazado [al máximo], entonces el número de bits clásicos de información codificada es el doble del número de qubits enviados a través del canal. Y, por supuesto, existe el problema obvio del enredo cuántico y cómo un qubit enredado sabe cómo se midió su compañero instantáneamente, independientemente de la distancia entre ellos. La relatividad especial requiere que la comunicación no sea más rápida que la velocidad de la luz y, de hecho, esto no se ve violado por el problema de enredos (aún es necesario comunicarse de manera clásica para extraer información útil), pero esto no es satisfactorio cuando se piensa en la naturaleza de enredo en sí mismo.
La mecánica cuántica es relativamente nueva, y la informática teórica es aún más nueva. Ciertamente deberíamos esperar que surjan más ideas sobre la naturaleza fundamental de la realidad de la intersección de estos dos campos.
[1] La forma mucho menos descuidada de decir esto es muy técnica. Algunas lecturas adicionales: Página en mathoverflow.net
[2] Ver: [quant-ph / 9706006] Funciones computables, mediciones cuánticas y dinámica cuántica
[3] Teoría cuántica, el principio de Church-Turing y la computadora cuántica universal.
[4] Es un poco más complicado que esto. Para un hamiltoniano de 2 locales, se sabe que la complejidad es NP completa, pero para un problema de 3 locales es QMA completa (básicamente, “NP cuántica” completa). Consulte el siguiente documento para leer más: [quant-ph / 0406180] La complejidad del problema local hamiltoniano
[5] [quant-ph / 0502072] Problemas NP-completos y realidad física
[6] Esta tesis es un buen recurso: [1303.4690] Recursos teóricos de la información en la teoría cuántica. Véase también el libro de Nielson y Chuang, Computación cuántica e Información cuántica .