📋 👩‍❤️‍💋‍👩 🙍🏼 MIP * = RE: evidencia de la época del campo de la informática que causó el efecto dominó en física y matemáticas 🤰🏻 ☝🏻 👩‍🌾

Los informáticos han alcanzado nuevas fronteras en la verificación de soluciones a problemas por métodos computacionales. Al mismo tiempo, encontraron respuestas a las preguntas abiertas más importantes de la mecánica cuántica y las matemáticas puras.

En 1935, Albert Einstein, trabajando con Boris Podolsky y Nathan Rosen, investigó la posibilidad abierta por las nuevas leyes de la física cuántica: dos partículas pueden estar enredadas cuando incluso grandes distancias no violan su interconexión. Al año siguiente, Alan Turing formuló la primera teoría general de la computación y demostró que hay problemas que las computadoras nunca pueden resolver. Estas dos ideas revolucionaron los campos de la ciencia con los que se relacionan. Además, parecía que no tenían nada que ver el uno con el otro. Pero ahora la prueba

MIP * = RE los combinó, lo que condujo a la solución de muchos problemas en el campo de la informática, la física y las matemáticas.

Las computadoras cuánticas realizan cálculos utilizando bits cuánticos entrelazados (qubits), en lugar de ceros y unos clásicos. Nueva evidencia indica que tales computadoras, en teoría, pueden usarse para probar soluciones a una gran cantidad de problemas. La conexión entre el entrelazamiento cuántico y la informática tradicional fue una gran sorpresa para muchos investigadores.

Miguel Navascués es estudiante de física cuántica en el Instituto de Óptica Cuántica e Información Cuántica en Viena. "Eso fue una completa sorpresa", dijo, comentando la evidencia.

Los coautores de la evidencia establecieron el objetivo de definir los límites del enfoque para verificar soluciones a problemas computacionales. Este enfoque implica enredo cuántico. Después de descubrir estos límites, los investigadores llegaron a la solución de otros dos problemas, que era casi un subproducto de su trabajo. Estamos hablando de la hipótesis de Zirelson en física con respecto al modelado matemático del entrelazamiento cuántico y el problema relacionado en matemáticas puras: el problema de Conn en la teoría del álgebra de von Neumann (problema de integración de Conn).

Como resultado, los resultados de aplicar la evidencia en matemáticas y física causaron algo así como el efecto dominó.

“Todas las ideas pertenecen al mismo período. Es agradable verlos reunirse nuevamente de una manera tan espectacular ", dice Henry Yuen) de la Universidad de Toronto, uno de los coautores de la evidencia. Aparte de él en este trabajo participaron Chzhenfen Ji ( Zhengfeng de Ji ) de la Universidad Tecnológica de Sydney, John Wright ( John Wright ) de la Universidad de Texas en Austin, Anand Natarajan ( Anand Natarajan ) y Thomas Vidic ( de Thomas Vidick ) del Instituto de Tecnología de California. Los cinco científicos trabajan en el campo de la informática.

Problemas insolubles

Turing, incluso antes del advenimiento de las computadoras, sentó las bases sobre las cuales se construyen las reflexiones sobre la informática. Y él, al mismo tiempo, demostró que hay un cierto problema que, lo que es demostrable, las computadoras no pueden resolver. Este es el llamado problema de apagado.

Típicamente, los programas de computadora reciben algo en la entrada y generan salida. Pero a veces se quedan atrapados en ciclos interminables, lo que significa que nunca se detienen. Cuando esto sucede, solo hay una forma de salir de esta situación. Según Henry Yuen, debe detener manualmente el programa. Solo necesitas poner fin a su trabajo.

Turing demostró que no existe un algoritmo universal capaz de determinar si un programa se detendrá alguna vez. Para averiguarlo, debe ejecutar el programa.

Henry Yuen, Thomas Widick, Zhengfeng Ji, Anand Natarajan, John Wright

“ Esperaste un millón de años y el programa no se detuvo. ¿Quizás solo tienes que esperar 2 millones de años? No hay forma de saberlo de antemano ", dice William Slofstra ( William Slofstra ), un matemático de la Universidad de Waterloo.

Turing, desde un punto de vista técnico, demostró que el problema de apagado no tiene solución. Incluso la computadora más poderosa que puedas imaginar no es capaz de manejarla.

Después de Turing, los informáticos comenzaron a clasificar otras tareas por su complejidad. Las tareas más complejas requieren más potencia de procesamiento, más tiempo de procesador y memoria. Este es un estudio de la complejidad computacional de los algoritmos.

Como resultado, cualquier problema plantea dos grandes preguntas para los investigadores: “¿Qué tan difícil es resolverlo? ¿Cuál es la dificultad de verificar que la solución resultante sea correcta?

Interrogatorio de la decisión mediante interrogatorio.

Si las tareas son relativamente simples, sus soluciones se pueden verificar de forma independiente. Pero cuando las tareas se vuelven más complicadas, incluso verificar los resultados de su solución puede ser increíblemente difícil. A pesar de esto, en 1985, los informáticos decidieron que era posible generar confianza en la exactitud de la respuesta, incluso si no era posible confirmar esto por sí mismos.

El método de verificación sigue la lógica del interrogatorio policial.

Si el sospechoso cuenta una historia cuidadosamente pensada, entonces el investigador probablemente no podrá simplemente tomar y encontrar la confirmación de cada uno de sus detalles. Pero al hacer las preguntas correctas, puedes atrapar al sospechoso con una mentira o confirmar la veracidad de su historia.

En términos de informática, los dos lados del interrogatorio están representados por dos computadoras. El primero es un potente sistema informático que ofrece una solución al problema. Se le llama testigo. El segundo ya no es un dispositivo tan poderoso que hace preguntas al evaluador para determinar si la respuesta que ofrece es correcta. Esta computadora se llama un verificador.

Considere un ejemplo simple. Supongamos que alguien (el verificador) sufre de daltonismo. Alguien más (el testigo) afirma que las dos bolas están pintadas en diferentes colores y no son diferentes entre sí. El verificador no puede verificar esta declaración por sí mismo. Pero, habiendo construido inteligentemente el interrogatorio, puede descubrir si esto es realmente así.

Para hacer esto, puedes esconder las bolas detrás de la espalda y mezclarlas. Y luego, pregúntale al probador qué bola está en cada mano. Si son realmente diferentes, el probador siempre debe responder a esa pregunta correctamente. Pero si tienen el mismo color, es decir, se ven exactamente iguales, la mitad de las respuestas del probador resultarán incorrectas.

Thomas Widick dice que si más de la mitad de las respuestas del probador resultan correctas, uno puede estar muy seguro de que las bolas tienen diferentes colores.

Al hacer preguntas de prueba, puede verificar las soluciones de una clase más amplia de problemas de los que puede verificar usted mismo.

En 1988, los informáticos examinaron una situación en la que hay dos probadores que ofrecen soluciones para el mismo problema. Al final, si hay dos sospechosos que pueden ser interrogados, esto simplificará la divulgación del delito o la verificación de la decisión, ya que pueden verse obligados a enfrentarse entre sí.

Según Thomas Widick, esto le da más influencia al verificador. Él interroga, hace preguntas relacionadas, verifica las respuestas. Si los sospechosos dicen la verdad, sus respuestas deberían coincidir entre sí la mayor parte del tiempo. Si mienten, sus respuestas a menudo divergirán.

Del mismo modo, los investigadores demostraron que al interrogar a dos testigos por separado, haciéndoles preguntas sobre las soluciones que encontraron, es posible verificar rápidamente las soluciones de una clase de problemas aún más extensa que cuando trabajan con un probador.

Los estudios de la complejidad computacional de los algoritmos pueden parecer puramente teóricos, pero están muy relacionados con el mundo real. Los recursos que las computadoras necesitan para resolver problemas y verificar soluciones (tiempo y memoria) son recursos físicos. Por esta razón, los nuevos descubrimientos en física pueden cambiar el enfoque del estudio de la complejidad computacional.

Anand Natarajan dice que si nos alejamos de la base física clásica de los cálculos y elegimos algo completamente diferente, como los mecanismos cuánticos, también obtendremos una nueva teoría de la complejidad computacional.

La nueva evidencia es el resultado final de una colisión de científicos informáticos del siglo XXI con una de las ideas más extrañas de la física del siglo pasado, con la idea del enredo cuántico.

Problema de Conn

Cuando dos partículas están enredadas, de hecho, no se afectan entre sí. No existe una relación causal entre sus acciones. Einstein y sus coautores trabajaron en esta idea en un artículo de 1935. Posteriormente, los físicos y matemáticos intentaron llegar a una forma matemática de describir lo que realmente significa el enredo cuántico.

Sin embargo, estos esfuerzos han llevado a resultados mixtos. Los científicos han ideado dos modelos matemáticos diferentes de enredos. Sin embargo, no estaba claro si estos modelos son equivalentes entre sí.

La presencia de tal disonancia potencial, de forma indirecta, condujo a la aparición de un problema importante en el campo de las matemáticas puras. Este es el problema de Conn en la teoría de las álgebras de von Neumann. Al final, jugó el papel de algún tipo de "pista" que cinco informáticos aprovecharon para derivar sus pruebas.

La primera forma de modelar el entrelazamiento cuántico era percibir las partículas como objetos espacialmente aislados entre sí. Supongamos que una de estas partículas está en la Tierra y la otra está en Marte. La distancia entre ellos es algo que excluye una relación causal entre ellos (están causalmente separados). Esto es lo que se llama un modelo de producto tensorial.

Pero en algunas situaciones, la separación causal de las entidades no es del todo obvia. Como resultado, los matemáticos llegaron a una segunda forma más general de describir la independencia causal.

Cuando el orden en que se realizan dos operaciones no afecta el resultado, la operación se llama conmutativa: 3x2 es lo mismo que 2x3. En este segundo modelo, las partículas se enredan cuando sus propiedades están correlacionadas, pero el orden en que se realizan las mediciones no importa. Uno puede tomar medidas en la partícula A para predecir el momento de la partícula B, y viceversa. En cualquier caso, el resultado será el mismo. Esto se llama un modelo de enredo de operador de conmutación.

Ambas descripciones de enredos usan matrices de números llamados matrices. Las matrices consisten en filas y columnas. El modelo de producto tensorial utiliza matrices con un número finito de filas y columnas. El modelo de operador de conmutación utiliza objetos más generales que funcionan como matrices con un número infinito de filas y columnas.

Con el tiempo, los matemáticos comenzaron a estudiar estas matrices como objetos de interés independiente, no conectados de ninguna manera con el mundo físico. En línea con este trabajo, el matemático Alain Connes sugirió en 1976 que debería ser posible aproximar muchas matrices de dimensión infinita utilizando matrices de dimensión finita. Esta es una de las consecuencias del problema Conn en la teoría de las álgebras de von Neumann.

En la próxima década, el físico Boris Tsirelson formuló una nueva versión de este problema, que nuevamente lo devolvió al campo de la física. Zirelson sugirió que los modelos del producto tensor y el operador de conmutación son aproximadamente equivalentes entre sí. Esta afirmación tiene sentido, ya que ambos modelos, teóricamente, son dos formas diferentes de describir el mismo fenómeno físico. El trabajo posterior mostró que debido a la conexión entre matrices y modelos físicos que los usan, los problemas de Conn y Zirelson están indirectamente relacionados: si uno se resuelve, el otro se resolverá.

Pero la solución a ambos problemas provino de un lugar completamente inesperado.

Juego de física

En la década de 1960, al físico John Bell se le ocurrió una prueba para determinar si el entrelazamiento cuántico es un fenómeno físico real, no un concepto teórico. La prueba utilizó algo así como un juego, cuyos resultados permitieron descubrir si ciertos mecanismos que no están relacionados con la física ordinaria funcionan durante el juego.

Más tarde, los informáticos se dieron cuenta de que esta prueba relacionada con el entrelazamiento cuántico también se puede utilizar como una herramienta para verificar soluciones a problemas muy complejos.

Pero antes de continuar, hablemos sobre el juego. Imagine que hay dos jugadores: Alice y Bob, y también un campo de juego 3x3. El presentador asigna una línea a Alice y le pide que ingrese 0 o 1 en cada celda, de modo que su suma dé un número impar. Bob obtiene una columna que debe llenarse con ceros y unos para que su suma dé un número par. Ganarán si ponen el mismo número en el lugar donde se cruzan la fila y la columna. Es imposible comunicarse con él.

En circunstancias normales, lo mejor que pueden hacer es ganar el 89% del tiempo. Pero si se tiene en cuenta el factor de enredo cuántico, entonces sus posibilidades mejoran.

Imagina que Alice y Bob han enredado partículas cuánticas. Toman medidas de sus partículas y usan los resultados de la medición para indicar qué escribir en cada celda: 0 o 1. Debido a que las partículas están enredadas, los resultados de la medición se correlacionarán entre sí. Y esto también significa que las acciones de los jugadores estarán interconectadas. Como resultado, resulta que siempre podrán ganar el juego.

Si hay diferentes números en la celda donde se cruzan la fila y la columna, el juego se pierde. Si son iguales, ganaron.

Entonces, si resulta que dos jugadores son sorprendentemente exitosos en este juego, entonces podemos concluir que están usando algo diferente de lo que la física clásica puede dar. Estos experimentos de "Bell" hoy se llaman juegos "no locales", en referencia a la separación de jugadores. Los físicos, de hecho, realizan juegos similares en laboratorios.

Henry Yuen dice que a lo largo de los años, los científicos han realizado experimentos para demostrar la realidad de estos fenómenos aterradores.

Al igual que con el análisis de cualquier juego, es posible que necesite averiguar con qué frecuencia los jugadores pueden ganar en un juego no local, dado que juegan tan bien como pueden. Por ejemplo, en el caso del solitario, puedes calcular la frecuencia de posibles victorias de quien juega perfectamente.

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

Los informáticos llegaron a la respuesta utilizando los dos modelos de entrelazamiento cuántico descritos anteriormente. El algoritmo que utiliza el modelo de producto tensor establece el valor mínimo para el cálculo aproximado de la probabilidad máxima de ganar para todos los juegos no locales. Otro algoritmo que utiliza el modelo del operador de conmutación establece el valor máximo.

La respuesta dada por las implementaciones de estos algoritmos, cuanto más precisa, más tiempo se ejecuta el programa. Si la hipótesis de Zirelson es cierta, y estos dos modelos son equivalentes, entonces los límites inferior y superior deben acercarse entre sí, convirtiéndose en un solo valor que represente la probabilidad máxima aproximada de ganar.

Pero si la hipótesis de Zirelson no es cierta, y los dos modelos no son equivalentes, entonces, según Henry Yuen, los límites superior e inferior siempre estarán separados. Y no habrá forma de calcular ni siquiera el porcentaje aproximado de ganancias para juegos no locales.

Cinco investigadores en su nuevo trabajo aprovecharon el argumento sobre si los límites superior e inferior convergen, y si la hipótesis de Zirelson es verdadera o falsa. Hicieron esto en aras de encontrar la respuesta a la pregunta de en qué situaciones es posible verificar soluciones a problemas computacionales.

Ayuda intrincada

Al comienzo de los dos mil científicos informáticos, comenzaron a preguntarse cómo cambiaría el rango de tareas, cuyas soluciones pueden verificarse "interrogando" a dos probadores que poseen partículas intrincadas.

La mayoría de los científicos pensaban que la confusión perjudica la verificación. Al final, será más fácil para los dos "sospechosos" conciliar testimonios falsos si tienen alguna forma de coordinar las respuestas.

Pero en los años siguientes, quedó claro que la afirmación opuesta era cierta: al "interrogar" a los probadores que tienen partículas intrincadas, se puede verificar una clase mucho más amplia de problemas que cuando se trabaja con probadores que no tienen tales partículas.

Thomas Widick dice que el enredo es una forma de crear correlaciones que parecen ayudar a los testigos a mentir. Pero, de hecho, este fenómeno se puede utilizar para su ventaja.

Para entender cómo usarlo, primero debe lidiar con la escala casi sobrenatural de tareas cuyas soluciones se pueden verificar gracias a este procedimiento interactivo.

Imagine un gráfico: un conjunto de puntos (vértices) conectados por líneas (caras). Debe averiguar si, usando tres colores, es posible pintar los vértices de modo que no haya dos vértices en el gráfico que estén conectados por una cara y al mismo tiempo pintados del mismo color. Si es posible, ese gráfico es "tricolor".

Si le da a un par de pruebas un gráfico muy grande, y le dicen que es "tricolor", entonces podría preguntarse si hay una manera de verificar su respuesta.

En el caso de gráficos muy grandes, sería imposible verificar la respuesta directamente. En cambio, puede preguntar a cada uno de los evaluadores qué color tiene uno de los dos vértices conectados. Si cada uno de ellos informa de diferentes colores, y darán respuestas similares cada vez que se les pregunte sobre esto, tendremos la confianza de que el gráfico es de hecho "tricolor".

Pero incluso esta estrategia de interrogación no funcionará en grandes gráficos con más caras y vértices que los átomos en el universo. Incluso hacer una pregunta específica (“Dime el color del vértice XYZ”) se convierte en un problema insoportable para alguien que intenta verificar una solución a un problema. La cantidad de datos necesarios para especificar simplemente el nombre de un vértice particular es mayor de lo que el verificador puede almacenar en la memoria disponible.

Pero el entrelazamiento cuántico hace posible un esquema de trabajo, en cuya aplicación los probadores mismos formulan las preguntas.

“El verificador no necesita hacer preguntas. El verificador obliga a los proponentes a formular independientemente estas preguntas y responderlas ”, dice John Wright.

El verificador necesita que los probadores informen los colores de los vértices conectados. Si los vértices no están conectados, las respuestas a las preguntas no dirán nada sobre si el gráfico es "tricolor" o no. En otras palabras, el verificador necesita probadores para hacer preguntas relacionadas. Uno de los probadores pregunta sobre la parte superior de ABC y el segundo sobre la parte superior de XYZ. Se supone que los dos picos están conectados, a pesar del hecho de que ninguna de las pruebas sabe cuál de las dos "piensa". (Esto es similar a cómo Alice y Bob esperan escribir el mismo número en la misma celda, a pesar de que ninguno de ellos sabe con qué fila o columna de la tabla trabaja el otro).

Si dos probadores formularan de manera completamente independiente tales preguntas, entonces no habría ningún mecanismo para obligarlos a seleccionar vértices conectados (correlacionados), de tal manera que el verificador verifique sus respuestas. Pero tal correlación es exactamente lo que puede lograr el enredo cuántico.

Thomas Widick dice que usarán complejidades para referir prácticamente todos los casos a los testigos. Los científicos hacen que los evaluadores elijan sus propias preguntas.

Al final de este procedimiento, cada uno de los probadores informa un color de vértice. El verificador verifica si estos son de diferentes colores o no. Si el gráfico es de hecho "tricolor", entonces los evaluadores nunca deberían informar el mismo color.

Según Henry Yuen, si el gráfico es "tricolor", entonces los evaluadores pueden convencer al investigador de que esto es así.

Al final resultó que, este procedimiento de verificación es otro ejemplo de un juego no local. Los verificadores "ganan" si convencen al investigador de que su decisión es correcta.

En 2012, Thomas Widik y Tsuyoshi Ito) demostró que uno puede jugar una amplia variedad de juegos no locales utilizando intrincados probadores para probar soluciones. Esto se aplica, como mínimo, al mismo número de tareas que se pueden verificar al interrogar dos computadoras clásicas. Por lo tanto, el uso de evidencia confusa no perjudica la verificación. El año pasado, Anand Natarajan y John Wright demostraron que interactuar con testigos intrincados en realidad extiende la clase de problemas cuyas soluciones pueden verificarse.

Pero los informáticos no sabían sobre la gama completa de tareas cuyas soluciones se pueden verificar utilizando este enfoque. Ahora lo saben.

efecto dominó

En su nuevo trabajo, cinco científicos demostraron que el "interrogatorio" de testigos confundidos hace posible verificar soluciones a problemas irresolubles, incluida la solución de un problema de cierre.

Henry Yuen dice que los modelos de este tipo tienen capacidades de verificación inimaginables.

Pero la tarea de detención no tiene solución. Y este hecho fue la fuerza impulsora que condujo a la prueba final.

Imagine que entregó el programa a un par de testigos confundidos. Les preguntaste si este programa alguna vez se detendrá. Estás listo para verificar sus respuestas a través de algún tipo de juego no local. Los revisores generan preguntas y "ganan" en función de la coordinación de sus respuestas.

Si el programa realmente se detiene, los proponentes deberían poder ganar el juego en el 100% de los casos. Esto es similar a un ejemplo con un gráfico: si es verdaderamente "tricolor", entonces los probadores enrevesados nunca deberían informar el mismo color para los vértices conectados. Si el programa nunca se detiene, los evaluadores deberían ganar solo por casualidad, 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 tendrá que resolver el problema de detención. Pero resolver este problema es imposible. Esto significa que es imposible encontrar el nivel máximo aproximado de probabilidad de ganar para juegos no locales, así como para el problema de detención.

Y esto, a su vez, significa que la hipótesis de Tsirelson es falsa: los dos modelos de entrelazamiento cuántico no son equivalentes. Si fueran equivalentes, entonces sería posible reducir los límites inferior y superior al mismo valor y calcular la probabilidad máxima aproximada de ganar.

David Pérez-García, de la Universidad Complutense de Madrid, dice que dicho algoritmo no puede existir, como resultado, los dos [modelos] deben ser diferentes.

El nuevo trabajo demuestra que la clase de problemas cuyas soluciones pueden verificarse con la ayuda de intrincados dispositivos de prueba cuánticos, una clase llamada MIP *, es exactamente igual a la clase de problemas que no son más complicados que el problema de detención: la clase RE. El título del artículo contiene una indicación concisa de esto: "MIP * = RE".

En el curso de la prueba de que las dos clases de complejidad son iguales, los científicos demostraron que la hipótesis de Tsirelson es falsa, lo que, gracias a trabajos previos, significa que la hipótesis de Conn también es falsa.

Los investigadores que trabajan en sus respectivos campos se sorprendieron por el hecho de que se obtuvieron soluciones a problemas a gran escala gracias a la evidencia del campo de la informática, que, al parecer, no está relacionada con las matemáticas y la física.

Miguel Navazquez dice que si hubiera visto un artículo con el título MIP * = RE, no habría pensado que ella tenía algo en común con su trabajo. Fue coautor de un trabajo anterior que vincula las hipótesis de Zirelson y Conn. Para él, esto fue una completa sorpresa.

Los físicos y matemáticos cuánticos apenas comienzan a dominar una nueva prueba. Antes de eso, los matemáticos estaban interesados en la cuestión de si pueden aproximar matrices de dimensión infinita, utilizando en su lugar matrices grandes de dimensión finita. Ahora, gracias al hecho de que la hipótesis de Conn ha demostrado ser falsa, saben que esto no se puede hacer.

"Sus resultados indican que esto no es posible", dijo William Slofstra.

Los informáticos no buscaron analizar la hipótesis de Conn. Y, como resultado, no están en la mejor posición para explicar las posibles consecuencias de resolver este problema.

“Personalmente, no soy matemático. "No entiendo muy bien la formulación inicial de la hipótesis Conn", dice Anand Natarajan.

Él y sus coautores esperan que los matemáticos traduzcan nuevos resultados a su propio idioma. En una publicación que presenta pruebas, Thomas Widick escribe: "No tengo dudas de que al final, la teoría de la complejidad computacional no será necesaria para obtener resultados puramente matemáticos".

Sin embargo, cuando otros investigadores se familiarizan con la prueba, el camino de la investigación, gracias al cual fue posible llegar a él, llega a su fin. Durante más de tres décadas, los científicos informáticos simplemente han intentado averiguar hasta dónde pueden llevarlos la verificación interactiva de las soluciones de problemas. Ahora frente a ellos se encuentra la respuesta, en forma de un artículo largo con un título simple y con ecos de las ideas de Turing.

“Hay muchos trabajos cuyos autores solo se preguntan cuáles son las posibilidades de un procedimiento de verificación utilizando dos intrincadas pruebas cuánticas. Ahora sabemos lo poderoso que es este procedimiento. Esta historia ha llegado a su fin ", dice Anand Natarajan.

¡Queridos lectores! ¿Qué significa la prueba MIP * = RE para el área en la que trabaja?