Urmila Mahadev pasó ocho años en la magistratura en busca de una respuesta a una de las preguntas más básicas de la computación cuántica: ¿cómo sabemos que una computadora cuántica hizo al menos algo a nivel cuántico?
En la primavera de 2017, Urmila Mahadev estaba en una buena posición, desde el punto de vista de la mayoría de los estudiantes graduados. Acaba de resolver el problema crucial de la computación cuántica: el campo de la informática, aprovechando sus capacidades de las extrañas leyes de la física cuántica. Junto con sus trabajos anteriores, un nuevo resultado de Mahadev que describe el llamado "La informática a ciegas" hizo "obvio que ella es una estrella en ascenso", dijo
Scott Aaronson , un especialista en TI de la Universidad de Texas en Austin.
Mahadev, que en ese momento tenía 28 años, ya estaba en su séptimo año en la escuela de posgrado de la Universidad de California en Berkeley, mucho más que el tiempo que les toma a la mayoría de los estudiantes perder la paciencia y querer terminar la escuela. Y luego, finalmente, pudo escribir una "excelente tesis doctoral", dijo
Umesh Vazirani , su curadora en Berkeley.
Pero Mahadev no terminó de estudiar ese año. Ella ni siquiera considera este tema. Ella no ha terminado todavía.
Durante más de cinco años, trabajó con otra tarea de investigación, que Aaronson llamó "una de las preguntas más básicas que se pueden formular en el campo de la computación cuántica". A saber: si le pide a una computadora cuántica que haga un cálculo por usted, ¿cómo sabe si sigue sus instrucciones y, de hecho, hace algo a nivel cuántico?
Esta pregunta pronto puede dejar de ser puramente académica. Los investigadores esperan que no pasen muchos años, y las computadoras cuánticas podrán ofrecer una aceleración exponencial para resolver muchos problemas, desde modelar una situación cerca de un agujero negro hasta simular el plegamiento de proteínas grandes.
Pero tan pronto como una computadora cuántica pueda realizar cálculos de los que la clásica no es capaz, ¿cómo sabemos que los conduce correctamente? Si no cree en una computadora ordinaria, en teoría puede estudiar cuidadosamente cada paso de sus cálculos usted mismo. Pero las computadoras cuánticas resisten inherentemente tales controles. Para empezar, su trabajo es extremadamente complicado: para registrar una descripción del estado interno de una computadora, que consta de solo unos pocos cientos de bits cuánticos o qubits, necesitará un disco duro más grande que el Universo observado.
E incluso si tuviera un lugar para escribir esta descripción, no podría desarmarse. El estado interno de una computadora cuántica suele ser una superposición de muchos estados no cuánticos, sino clásicos (como el del gato Schrödinger, que está vivo y muerto). Pero tan pronto como mides un estado cuántico, inmediatamente colapsa en uno de los clásicos. Eche un vistazo dentro de una computadora cuántica con 300 qubits, y verá solo 300 bits clásicos, ceros y unos, sonriéndole cortésmente a cambio.
"Una computadora cuántica es poderosa, pero misteriosa", dijo Vazirani.
Dadas estas limitaciones, los informáticos han estado pensando durante mucho tiempo si una computadora cuántica puede proporcionar una garantía absolutamente confiable de que realmente hizo lo que dice ser. "¿La interacción entre los mundos cuántico y clásico será lo suficientemente fuerte como para hacer posible ese diálogo?" Preguntó
Dorit Akharonova , un científico de la computación en la Universidad Hebrea de Jerusalén.
En el segundo año de la magistratura, Mahadev fue capturada por esta tarea, y ella ni siquiera comprende completamente por qué. En los años siguientes, trató de usar un enfoque para ella, luego otro. "Tuve muchos de esos momentos cuando me pareció que estaba haciendo todo bien, y luego todo se rompió, ya sea muy rápido o después de un año", dijo.
Pero ella se negó a rendirse. Mahadev mostró un nivel de determinación inmutable que Vazirani no había conocido antes. "En este sentido, Urmila es absolutamente extraordinario", dijo.
Y ahora, después de ocho años de estudios de posgrado, Mahadev tuvo éxito. Creó un protocolo interactivo con el que un usuario que no tiene capacidades cuánticas puede utilizar una criptografía para frenar una computadora cuántica y dirigirla a cualquier parte, con total confianza en que la computadora cuántica obedece las órdenes. El enfoque de Mahadev, dijo Vazirani, le da al usuario "una palanca de presión de la cual la computadora no puede deshacerse".
"Es absolutamente asombroso" que un estudiante graduado pueda lograr este resultado solo, dijo Aaronson.
Mahadev, ahora un postdoctorado de investigación en Berkeley, presentó su protocolo en octubre de 2018 en el
Simposio anual
sobre Ciencias de la Computación , una de las conferencias informáticas más grandes celebradas este año en París. La audiencia le otorgó su trabajo con los premios "mejor trabajo" y "mejor trabajo estudiantil", un premio raro para un especialista en informática teórica.
En una publicación de blog,
Thomas Widick , un especialista en TI del Instituto de Tecnología de California, que había trabajado con Mahadev en el pasado, describió su resultado como "una de las ideas más destacadas que surgieron en la intersección de la informática cuántica y la informática teórica en los últimos años".
Los investigadores en el campo de la informática están encantados no solo por lo que el protocolo Mahadev es capaz de hacer, sino también por un enfoque radicalmente nuevo que ayuda a hacer frente a este problema. El uso de la criptografía clásica en el campo cuántico es "una idea verdaderamente innovadora", escribió Vidik. "Creo que muchos otros resultados crecerán con estas ideas".
Largo camino
Mahadev creció en Los Ángeles, en una familia de médicos, y estudió en la Universidad del Sur de California, donde se mudó de un área a otra, inicialmente convencida solo de que ella misma no quería ser doctora. Luego se interesó mucho en el curso de informática teórica, que fue impartido por Leonard Aidleman, uno de los creadores del famoso algoritmo de cifrado RSA. Entró en la escuela de posgrado en Berkeley, indicando en una nota explicativa que estaba interesada en todos los aspectos de la informática teórica, excepto la computación cuántica.
"Era algo completamente ajeno al que tenía la menor idea", dijo.
Pero, una vez en Berkeley, pronto cambió de opinión bajo la influencia de las explicaciones disponibles de Wazirani. Le presentó a la búsqueda de un protocolo para confirmar la computación cuántica, y esta tarea "realmente hizo que su imaginación funcionara", dijo Vazirani.
"Los protocolos son como acertijos", explicó Mahadev. "Es más fácil para mí que con otras preguntas, porque aquí puedes comenzar a pensar de inmediato en los protocolos, dividirlos en pedazos y ver cómo funcionan". Ella eligió esta tarea para su doctorado, emprendiendo un "camino muy largo", como dijo Vazirani.
Si una computadora cuántica puede resolver un problema que el clásico no es capaz de hacer, esto no significa automáticamente que la solución será difícil de verificar. Tomemos, por ejemplo, el problema de factorizar números grandes: se cree que una computadora cuántica grande puede resolverlo de manera eficiente, pero al mismo tiempo permanece más allá de las capacidades de cualquier computadora clásica. Pero incluso si una computadora clásica no puede factorizar el número, puede verificar fácilmente si el resultado cuántico es correcto; solo necesita multiplicar todos los factores y ver si dan la respuesta correcta.
Sin embargo, los científicos informáticos creen (y recientemente han dado un paso para demostrar) que muchas tareas que una computadora cuántica podría resolver carecen de tal característica. En otras palabras, una computadora clásica no solo no puede resolverlos, ni siquiera puede reconocer si la solución propuesta será correcta. Como resultado, en 2004,
Daniel Gottsman , físico teórico del Instituto Perimetral de Waterloo, preguntó si era posible llegar a un protocolo que permitiera a una computadora cuántica demostrarle a un observador no cuántico que realmente había logrado lo que estaba afirmando.
Durante cuatro años, los investigadores de computación cuántica han encontrado una respuesta parcial. Dos equipos diferentes
mostraron que una computadora cuántica puede probar sus cálculos, pero no a un verificador puramente clásico, sino a uno que tiene acceso a otra computadora cuántica muy pequeña. Posteriormente, los investigadores mejoraron este enfoque al mostrar que el evaluador solo necesitaba la capacidad de medir el estado de un qubit a la vez.
Y en 2012, un equipo de investigadores, que incluía a Vazirani, demostró que un verificador completamente clásico puede verificar los cálculos cuánticos si fueron realizados por un par de computadoras cuánticas que no se comunicaban entre sí. Sin embargo, su enfoque fue diseñado específicamente para tal escenario, y la tarea pareció encontrarse en un callejón sin salida, dijo Gottsman. "Creo que probablemente hubo personas que pensaron que no había forma de ir más allá".
Alrededor de este tiempo, Mahadev se enfrentó con el problema de la confirmación. Al principio, trató de producir un resultado "incondicional", sin especificar lo que una computadora cuántica puede y no puede hacer. Pero, después de que trabajó en la tarea durante algún tiempo sin éxito, Vazirani propuso la posibilidad de utilizar la criptografía "post-cuántica", es decir, la criptografía, cuya ruptura, según los investigadores, está más allá de las capacidades de las computadoras cuánticas, aunque con seguridad ellos no lo saben (Los métodos como el algoritmo RSA utilizado para cifrar las transferencias en línea no son posteriores a la cuantía: una computadora cuántica grande puede descifrarlos, porque su seguridad se basa en la dificultad de factorizar números grandes).
En 2016, mientras trabajaban en una tarea diferente, Mahadev y Vazirani hicieron un gran avance, que será decisivo en el futuro. Junto con
Paul Cristiano , un especialista en TI de OpenAI, una empresa con sede en San Francisco, idearon una forma de utilizar la criptografía para hacer que una computadora cuántica entre en un "estado secreto", un estado que es descrito por un verificador clásico, pero no por la computadora cuántica en sí. .
Su procedimiento se basa en una función de "trampa", una que es fácil de ejecutar, pero difícil de revertir, a menos que tenga una clave criptográfica secreta. (En ese momento, los investigadores aún no sabían cómo hacer una trampa adecuada, esto vino más tarde). La función también debe tener la propiedad "dos en uno", lo que significa que para cada conjunto de datos de salida hay dos conjuntos diferentes de datos de entrada. Por ejemplo, podemos imaginar una función que cuadra los números: además del número 0, para cada resultado (por ejemplo, 9) hay dos números de entrada correspondientes (3 y -3).
Armado con una función similar, puede hacer que una computadora cuántica entre en un estado secreto de la siguiente manera. Primero, le pide a la computadora la tarea de construir una superposición de todos los datos de entrada posibles de la función (esto puede parecer una tarea difícil para la computadora, pero de hecho es simple). Luego le dice a la computadora que aplique la función a esta superposición gigantesca, creando un nuevo estado que es una superposición de toda la salida posible de la función. Las superposiciones de entrada y salida se confundirán, lo que significa que medir una de ellas afectará instantáneamente a la otra.
Luego le ordena a la computadora que mida el estado final e informe el resultado. Una medición contrae el estado en uno de los posibles conjuntos de datos de salida, y el estado de entrada se contrae para corresponder a él, porque están confundidos; por ejemplo, si usamos la función cuadrada, si el estado de salida es 9, entonces la entrada colapsará a la superposición 3 y -3.
Pero recuerde que usamos una función de trampa. Tenemos una clave secreta para la trampa, por lo que podemos encontrar fácilmente los dos estados que componen la superposición de entrada. Una computadora cuántica no puede. Y no puede simplemente medir la superposición de entrada para averiguar en qué consiste, ya que dicha medición la colapsará aún más, dejando a la computadora una de dos opciones, sin la capacidad de calcular la otra.
En 2017, Mahadev entendió cómo crear las funciones de trampa en las que se basa el método de estado secreto utilizando la criptografía llamada
Aprendizaje con errores (LWE). Utilizando estas funciones de trampa, pudo crear una versión cuántica de la computación "ciega", con la cual los usuarios de los sistemas de computación en la nube pueden ocultar sus datos para que las computadoras en la nube no puedan leerlos, incluso si realizan cálculos con ellos. Poco después, Mahadev, Wazirani y Cristiano se asociaron con Vidik y
Zwika Brackerski (del Instituto Weizmann en Israel) para mejorar aún más la calidad de estas funciones y utilizar el método de estado secreto para desarrollar una forma garantizada de que una computadora cuántica pueda generar
números probables al azar .
Mahadev podría haber obtenido el título sobre la base de tales resultados, pero tenía la intención de seguir trabajando hasta que resolviera el problema de confirmación. "Nunca pensé en un lanzamiento porque mi objetivo no era un lanzamiento en absoluto", dijo.
A veces, la incertidumbre en la capacidad de resolver este problema la presionó. Pero, dijo, "pasé tiempo aprendiendo cosas que me interesan, por lo que este pasatiempo no se puede llamar un desperdicio".
Tallado en piedra
Mahadev intentó usar diferentes enfoques del método de estado secreto para organizar un protocolo de confirmación, pero durante algún tiempo esto no condujo a nada. Y entonces se le ocurrió una idea: los investigadores ya habían demostrado que el probador puede verificar una computadora cuántica si tiene la capacidad de medir bits cuánticos. Por definición, el verificador clásico no tiene esa oportunidad. Pero, ¿qué pasaría si un probador clásico pudiera de alguna manera hacer que una computadora cuántica tome medidas por sí mismo y honestamente informe sus resultados?
La dificultad será cómo Mahadev entendió que la computadora cuántica promete realizar cualquier medida específica antes de descubrir qué medida le pedirá el inspector; de lo contrario, será muy simple que la computadora lo engañe. Aquí es donde entra en juego el método del estado secreto. El protocolo Mahadev requiere una computadora cuántica para crear primero un estado secreto y luego confundirlo con el estado que debe medir. Y solo entonces la computadora sabe qué medidas deben realizarse.
Como la computadora no conoce los detalles internos del estado secreto conocido por el inspector, Mahadev demostró que la computadora cuántica no podía hacer trampa de ninguna manera, sin dejar ninguna duda al respecto. De hecho, escribió Vidik, los qubits que una computadora necesita medir están "tallados en una piedra criptográfica". Por lo tanto, si los resultados de la medición parecen ser la prueba correcta, entonces el inspector puede estar seguro de que lo es.
“¡Esta es una idea tan maravillosa! - escribió Vidik. "Ella me golpea cada vez que Urmila la explica".
El protocolo de confirmación de Mahadev, junto con un generador de números aleatorios y cifrado ciego, depende de la suposición de que las computadoras cuánticas no pueden descifrar LWE. Hasta ahora, LWE es ampliamente considerado como el principal candidato para la criptografía post-cuántica, y pronto el Instituto Nacional de Estándares y Tecnología puede aprobarlo como un nuevo estándar criptográfico, para reemplazar aquellos que son propensos a fracturarse con una computadora cuántica. Pero esto no garantiza que sea realmente seguro contra las computadoras cuánticas, advirtió Gottsman. "Pero hasta ahora todo está claro", dice. "Nadie ha encontrado evidencia de la posibilidad de romperlo".
En cualquier caso, la confianza del protocolo en la LWE hace que Mahadev sea un trabajo ganador en cualquier caso, escribió Vidik. La única forma en que una computadora cuántica puede engañar al protocolo es si alguien del mundo de la computación cuántica se le ocurre cómo descifrar LWE, lo que en sí mismo será un logro notable.
Es poco probable que el protocolo Mahadev se implemente en una computadora cuántica real en el futuro previsible. Hasta ahora, necesita demasiada potencia informática desde un punto de vista práctico. Pero en el futuro esto puede cambiar a medida que crecen las computadoras cuánticas, y los investigadores simplifican este protocolo.
Es improbable que el protocolo aparezca dentro de, por ejemplo, los próximos cinco años, pero "no es una ciencia ficción", dijo Aaronson. "Ya será posible comenzar a pensar en este tema si todo sale como debería, en la próxima etapa de desarrollo de las computadoras cuánticas".
Y, dada la rapidez con que se desarrolla esta área, esta etapa puede comenzar antes de lo esperado. Después de todo, hace solo cinco años, dijo Vidik, los investigadores creían que hasta que las computadoras cuánticas no pudieran resolver ningún problema del que las computadoras clásicas no son capaces, pasarían muchos años más. "Y ahora", dijo, "la gente cree que esto sucederá en un año o dos".
Makhadev, habiendo resuelto su problema favorito, permaneció en un estado algo confuso. Mahadev dice que le gustaría entender qué es lo que hace que este problema sea tan adecuado para ella. « - , ». , , , , , , .
« , , — . – ».