¿Es el universo una computadora cuántica? ¿Es la barrera de la velocidad de la luz una restricción computacional?

Actualmente hay un debate en curso en el blog de matemáticas líder Gödel's Lost Letter, entre Gil Kalai y Aram Harrow, con el primero argumentando que construir una computadora cuántica puede no ser posible debido a la propagación del ruido, y el segundo argumentando lo contrario.

Me pregunto si hay algún argumento para demostrar que es posible construir una computadora cuántica, en virtud de mostrar que la computación cuántica es evidente en el mundo físico.

Entonces la pregunta es:

(A) ¿Hay algún ejemplo conocido de interacciones físicas en las que se pueda determinar que las transiciones de estado de nivel macro solo se corresponden con un cálculo cuántico subyacente? Es decir, de manera similar a que el algoritmo de Shor es exponencialmente más rápido que cualquier algoritmo de factorización clásico conocido, ¿existen ejemplos de procesos físicos conocidos, por ejemplo, la estabilización de perturbaciones en un grupo de partículas muy grande, que podría demostrarse, asumiendo que P<>NP, solo es eficiente? resuelto por un cálculo cuántico.

Algunas preguntas adicionales, lo admito altamente especulativas, serían entonces:

(B) ¿Es la velocidad de la barrera de la luz posiblemente un límite computacional natural de nuestro universo particular, de modo que para la clase de complejidad computacional de la mecánica cuántica, trabajando en una estructura de espacio-tiempo similar a una red relacional subyacente, esta es la velocidad máxima que las reglas computacionales ¿Puede mover una representación de partículas/ondas a través de una región de red de la energía/complejidad más baja (es decir, un vacío)?

(C) ¿Es la mecánica cuántica una necesidad real para que el universo siga las leyes físicas clásicas a nivel macro? El argumento informal es que en interacciones de nivel cuántico de partículas de muchos a muchos, solo la capacidad de cada partícula para calcular en paralelo un número infinito o cuasi-infinito de caminos es lo que permite que el universo resuelva una solución en tiempo real en el nivel macro.

Solicitando referencias a investigaciones en este sentido, o cualquier argumento para apoyar o contradecir estas especulaciones.

Este libro parece relevante: Programando el universo: un científico informático cuántico se enfrenta al cosmos. Seth Lloyd. Asumiría que mis especulaciones están incluidas allí, pero aún no las he leído.
El libro de Lloyd tiene mucho material interesante, particularmente relacionado con la entropía de Shannon desde un punto de vista computacional. Sin embargo, no parece que cubra mis especulaciones.
Publicado de forma cruzada en TP.SE: theoryphysics.stackexchange.com/q/1019/189
No sé qué significa tu pregunta (A). Parece estar asumiendo que las computadoras cuánticas pueden hacer cosas que las computadoras clásicas no pueden. La computación clásica puede hacer todo lo que hace la computación cuántica, aunque posiblemente tarde exponencialmente más.
Bueno, ciertamente soy consciente de que las computadoras cuánticas no son un contraejemplo de la conjetura de Church-turing, y creo que soy razonablemente consciente de la comprensión actual de la posición de BQP en la jerarquía de las clases de complejidad. Simplemente me preguntaba que, de manera similar a que su algoritmo de factorización es exponencialmente más rápido que cualquier algoritmo clásico conocido, hay ejemplos de reacciones físicas, por ejemplo, estabilización de perturbaciones en un grupo de partículas muy grande, que podría demostrarse que solo se resuelve de manera eficiente mediante un computación cuántica.
Y para aclarar aún más, si la respuesta a la pregunta (A) es "no", es decir, el universo en ningún caso funciona como una computadora cuántica, a pesar de tener todos los componentes básicos disponibles, entonces tendería a creer que nuestros intentos de construir un computadora cuántica probablemente sería inútil. Para ser claro, creo que la respuesta es sí. –
Es posible que desee leer el blog de Scott Aaronson y su tesis doctoral.
Sigo su blog. Verá su tesis doctoral. Gracias.
La tesis de Scott Aaranson parece tremendamente interesante, y desde la introducción parece muy relevante para mis preguntas. Habrá que dedicar un tiempo a leer... Tesis: Límites de la computación eficiente en el mundo físico, 2004, Scott Joel Aaronson, scottaaronson.com/thesis.pdf
Ahora que lo has explicado, veo que es una pregunta razonable.
Gracias, ahora es un poco más claro. Sin embargo, creo que la conexión de (A) con (B) y (C) es demasiado débil. Para mucha gente, sonaría como si estuvieras haciendo tres preguntas diferentes. Tratamos de tener una pregunta por publicación en este sitio, entonces, ¿por qué no las suelta?
Además, no estoy seguro de que exista una relación entre la velocidad de la luz y la complejidad en el sentido que preguntas. La teoría de la complejidad está escrita en términos de la cantidad de operaciones fundamentales que necesita para realizar alguna operación. Las operaciones fundamentales tienen todas un pequeño coste (unitario). Parece que en su argumento, la velocidad de la luz podría estar relacionada con las operaciones fundamentales en sí, pero no con la cantidad de veces que puede usarlas.

Respuestas (4)

La respuesta a esta pregunta es un sorprendente no, y esto no se debe a que no tengamos suficientes sistemas cuánticos. Tenemos mucho. El problema es que si un sistema natural con una gran cantidad de partículas está implementando un cálculo que requiere recursos exponenciales, no podemos hacer el cálculo para verificar si la mecánica cuántica es precisa. La mecánica cuántica podría estar fallando todo el tiempo en estados nucleares altamente excitados y altamente entrelazados, pero no lo sabríamos, porque no podemos calcular los niveles de energía exactos, solo podemos confiar en la experimentación.

Primero, para A, todo sistema cuántico con una gran cantidad de partículas e interacciones fuertes está implementando un cálculo cuántico no trivial, pero no podemos verificar si lo está haciendo correctamente. Por ejemplo, si excita un núcleo de uranio a un estado muy excitado, de modo que pueda emitir rayos X, neutrones y protones, y observe el espectro radiado de la materia, las amplitudes de emisión son un producto muy complicado de un 250 sistema de partículas con enredos imposibles de calcular. Estos cálculos simplemente no pueden ser realizados por ninguna computadora clásica, por lo que simplemente no sabríamos si la mecánica cuántica está fallando. Pero sí, un núcleo de uranio en un estado excitado de 700 MeV está realizando un cálculo cuántico imposiblemente complejo que no podemos calcular ni siquiera con una computadora del tamaño del universo.

Para B --- su pregunta no tiene sentido, pero la velocidad de la luz limita la velocidad de transferencia de información en una computadora. Esto no es una gran limitación de principio, porque simplemente dice que un paso de cálculo que mueve datos del punto A al punto B tomará un tiempo proporcional a la distancia entre A y B. Esto no tiene relación con la complejidad computacional, porque puede hacer el movimiento en tiempo polinomial en el tamaño de su memoria, incluso si está diseñado de manera ineficiente en línea recta. Esta es una pista falsa. Las palabras "esta es la velocidad máxima a la que una partícula sin masa puede calcular un camino resuelto cuando viaja a través de un campo cuántico vacío" no tienen sentido.

Para C: la respuesta aquí es no --- solo puede tener mecánica clásica, que no requiere sumas infinitas para resolver la respuesta. La idea de que se requiere la mecánica cuántica para reproducir respuestas definitivas clásicas es extraña, porque en realidad es misterioso cómo sucede esto. Para producir resultados definitivos a partir de la confusión de la superposición cuántica, debe suponer que estamos dividiendo entidades en una imagen de muchos mundos, o bien poner leyes de creación definitiva a mano que hacen lo mismo de manera efectiva. Si la naturaleza es fundamentalmente clásica, esto no va a importar.

Comentarios sobre la discusión vinculada

El argumento que hace Gil Kalai es interesante, pero está mal expresado. Christopher Moore lo expresó de manera convincente en el primero de los comentarios aquí: http://rjlipton.wordpress.com/2012/01/30/perpetual-motion-of-the-21st-century/ , y no quiero repetir demasiado. Cuando está proponiendo que la computación cuántica fallará, está proponiendo que la mecánica cuántica es incorrecta y que la falla ocurre en sistemas físicos grandes altamente entrelazados.

El argumento en contra de la mecánica cuántica por la imposibilidad de que un sistema físico realice un cálculo exponencial es completamente diferente de otros argumentos en contra de la mecánica cuántica. El principio filosófico es que la naturaleza no puede ser mucho más rica computacionalmente que nosotros, porque esto introduce un elemento místico de incomputabilidad en principio en los grandes sistemas cuánticos de la naturaleza. Este principio es nuevo en lo que respecta a la literatura, pero no se debe a Gil Kalai. Lo escuché por primera vez del estudiante de informática Abram Connely hace una década, este era su conflicto personal con la mecánica cuántica. Encontré un punto persuasivo e interesante, y traté de darle una exposición en mi respuesta aquí: ¿Consecuencias del nuevo teorema en QM?. La formulación precisa que da Kalai es interesante, pero formulada de una manera subóptima.

Para creer que la computación cuántica es imposible, se necesita absolutamente una nueva ley de la física que reemplace a la mecánica cuántica, o al menos un principio para determinar cómo falla la mecánica cuántica. La afirmación de que el fracaso es fundamental, porque el universo no puede ser tan complicado, requiere que al menos intentes especificar cómo se puede simplificar el universo.

Es incorrecto argumentar que el simple ruido de implementación hace que la computación cuántica sea inviable, sin proponer que existe una ley de la naturaleza que prohíbe los enredos de la computación cuántica. La razón es que puede eliminar el ruido simplemente enfriando el sistema y haciendo que las piezas sean precisas. En principio, no existe un límite para el tamaño de la computación cuántica, incluso sin corrección de errores. La corrección de errores cuánticos es fundamental para la implementación en la práctica, pero en principio, puede imaginar una computadora perfecta y acercarse cada vez más a un sistema cada vez más frío, sin límite excepto cuánto está dispuesto a gastar.

Un fallo de la mecánica cuántica que solo afecta a los entrelazamientos mutuos de un gran número de partículas cuánticas puede haber escapado fácilmente a la detección, pero cuando se proponen modificaciones a la mecánica cuántica, se debe comprobar que no conduzcan a cosas que no habrían escapado a la detección. Cosas como fallas en la conservación de la energía, fallas en la coherencia de pocas partículas, pérdida irreversible de información en sistemas de pocos cuerpos, fricción en el movimiento atómico y todo tipo de cosas más.

Para verificar estas cosas, es insuficiente formular el principio de falla computacional sobre un dispositivo de computación abstracto. Se debe mostrar cómo este principio modifica la dinámica de la función de onda a escala atómica real. La idea de que esto es una no linealidad en la ecuación de Schrödinger es simplemente mala, por lo que si está proponiendo tal modificación, debería ser porque el SE es una descripción emergente de un sistema fundamentalmente clásico.

Estas ideas se deben a t'Hooft, quien también se muestra escéptico con respecto a la computación cuántica, principalmente por la misma razón por la que Einstein se mostró escéptico con respecto a la mecánica cuántica. t'Hooft ha dado varios intentos de un modelo sobre cómo reemplazar la mecánica cuántica con un sistema que no será capaz de computación exponencial, y si uno está proponiendo decoherencia fundamental (que es lo que está haciendo Gil Kalai), uno debería hacerlo en el contexto de al menos una especulación sobre el sustrato subyacente.

Gracias, Ron. +1. De acuerdo en que B no tiene sentido como se indica. Volveré a escribir en breve para transmitir con mayor precisión mi significado previsto. Sin embargo, creo que esto no cambiará tu respuesta. Con respecto a A, supongo que su respuesta significa: Sí, el universo implementa cálculos cuánticos solo a nivel cuántico, pero a nivel macro no podemos verificar esto (es decir, es efectivamente indecidible en nuestro mundo) y también ( B) no tiene un impacto real en la evolución del mundo físico a nivel macro.
@GrigoriStrassmann: Sí --- y es por eso que personalmente desconfío de la computación cuántica --- por definición, no hemos podido verificar cuándo un sistema físico está haciendo más computación de la que cabe en una computadora clásica del tamaño de la universo. El algoritmo de Shor es una brillante excepción, porque podemos comprobar si la respuesta es un factor del gran número de manera trivial. Entonces, necesitamos ejecutar el algoritmo de Shor en un número de 10,000 dígitos al menos una vez antes de que podamos estar seguros de que QM es la teoría final. Tengo un 60% de confianza en que esto funcionará, pero tal vez t'Hooft, Connely y Kalai tengan razón.
Editado (B) para reflejar con mayor precisión la intención original de la pregunta.
Estoy de acuerdo en que el algoritmo de Shor es brillante, pero dado que se cree que la factorización pertenece a la clase de problemas NP intermedios, el comportamiento es el esperado para todos los problemas NP. Las soluciones son difíciles de calcular, pero fáciles de verificar. Entonces, suponiendo una prueba de P<>NP, ¿una computadora cuántica en funcionamiento que factorice números muy grandes en tiempo polinomial no sería una respuesta definitiva de sí a la pregunta A?
@GrigoriStrassmann: Sí, más o menos, hasta malas palabras. Para que sea riguroso, técnicamente tienes que probar que la factorización no se puede resolver polinómicamente (no es NP completo, por lo que no es suficiente para probar P<NP). Para fines físicos, es obvio que, incluso si hay un algoritmo de factorización P complicado, la única forma en que la naturaleza podría factorizar utilizando el algoritmo de Shor (que no es más que una búsqueda en lo que respecta a la factorización) es intentar exponencialmente muchas multiplicaciones a la vez, por lo que no necesitaría una prueba de nada --- QM simplemente se mostraría como exponencial.
Su nueva B es clara, pero creo que la forma clara de la pregunta también aclara la respuesta.
En realidad, ¿qué significa decir que QM es preciso? ¿Quiere decir en comparación con una solución continua exacta? Bueno, si no hay estructuras continuas en el mundo físico, entonces los resultados de un cálculo de QM físico solo serán tan precisos como lo permitan los estados finitos subyacentes. Es una pregunta interesante si hay configuraciones experimentales, por ejemplo, con sistemas cuánticos dinámicos iterados, que podrían demostrar tales desviaciones de la precisión perfecta.
"Pero sí, un núcleo de uranio en un estado excitado de 700 MeV está realizando un cálculo cuántico imposiblemente complejo que no podemos calcular ni siquiera con una computadora del tamaño del universo". – por lo que sabemos, el universo podría ser infinito. Eso debería ser espacio más que suficiente para calcular un átomo de uranio, ¿no? (Sin embargo, el cálculo puede llevar mucho tiempo).
@celtschk: aquí universe==el universo observable. El número de bits se asume por el número de áreas de Planck en el horizonte cosmológico. El átomo U con electrones tiene 350 partículas, que, incluso con una descripción cuántica tosca, supera el tamaño que se puede simular con una computadora clásica de ese tamaño. Pero, por supuesto, para estados fundamentales o estados de baja excitación, existen mejores métodos como DFT.

Los experimentos de John Bush sobre la hidrodinámica de ondas piloto han demostrado evidentemente que la replicación a macroescala de los efectos cuánticos es completamente posible, la interpretación de Copenhague puede tener problemas y la respuesta a su pregunta puede terminar siendo "sí", después de todo. para sorpresa de la mayoría de nosotros.

Dicho esto, hasta que se realicen más experimentos, dudo que la opinión expresada en esta respuesta sea muy popular.

Sugiero agregar algo como esto a su respuesta, para todos los que no saben lo que hizo John Bush.

Solo quería comentar, pero se estaba haciendo demasiado largo. Quería decir algo sobre (A).

Los spin-flips están obviamente en una correspondencia natural con los cálculos cuánticos y ocurren todo el tiempo. Sin embargo, no me atrevería a argumentar que están "solo en correspondencia con los cálculos cuánticos", ya que podrías hacer que "correspondan" a absolutamente cualquier cosa que quieras. De hecho, también se puede decir que corresponden a los clásicos lanzamientos de monedas. Un ejemplo más cuántico (quizás no muy significativo): " podría " decir siempre que el universo es una computadora cuántica analógica que se está simulando a sí misma.

Tal vez más relevante, ¿por qué cualquier argumento de esta naturaleza sería un indicio de que se pueden construir computadoras cuánticas? Suponga que el argumento que propone es válido en un sentido fuerte y, además, que las computadoras cuánticas no se pueden construir. Ya que se pueden construir computadoras clásicas . Entonces, podría argumentar perfectamente que "deberíamos" considerar el universo como una computadora clásica, usando un ϵ -lejos de la línea de razonamiento. Incluso si no crees en la computación cuántica, esta no parece una imagen útil de la realidad para un físico moderno. ¿Dónde pones todos los efectos cuánticos que se han demostrado experimentalmente?

Lo que sigue es excesivamente especulativo y algunos de los argumentos son antropomórficos, así que lea según su propio nivel de tolerancia. Se relaciona esencialmente con la interpretación del mundo físico en términos de la teoría de la información y, posiblemente, la teoría de la medición cuántica, en lugar de hacerlo directamente desde la mecánica cuántica.



Si consideramos el espacio o el espacio-tiempo como una construcción estadística a partir de información finita adquirida a lo largo del tiempo, y existe un límite de tiempo discreto inferior como el tiempo de Planck, de hecho debe haber un límite de velocidad tal (quizás c o algún múltiplo de c) que surge naturalmente, ya que el observador no puede percibir los objetos que viajan más rápido que la velocidad finita a la que puede calcular las relaciones métricas entre los puntos del espacio-tiempo. Viajar más rápido que este límite sería como tratar de tener tu pastel y comértelo también... no serías capaz de observar un objeto más rápido que la luz porque no tendrías tiempo para percibir el fondo espacial a partir de la información recibida. Ahora bien, podría haber lagunas muy interesantes en esta idea que podrían permitir FTL en ciertas circunstancias, particularmente si el espacio se puede crear a un ritmo más rápido que la velocidad de la luz, como quizás ocurrió en el universo primitivo. También se podría argumentar que FTL es posible pero no directamente observable en este escenario. Si c es el límite de velocidad real, un efecto experimental que se podría esperar es la mezcla de las coordenadas x, y y z a velocidades cercanas a c, de modo que también debería haber una contracción ay/z, así como una contracción x de Lorentz.


Quizás más interesante que establecer un simple límite de velocidad, sin embargo, es que los tipos de tales espacios de fondo determinados estadísticamente que podrían ser medidos y determinados de manera realista por un observador podrían tener conexiones más profundas con la gravedad en escalas abiertas grandes y grupos O(N) en escalas cerradas pequeñas. . El espacio euclidiano que generalmente observamos en escalas intermedias entre estos dos extremos tiene propiedades simétricas muy simples y únicas (rotación, traslación, invariancia de inversión) que uno podría esperar que emergieran naturalmente de cualquier construcción estadística de todos los espacios posibles tanto como Feynman muchos caminos se unen hacia el principio de mínima acción. A escalas muy grandes, sin embargo, definitivamente existen restricciones dimensionales (y probablemente topológicas) para la percepción de un espacio estadístico de este tipo que requeriría la introducción de asimetrías (y, por lo tanto, curvaturas). Por ejemplo, podemos aproximar a un observador que puede recopilar solo cantidades finitas de información sobre su espacio a lo largo del tiempo como un caminante aleatorio que puede observar un punto espacial en una red espacial por unidad de tiempo. Es un hecho bien conocido que en una red infinita más alta que dos dimensiones, el observador solo regresaría/observaría cualquier punto o transición un número finito de veces a pesar de un tiempo infinito para la observación y, por lo tanto, sería incapaz de determinar estadísticamente la métrica. de tal espacio! Sin embargo, para espacios generalmente finitos (y, por lo tanto, cerrados y pequeños), esto no es un problema,


Quizás también sea un antropomorfismo revelador que percibamos espacios 2D abiertos de dos maneras diferentes, como una pantalla 2D como proyección frente a nosotros, o como una proyección lineal similar a un horizonte multiplicada por una distancia radial sobre la superficie de un cuerpo gravitatorio. El segundo es mucho menos directo y la linealidad o falta de ella aparece limitada y controlada por la gravedad alcanzando un absoluto en la superficie de un agujero negro donde el observador y su realidad quedan completamente aplanados. Si hubiera una conexión continua/suave entre los dos, esto podría formar una nueva dualidad.

Por favor, trate de no hacer tantas ediciones pequeñas. Cada vez que lo edita, la pregunta aparece en la parte superior de la página principal y desvía la atención de otras preguntas que lo merecen. Guarde la edición para cuando tenga algo más grande que arreglar.