🙍🏿 ♌️ 🧑 Una prueba significativa del teorema de la informática captura la física con las matemáticas. 🎷 🏠 👷

Los especialistas en informática han identificado nuevas fronteras en el conocimiento verificado a través de la computación. Y al mismo tiempo resolvieron problemas significativos de la mecánica cuántica y las matemáticas puras.

En 1935, Albert Einstein, junto con Boris Podolsky y Nathan Rosen, intentaron aprovechar la oportunidad que se abrió con las nuevas leyes de la física cuántica: el "enredo" de dos partículas, que en este caso pueden separarse por una gran distancia.

Al año siguiente, Alan Turing formuló la primera teoría generalizada de la computación y demostró la existencia de problemas, en principio no sujetos a las computadoras.

Estas dos ideas han revolucionado sus respectivos campos. Además, parecía que no tenían nada que ver el uno con el otro. Sin embargo, ahora una prueba significativa los unió, resolviendo simultáneamente una gran cantidad de problemas de informática, física y matemáticas.

La nueva evidencia sugiere que las computadoras cuánticas que realizan cálculos usando bits cuánticos, o "qubits", en lugar de ceros y unos clásicos, pueden usarse teóricamente para confirmar soluciones a una amplia gama de problemas. La conexión entre el entrelazamiento cuántico y la tecnología informática fue un shock para muchos investigadores.

"Fue completamente inesperado", dijo Miguel Navazquezestudiando física cuántica en el Instituto de Óptica Cuántica e Información Cuántica en Viena.

Los coautores de la prueba decidieron determinar los límites de las posibilidades de confirmar soluciones a problemas computacionales. Su enfoque utiliza la confusión. Habiendo encontrado estos límites, los investigadores al mismo tiempo, casi como un efecto secundario, respondieron otras dos preguntas: el problema de Zirelson en física con respecto al modelado matemático de enredos, y el problema relacionado de las matemáticas puras, la hipótesis de anidación de Conn .

Los resultados finalmente cayeron como fichas de dominó.

“Todas las ideas originales nacieron aproximadamente al mismo tiempo. Es conveniente que todos se hayan unido de una manera tan increíble ", dijo Henry Ewande la Universidad de Toronto, uno de los autores de la evidencia. Otros autores: Zhengfeng Ji de la Universidad Tecnológica de Sydney, Anand Natarajan y Thomas Widick del Instituto de Tecnología de California, y John Wright de la Universidad de Texas en Austin. Los cinco son informáticos.

Tareas insolubles

Turing identificó la plataforma principal para el estudio de la informática incluso antes del advenimiento de las propias computadoras. Y literalmente enseguida demostró que las computadoras, en principio, no podían resolver ciertos problemas, y que esto podía probarse. La cuestión es si el programa que resuelve un problema en particular termina su trabajo.

Típicamente, los programas de computadora reciben datos de entrada y después de un tiempo producen datos de salida. Pero a veces se atascan en ciclos interminables, lo que hace que sus engranajes giren para siempre. Cuando esto te sucede, solo te queda una opción.

“Tengo que clavar manualmente el programa. Solo detenla, ”dijo Ewan.

Turing demostró que no existe un algoritmo general que pueda determinar si un programa completará la ejecución o funcionará para siempre. Para averiguarlo, debe ejecutar el programa en sí.

Ewan, Vidik, Ji, Natarajan y Wright

“ Esperaste un millón de años y el programa no terminó de funcionar. ¿Necesitas esperar otro millón de años? No hay respuesta a esta pregunta ", dijo William Slofstra , matemático de la Universidad de Waterloo.

Técnicamente hablando, la tarea de detener un programa no tiene solución, incluso la computadora más poderosa que puedas imaginar no puede resolverlo.

Después de Turing, los informáticos comenzaron a clasificar otras tareas de acuerdo con su complejidad. Las tareas más complejas requieren más recursos informáticos para resolver: más tiempo para trabajar, más memoria. Así que estudie la complejidad computacional de las tareas.

Como resultado, puede hacer dos preguntas sobre cada tarea: "¿Qué tan difícil es resolverlo?" y "¿Qué tan difícil es verificar la respuesta correcta?"

Interrogatorio para confirmación

En el caso de tareas simples, la respuesta se puede verificar de forma independiente. Pero a medida que se vuelven más complicados, incluso verificar la respuesta puede convertirse en una tarea imposible. Sin embargo, en 1985, los informáticos se dieron cuenta de que era posible verificar la exactitud de la respuesta, incluso si era imposible confirmarla usted mismo.

Este método sigue la lógica de una investigación policial. Si el sospechoso cuenta una historia confusa, es posible que no pueda ver todos los detalles. Pero al hacer las preguntas correctas, puede atrapar al sospechoso en una mentira, o puede estar seguro de la verdad de la historia.

En términos de informática, el interrogatorio contiene una computadora poderosa que ofrece una solución al problema, conocida como "probador", y una computadora menos poderosa que hace preguntas al probador para determinar la exactitud de la respuesta, conocida como "prueba".

Un ejemplo simple: imagine que no distingue entre colores, y la otra persona, el probador, afirma que dos de algunas bolas tienen un color diferente. No puede verificar esta declaración por su cuenta, pero a través de un ingenioso interrogatorio, aún puede verificar que es cierta.

Ponga las bolas detrás y mezcle. Pídale al probador que le diga cuál tiene qué color. Si realmente son de diferentes colores, el probador debe responder constantemente correctamente la pregunta. Si son del mismo color, es decir, se ven iguales, el probador en la mitad de los casos expresará la suposición equivocada.

"Si veo que has logrado mucho más éxito que en la mitad de los casos, entonces estoy casi seguro de que no son del mismo color", dijo Vidik.

Al hacer preguntas de prueba, puede confirmar la exactitud de las soluciones para una gama más amplia de tareas de las que podría resolver usted mismo.

En 1988, los informáticos pensaron en lo que sucedería si dos probadores sugirieran soluciones al mismo problema. Después de todo, si tiene la oportunidad de interrogar a dos sospechosos, le será aún más fácil resolver el crimen o confirmar la exactitud de la decisión: se pueden comparar entre sí.

“Para quienes lo controlan, les da más espacio para la presión. Usted interroga, hace preguntas relacionadas con el caso, verifica las respuestas ", dijo Vidik. Si los sospechosos dicen la verdad, sus respuestas deberían coincidir la mayor parte del tiempo. Si mienten, habrá más contradicciones.

Del mismo modo, los investigadores demostraron que al interrogar por separado a los dos probadores con respecto a sus respuestas, uno puede confirmar rápidamente la corrección de la solución para una clase aún más amplia de problemas, en comparación con el que puede abordar con un solo probador.

La complejidad computacional puede parecer una idea puramente teórica, pero, sin embargo, está estrechamente relacionada con el mundo real. Los recursos que las computadoras necesitan para resolver problemas y confirmar decisiones (tiempo y memoria) son fundamentalmente físicos. Por lo tanto, los nuevos descubrimientos en física pueden cambiar la complejidad computacional.

"Si elige un conjunto diferente de leyes físicas, por ejemplo, el mundo cuántico en lugar del clásico, entonces se puede deducir de él otra teoría de la complejidad", dijo Natarajan.

La nueva evidencia es el resultado final de la confrontación entre un informático del siglo XXI y una de las ideas más extrañas de la física del siglo XX: el enredo.

Hipótesis de anidación de Conn

Cuando dos partículas se enredan, no se afectan entre sí, no tienen una relación causal. Einstein et al. Revelaron esta idea en un artículo de 1935. Después de eso, los físicos y los matemáticos intentaron encontrar una forma matemática de describir lo que realmente significa confusión.

Sin embargo, hubo cierta confusión. Los científicos idearon dos modelos matemáticos diferentes de enredos, y el hecho de que sean equivalentes entre sí no era del todo obvio.

Indirectamente, esta disonancia potencial influyó en la aparición de un problema importante del campo de las matemáticas puras, la hipótesis de anidación de Conn. Y al final, también sirvió como un cisma, que cinco informáticos aprovecharon en su nueva evidencia.

La primera forma de modelar el enredo es imaginar partículas aisladas espacialmente. Uno de ellos, por ejemplo, está en la Tierra, y el otro está en Marte; la distancia entre ellos excluye una relación causal. Esto se llama un modelo de producto tensorial.

Pero en algunas situaciones, no está del todo claro si dos objetos están realmente causalmente aislados entre sí. Por lo tanto, los matemáticos han encontrado una forma más general de describir la independencia causal.

Cuando la secuencia de operaciones en los objetos no importa, la operación se considera conmutada: 3 x 2 dará lo mismo que 2 x 3. En el segundo modelo, las partículas se enredan cuando sus propiedades se correlacionan, pero la secuencia de mediciones no importa. Mida la partícula A para predecir el momento de la partícula B, o viceversa. En cualquier caso, la respuesta será la misma. Esto se llama un modelo de entrelazado de operador conmutado.

Ambas descripciones de enredos utilizan matrices de números organizados en columnas y filas: matrices. El modelo de producto tensorial utiliza matrices con un número finito de columnas y filas. El modelo de enredo del operador de conmutación utiliza un objeto más general que funciona como una matriz pero tiene un número infinito de filas y columnas.

Con el tiempo, los matemáticos comenzaron a explorar estas matrices por su cuenta, por separado de su conexión con la física. En el marco de este trabajo, el matemático Alain Conn en 1976 planteó la hipótesis de que muchas matrices de dimensión infinita pueden ser aproximadas por matrices con dimensión finita. Esta fue una de las conclusiones de la hipótesis de anidación de Conn.

En la próxima década, el físico soviético [en el físico original, pero en Wikipedia aparece como matemático / aprox. transl.] Boris Tsirelson propuso su propia versión de este problema, que nuevamente se asoció con la física. Zirelson sugirió que el producto tensor y los modelos de operador conmutativo que describen enredos son aproximadamente equivalentes. Esto tiene sentido, ya que en teoría estas son dos formas diferentes de describir el mismo fenómeno físico. Los trabajos posteriores mostraron que, debido a la conexión de las matrices y los modelos físicos que los utilizan, la hipótesis de Conn sobre la anidación y el problema de Zirelson se suceden: resuelve uno y resuelve el otro.

Sin embargo, la solución a ambos problemas como resultado apareció en una dirección completamente diferente.

Física y juegos

En la década de 1960, al físico John Bell se le ocurrió una prueba para determinar si el enredo es un fenómeno físico real o simplemente una idea teórica. Algo similar a un juego participó en la prueba, cuyo resultado informó si algo más que la física ordinaria, no cuántica, jugó un papel en el experimento.

Más tarde, los informáticos se darán cuenta de que esta prueba de enredos también se puede utilizar como una herramienta para validar soluciones a problemas muy complejos.

Pero primero, para comprender cómo funcionan estos juegos, imagine dos jugadores, Alice y Bob, y una caja de 3x3. El juez le da a Alice una línea y le sugiere que ponga 0 o 1 líneas en cada una de las celdas para que la suma de los números sea impar. A Bob se le asigna una columna y necesita completar todas sus celdas para que la suma de los números sea par. Ganan si ponen el mismo número en la misma celda, donde se cruzan la fila y la columna seleccionadas. Pero al mismo tiempo no pueden comunicarse.

En condiciones normales, lo mejor que pueden hacer los jugadores es ganar en el 89% de los casos. Pero en el mundo cuántico, pueden mejorar este resultado.

Supongamos que Alice y Bob comparten un par de partículas enredadas. Cada uno de ellos toma medidas de su partícula y utiliza los resultados para determinar si escribir 0 o 1 en cada celda. Dado que las partículas están enredadas, los resultados de sus mediciones se correlacionarán entre sí, lo que significa que sus respuestas también se correlacionarán, lo que significa , podrán ganar en el 100% de los casos.

Entonces, si ves que dos jugadores ganan el juego inesperadamente a menudo, puedes concluir que usan algo fuera de la física clásica. Ahora los experimentos de Bell se llaman juegos "no locales", en referencia a la separación de jugadores. Y los físicos en realidad hacen tales experimentos en laboratorios.

"La gente ha hecho tales experimentos durante años, y de ellos se deduce que este efecto aterrador realmente existe", dijo Ewan.

Al analizar cualquier juego, es posible que necesite información sobre con qué frecuencia los jugadores ganan un juego no local si intentan jugar de la mejor manera posible. Por ejemplo, si tomas Solitario Solitario, entonces puedes calcular la probabilidad con la que el jugador que juega perfectamente podrá ganar.

Pero en 2016, William Slofstra demostró que no existe un algoritmo general para calcular la probabilidad máxima exacta de ganar en juegos no locales. Los investigadores hicieron la pregunta: ¿es posible predecir al menos aproximadamente el porcentaje máximo de ganancias?

Los informáticos buscaron una respuesta utilizando dos modelos que describan complejidades. El algoritmo que utiliza el modelo de producto tensor determina el límite inferior, o el valor mínimo de la probabilidad máxima aproximada de ganar para todos los juegos no locales. Otro algoritmo que usó el modelo de enredo con un operador de acceso telefónico determinó su límite superior.

Cuanto más funcionen estos algoritmos, más preciso será el resultado que produzcan. Si la predicción de Zirelson es cierta, y estos dos modelos son realmente equivalentes, entonces los límites inferior y superior deberían acercarse gradualmente, convergiendo a un solo valor de la probabilidad máxima aproximada de ganar.

Pero si la predicción de Cirelson es incorrecta, y los dos modelos no son equivalentes, "los límites inferior y superior permanecerán por siempre separados", dijo Ewan. Será imposible calcular incluso el valor aproximado de la probabilidad máxima de ganar para juegos no locales.

En el nuevo trabajo, cinco investigadores usaron este tema, si los límites inferior y superior convergen, y si la hipótesis de Zirelson es cierta, para resolver una pregunta separada sobre la posibilidad de confirmar la corrección de la solución de un problema computacional.

Ayuda intrincada

A principios de la década de 2000, los científicos informáticos pensaron: ¿cómo cambiaría el espectro de tareas, cuyas soluciones pueden confirmarse entrevistando a dos probadores con partículas intrincadas?

La mayoría decidió que el enredo jugaría en contra de la confirmación. De hecho, será más fácil para dos sospechosos construir una mentira consistente si tienen una manera de coordinar las respuestas.

Pero en los últimos años, los informáticos se han dado cuenta de que en realidad es todo lo contrario: al interrogar a los probadores, dividir pares de partículas enredadas, uno puede confirmar soluciones a una gama mucho más amplia de problemas que sin enredos.

"La confusión es una forma de obtener una correlación que parece ayudarlos a mentir y engañar", dijo Vidik. "Pero en realidad puedes envolverlo a tu favor".

Para comprender cómo es esto posible, primero debe evaluar el rango casi sobrenatural de tareas cuyas soluciones puede verificar con este procedimiento interactivo.

Imagine un gráfico: un conjunto de puntos (vértices) conectados por líneas (bordes). Es posible que desee averiguar si es posible colorear los vértices con tres colores para que no haya pares de vértices del mismo color, unidos por un borde común.

Si le das a un par de personas que prueban un gráfico muy grande y dicen que se puede colorear en tres colores como se describe, pensarás: ¿hay alguna manera de verificar esta respuesta?

Los gráficos muy grandes no se pueden verificar directamente. En cambio, puede pedirle a cada probador que informe el color de dos vértices conectados por un borde. Si informan diferentes colores, y cada vez dan diferentes colores cuando sondean sobre otros vértices, su confianza en que la coloración en tres colores funcionará crecerá.

Pero esta estrategia de sondeo también deja de funcionar cuando los gráficos se vuelven realmente grandes, cuando el número de bordes y vértices comienza a exceder el número de átomos en el Universo. Para el verificador, incluso una tarea como plantear una pregunta específica (“dime el color del vértice XYZ”) se vuelve insoportable: la cantidad de datos necesarios para nombrar un vértice particular excede la memoria de trabajo disponible.

Sin embargo, la confusión permite a los probadores hacer preguntas ellos mismos.

“El revisor no necesita resolver las preguntas. El inspector hace que los propios probadores calculen las preguntas por él ”, dijo Wright.

El inspector necesita que los probadores le digan los colores de los vértices conectados. Si los vértices no están conectados, las respuestas a la pregunta no dirán nada sobre la posibilidad de colorear el gráfico en tres colores. En otras palabras, el examinador quiere que el probador haga preguntas relacionadas: un probador hace la pregunta sobre el vértice ABC, y el otro sobre el vértice XYZ. Y me gustaría que estos dos picos estén conectados, aunque ninguno de los probadores sabe de qué pico está hablando el otro. Al igual que Alice y Bob esperan poner el mismo número en el mismo cuadrado, aunque ninguno de ellos sabe con qué fila y columna trabaja el otro.

Si cada uno de los dos probadores emitiera una pregunta por sí solo, no se los podría obligar a seleccionar picos conectados o correlacionados, de modo que el examinador pudiera confirmar sus respuestas. Sin embargo, el enredo solo le permite construir una correlación.

“Vamos a usar la confusión para volcar todo el trabajo en los probadores. Les haremos elegir sus propias preguntas ”, dijo Vidik.

Al final del procedimiento, cada uno de los probadores informa un color. El revisor los verifica para encontrar una coincidencia. Si un gráfico puede ser coloreado en tres colores, los probadores nunca deberían producir el mismo color.

"Si el recuento se puede pintar en tres colores, los probadores pueden convencerlo de esto", dijo Ewan.

Resulta que este procedimiento de confirmación es otro ejemplo de un juego no local. Los probadores "ganan" al convencerlo de la exactitud de su decisión.

En 2012, Vidik y Tsiyoshi Ito demostraron que es posible, al jugar varios juegos no locales con evidencia confusa, confirmar las respuestas al menos al mismo número de tareas que cuando se interroga a dos computadoras clásicas. Es decir, el uso de probadores confusos no perjudica la confirmación de sus ottetes. Y el año pasado, Natarajan y Wright demostraron que interactuar con probadores intrincados en realidad extiende la clase de tareas validadas.

Sin embargo, hasta este punto, los informáticos no han adivinado el tamaño de la gama completa de tareas, cuyas soluciones pueden confirmarse de manera similar.

Cascada de consecuencias

En el nuevo trabajo, cinco informáticos prueban que el interrogatorio de probadores enrevesados puede confirmar soluciones a problemas no resueltos, incluido el problema de detención.

"Las capacidades de validación de este modelo son increíbles", dijo Ewan.

Sin embargo, el problema de detención no se puede resolver. Y este hecho se convirtió en clave para completar la prueba.

Supongamos que le das un programa a un par de probadores confusos. Les pides que digan si su ejecución se detendrá. Estás listo para probar su respuesta a través de una variedad de juegos no locales: los probadores dan preguntas y ganan dependiendo de la consistencia de sus respuestas.

Si el programa realmente se detiene, los probadores deberían poder ganar este juego en el 100% de los casos, como en el caso de un gráfico que se puede colorear con tres colores, cuando los probadores enrevesados no tienen que dar el mismo color para dos vértices conectados. Si el programa no se detiene, los probadores deberían ganar solo por casualidad, es decir, en el 50% de los casos.

Esto significa que si alguien le pide que determine la probabilidad máxima aproximada de ganar para un juego no local en particular, primero deberá resolver el problema de detención. Pero es imposible de resolver. Lo que significa que la tarea de calcular la probabilidad máxima aproximada de ganar no tiene solución, como lo es el problema de detenerse.

Y esto, a su vez, significa que la respuesta al problema de Zirelson es negativa: los dos modelos de enredo no son equivalentes. Si lo fueran, sería posible reducir los límites inferior y superior de la puntuación juntos y calcular la probabilidad máxima aproximada de ganar.

"No puede haber un algoritmo así, por lo que los dos modelos deben ser diferentes", dijo David Pérez-García, de la Universidad Complutense de Madrid.

El nuevo trabajo demuestra que la clase de problemas cuyas soluciones pueden confirmarse mediante la interacción con probadores cuánticos enredados, MIP *, es completamente equivalente a la clase de problemas que no son más complicados que el problema de detención, RE. El título del trabajo describe brevemente su esencia: "MIP * = RE".

En el proceso de búsqueda de evidencia de la igualdad de las dos clases de complejidad, los informáticos demostraron la falsedad de la hipótesis de Tsirelson, lo que, gracias a trabajos anteriores, significa la falsedad de la hipótesis de Conn sobre la anidación.

Fue un shock para los investigadores de los campos relevantes que las respuestas a problemas tan complejos se identificaran en el proceso de evidencia aparentemente no relacionada del campo de la informática.

"Cuando vi un trabajo llamado MIP * = RE, definitivamente no pensaría que tuviera algo que ver con mi trabajo", dijo Navazquez, coautor de un trabajo anterior que vincula la hipótesis de Cirelson con la hipótesis de Conn sobre la anidación. "Fue una completa sorpresa para mí".

Los especialistas en física cuántica y matemáticas recién comienzan a digerir esta información. Anteriormente, los matemáticos estaban interesados en saber si pueden aproximar matrices de dimensiones infinitas por grandes finitas. Ahora, conociendo la falsedad de la hipótesis de anidación de Conn, saben que no pueden.

"Desde su resultado, es imposible", dijo Slofstra.

Los propios informáticos no intentaron encontrar la confirmación de la hipótesis de Conn sobre la anidación, por lo que otras personas deberían explicar todas las consecuencias de las respuestas que encontraron.

“Yo mismo no soy matemático. No entiendo muy bien la definición inicial de la hipótesis de Conn sobre la anidación ”, dijo Natarajan.

Ellos y los coautores sugieren que los matemáticos mismos traduzcan el nuevo resultado al lenguaje de su campo. En un artículo que declara evidencia, Vidik escribió: "No tengo dudas de que la teoría de la complejidad ya no será necesaria para obtener resultados puramente matemáticos".

La evidencia resultante interrumpe la larga cadena de investigación que condujo a ella. Durante más de tres décadas, los científicos informáticos han estado tratando de averiguar hasta dónde llegará su confirmación interactiva. Ahora tienen una respuesta en forma de un largo trabajo con un encabezado simple y referencias a Turing.

"Hay una lista bastante grande de trabajos que preguntaron sobre qué oportunidades podrían ser" en el procedimiento de confirmación con la ayuda de dos probadores confusos, dijo Natarajan. “Ahora sabemos cuáles. La historia ha terminado.

Una prueba significativa del teorema de la informática captura la física con las matemáticas.