El universo de tareas controladas por computadora ha crecido. ¿Gracias a qué ingrediente secreto sucedió esto? Debido al enredo cuántico.
Imagina que alguien vino a ti y te dijo que tiene un oráculo que puede revelar los secretos secretos del universo. Puede que le interese esto, pero le sería difícil creerlo. Le gustaría encontrar una manera de confirmar que el oráculo está diciendo la verdad.
Este es el principal problema de la informática. Algunas tareas son demasiado difíciles de resolver en un tiempo razonable. Pero sus decisiones son fáciles de verificar. Ante esto, los científicos informáticos quieren saber: ¿qué tan compleja puede ser una tarea, cuya solución aún se puede verificar?
Resulta que la respuesta a esta pregunta es: casi inimaginablemente compleja.
En un
artículo que apareció en abril de 2019, dos especialistas en informática aumentaron radicalmente el número de tareas que caen en la categoría de "difícil de resolver, fácil de verificar". Describen un método que permite verificar soluciones a problemas de complejidad casi incomprensible. "Suena loco", dijo Thomas Widick, un especialista en TI del Instituto de Tecnología de California que no está involucrado en este trabajo.
El estudio es aplicable a las computadoras cuánticas que realizan cálculos de acuerdo con las reglas no intuitivas de la mecánica cuántica. Las computadoras cuánticas apenas han aparecido, pero en el futuro tienen el potencial de revolucionar la informática.
El nuevo trabajo, de hecho, nos da influencia sobre ese oráculo todopoderoso. Incluso si el oráculo promete darle soluciones listas para problemas cuyas posibilidades de solución están más allá de sus capacidades, aún queda una forma de verificar si el oráculo está diciendo la verdad.
Hasta el fin del universo
Cuando un problema es difícil de resolver, pero fácil de verificar, encontrar una solución lleva mucho tiempo, pero verificar la corrección de una solución en particular no lo hace. Por ejemplo, suponga que una persona le muestra un gráfico: un conjunto de puntos (vértices) conectados por líneas (bordes). Una persona pregunta si es posible colorear los vértices del gráfico con tres colores para que no haya dos vértices conectados que tengan el mismo color.
La tarea de tres colores es difícil de resolver. En el caso general, el tiempo requerido para buscar la coloración de vértices (o determinar que dicha coloración no existe) aumenta exponencialmente al aumentar el tamaño del gráfico. Si, por ejemplo, la búsqueda de una solución para un gráfico con 20 vértices toma 3
20 ns, es decir, unos segundos, entonces para un gráfico con 60 vértices tomará 3
60 ns, que es 100 veces la edad actual del Universo.
Pero digamos que alguien afirma haber pintado el recuento con tres colores. La verificación de esta aplicación no llevará mucho tiempo. Solo necesita recorrer todos los vértices uno por uno, estudiando los vértices asociados con ellos. A medida que aumenta el tamaño del gráfico, el tiempo de esta comprobación aumenta lentamente, como
polinomio . Como resultado, una computadora no tarda mucho más en verificar el color de una gráfica de 60 vértices que en una gráfica de 20 vértices.
"Con el color correcto en tres colores, es fácil probar su rendimiento", dijo
John Wright , físico del Instituto de Tecnología de Massachusetts, quien escribió este trabajo junto con
Anand Natarajan de Caltech.
En la década de 1970, los informáticos determinaron una clase de tareas que son fáciles de verificar, incluso si algunas de ellas son difíciles de resolver. Llamaron a esta clase NP,
tiempo polinómico no determinista . Desde entonces, en informática, la clase NP se ha estudiado más que otras. En particular, a los científicos informáticos les gustaría saber cómo cambia esta clase cuando el algoritmo de prueba recibe nuevas formas de verificar la corrección de la solución.
Preguntas correctas
Antes del trabajo de Natarajan y Wright, el poder de las inspecciones aumentó en dos grandes saltos.
Para entender el primero, imagine que no distingue entre colores. Alguien coloca dos cubos en la mesa frente a usted y le pregunta si son del mismo color o diferentes. Esta tarea es imposible para ti. Además, no puede confirmar la corrección de la solución de otra persona a este problema.
Sin embargo, se le permite hacer preguntas a esta persona que lo prueba. Supongamos que el prover te dice que los cubos son de diferentes colores. Usted llama a uno de ellos "Cubo A" y al otro "Cubo B". Luego los esconde detrás de su espalda, y accidentalmente intercambia lugares entre ellos. Luego abres los cubos y le pides al probador que encuentre el dado A.
Si los cubos son de diferentes colores, esta es una pregunta muy simple. El probador reconocerá el Cubo A, si este es, por ejemplo, un cubo rojo, y lo determinará correctamente cada vez.
Sin embargo, si los cubos son del mismo color, y el probador se equivocó al llamarlos diferentes, el probador solo puede adivinar cuál es cuál. Por lo tanto, podrá determinar correctamente el Cubo A solo en el 50% de los casos. Al preguntar constantemente al probador sobre su decisión, puede confirmar si es correcta.
Anand Natarajan y John Wright"El examinador puede enviar preguntas al probador", dijo Wright, "y quizás al final de la conversación, el examinador estará más convencido de la respuesta".
En 1985, tres informáticos demostraron que dicha evidencia interactiva se puede utilizar para confirmar soluciones a problemas más complejos que los problemas de NP. Su trabajo creó una nueva clase de tareas, IP, "tiempo polinómico interactivo". El método utilizado para confirmar los colores de los cubos se puede utilizar para confirmar las respuestas a preguntas mucho más complejas.
El segundo avance ocurrió en la misma década. Parece la lógica de una investigación policial. Si tiene dos sospechosos que han cometido, en su opinión, un delito, no los interrogarán juntos. Los interrogará en diferentes habitaciones y comparará las respuestas de una con las respuestas de la otra. Al entrevistarlos individualmente, puede revelar más verdad que si tuviera un sospechoso.
"Los dos sospechosos no podrán crear una historia consistente distribuida, porque no saben cuáles son las otras respuestas", dijo Wright.
En 1988, cuatro informáticos demostraron que si le pides a dos computadoras que resuelvan el mismo problema por separado y luego las preguntas por separado, puedes confirmar una clase de problemas que es incluso mayor que IP: la clase MIP, evidencia interactiva con mucha evidencia.
Con este enfoque, es posible, por ejemplo, confirmar la corrección de colorear un gráfico en tres colores para una secuencia de gráficos que aumentan de tamaño mucho más rápido que los gráficos de NP. En NP, los tamaños de los gráficos aumentan linealmente: el número de vértices puede crecer de 1 a 2, hasta 3, hasta 4, y así sucesivamente, de modo que el tamaño del gráfico no es desproporcionadamente mayor que la cantidad de tiempo requerida para verificar el color. Pero en MIP, el número de vértices del gráfico crece exponencialmente de 2
1 a 2
2 , 2
3 , 2
4 , y así sucesivamente.
Como resultado, los gráficos resultan ser demasiado grandes incluso para caber en la memoria de la computadora, que debe pasar por la lista de vértices y verificar el color. Sin embargo, el color aún se puede verificar haciendo a los dos probadores diferentes, pero preguntas relacionadas.
En MIP, el probador tiene suficiente memoria para ejecutar un programa que nos permite determinar si dos vértices del gráfico están conectados por un borde, y puede verificar las respuestas de los probadores para asegurarse de que el color sea correcto.
Expandir la lista de tareas que son difíciles de resolver, pero fáciles de verificar, desde computadoras clásicas hasta NP, IP y MIP. Pero las computadoras cuánticas funcionan de manera muy diferente. Y durante varias décadas no estuvo claro cómo su uso cambia esta imagen: ¿es más fácil o más difícil verificar las soluciones con su ayuda?
El nuevo trabajo de Natarajan y Wright tiene la respuesta a esta pregunta.
Trucos cuánticos
Las computadoras cuánticas realizan cálculos con bits cuánticos o qubits. Tienen una propiedad como
enredarse entre sí. Y cuando dos qubits, o incluso grandes sistemas de qubit, se confunden, esto significa que sus propiedades físicas se afectan entre sí de cierta manera.
En su nuevo trabajo, Natarajan y Wright consideran un escenario que incluye dos computadoras cuánticas diferentes, con los qubits de uno confundidos con los qubits del otro.
Parecería que tal configuración empeora la calidad de la verificación de respuesta. Todo el poder de la evidencia interactiva con muchos probadores se deriva precisamente del hecho de que puedes entrevistar a dos probadores por separado y verificar sus respuestas. Si las respuestas de los probadores son las mismas, entonces es muy probable que sean ciertas. Pero si los estados cuánticos de dos probadores están confundidos, parecerían tener más oportunidades para insistir consistentemente en la exactitud de las respuestas incorrectas.
De hecho, cuando el escenario con dos computadoras cuánticas enredadas se
dio a
conocer por primera
vez en 2003, los científicos informáticos sugirieron que el enredo reduciría la posibilidad de verificación. "La reacción obvia de todos, incluido el mío, fue que los probadores en este caso tenían más oportunidades", dijo Vidik. "Pueden usar la confusión para vincular sus respuestas".
Pero, a pesar del pesimismo inicial, Vidik pasó varios años tratando de demostrar lo contrario. En 2012, él y
Tsuyoshi Ito demostraron que existe la capacidad de probar todas las tareas en MIP utilizando computadoras cuánticas enredadas.
Ahora, Natarajan y Wright han demostrado que la situación es aún mejor: con la ayuda de la complejidad, uno puede probar una clase de problemas aún mayor que sin ella. Es posible revertir la conexión entre computadoras cuánticas enredadas en beneficio del verificador.
Para entender cómo hacer esto, recuerde el procedimiento de MIP para verificar el color de los gráficos cuyos tamaños crecen exponencialmente. El probador no tiene suficiente memoria para almacenar el gráfico completo, pero tiene suficiente memoria para determinar dos vértices conectados y hacerles una pregunta sobre el color de estos vértices.
En la clase de problemas considerados por Natarajan y Wright, llamado NEEXP, un tiempo no determinista dos veces exponencial, el tamaño de los gráficos crece aún más rápido que en MIP. Los gráficos en NEEXP crecen a una "tasa exponencial doble". En lugar de crecer como grados de dos - 2
1 , 2
2 , 2
3 , 2
4 , y así sucesivamente - el número de vértices en los gráficos crece como grados de dos - 2
2 1 , 2
2 2 , 2
2 3 , 2
2 4 , y así sucesivamente. Como resultado, los gráficos se vuelven tan grandes que el inspector ya no puede encontrar un par de vértices conectados.
"Para identificar el vértice, se necesitan 2
n bits, que es exponencialmente más de lo que el verificador tiene en la memoria", dijo Natarajan. Sin embargo, Natarajan y Wright demostraron que es posible verificar la coloración de un gráfico doble exponencial en tres colores, incluso sin la capacidad de determinar qué vértices necesitan pruebas. El hecho es que puedes hacer que los propios probadores elijan las preguntas correctas.
La idea de hacer que las computadoras se interroguen sobre sus propias decisiones suena tan razonable para los informáticos como pedirles a presuntos delincuentes que se interroguen a sí mismos es definitivamente una propuesta estúpida. Eso es solo que Natarajan y Wright demostraron que esto no es así. Y la razón de esto es la confusión.
"Los estados enredados son recursos compartidos", dijo Wright. "Todo nuestro protocolo es comprender cómo utilizar este recurso compartido para crear problemas interconectados".
Si las computadoras cuánticas están confundidas, entonces su elección de vértices se correlacionará y dará el conjunto correcto de preguntas para verificar la coloración en tres colores.
Al mismo tiempo, el inspector no necesita que las dos computadoras cuánticas estén entrelazadas para que sus respuestas a estas preguntas estén correlacionadas entre sí (esto sería similar a cómo dos criminales sospechosos correlacionan su falsa coartada). Otra extraña característica cuántica trata este problema. En mecánica cuántica,
el principio de incertidumbre nos prohíbe conocer la ubicación exacta y el momento de una partícula al mismo tiempo: si mide una propiedad, destruye información sobre otra. El principio de incertidumbre limita severamente su conocimiento de cualesquiera dos propiedades "complementarias" de un sistema cuántico.
Natarajan y Wright usan esto en su trabajo. Para calcular el color del vértice, obligan a dos computadoras cuánticas a tomar medidas complementarias. Cada computadora calcula el color de su propio vértice y, por lo tanto, destruye toda la información sobre la otra. En otras palabras, la confusión permite que las computadoras hagan preguntas correlativas, pero el principio de incertidumbre les prohíbe conspirar para responderlas.
"Necesitamos hacer olvidar a los probadores, y esto es lo principal que hicieron Natarajan y Wright en su trabajo", dijo Vidik. "Forzan al probador a borrar la información a través de la medición".
Las consecuencias de su trabajo se pueden llamar casi existenciales. Antes de que se publicara el trabajo, la limitación en el conocimiento que podemos obtener con plena confianza era mucho menor. Si el conjunto de NEEXP nos respondiera a un problema, solo tendríamos que aceptarlo por fe. Pero Natarajan y Wright salieron de estos límites e hicieron posible confirmar las respuestas de un universo mucho más grande de problemas computacionales.
Y ahora que han hecho esto, no está claro dónde se encuentra el próximo límite de verificabilidad. "Podría ser mucho más allá", dijo Lance Fortnau, especialista en TI del Instituto de Tecnología de Georgia. "Dejan abierta la oportunidad de dar el siguiente paso".