Imagina que visitas un laberinto con unos amigos. Emerges de la salida poco después de entrar y esperas durante horas antes de que salgan tus amigos. Naturalmente, preguntan sobre el camino que tomaste; seguramente puedes volver sobre tus pasos y mostrarles el camino, ¿verdad?

No así en un mundo regido por las extrañas leyes de la física cuántica. Hace veinte años, los investigadores de computación cuántica desarrollaron un algoritmo que aprovechó esas leyes para atravesar un tipo específico de laberinto matemático mucho más rápido que cualquier algoritmo que se ejecuta en una computadora clásica ordinaria. Pero esa aceleración tiene un costo: el algoritmo cuántico rápido encuentra la salida pero no tiene idea de cómo llegó allí.

Los investigadores se han preguntado durante mucho tiempo si esta compensación es inevitable. ¿Es realmente imposible encontrar la salida rápidamente sin olvidar el camino?

"Es un poco alucinante que incluso necesites hacer esta pregunta", dijo Mateo Coudron, científico informático del Instituto Nacional de Estándares y Tecnología en Gaithersburg, Maryland.

En noviembre pasado, Coudron y dos colegas dieron un gran paso para resolver ese problema de larga data: Ellos demostrado que ningún algoritmo en una clase amplia y natural de algoritmos cuánticos rápidos puede encontrar un camino a través de ese laberinto especial, llamado gráfico de árbol soldado. Los resultados muestran que cualquier algoritmo hipotético de búsqueda de rutas que no adivine a ciegas tendría que perder temporalmente el rastro de la entrada para tener alguna posibilidad de éxito. Parece que el olvido es inevitable.

"No hay forma de que hubiera adivinado que en realidad podrían probar eso", dijo Simón Apers, un investigador de computación cuántica del Centro Nacional de Investigación Científica del Instituto de Investigación de Fundamentos de Ciencias de la Computación en París, y agregó que el resultado "es muy útil para ilustrar lo que los algoritmos cuánticos pueden y no pueden hacer".

El impulso cuántico

Las computadoras cuánticas deben su poder en parte a un fenómeno conocido como superposición, que les permite explorar simultáneamente muchas opciones que una computadora clásica necesitaría considerar individualmente. Pero es no tan simple como realizar varios cálculos a la vez para ahorrar tiempo. Verificar el resultado de una superposición de opciones nunca revela una superposición de resultados; más bien, solo obtienes uno de los posibles resultados, cada uno de los cuales tiene una probabilidad diferente. Los algoritmos cuánticos se basan en el hecho de que las contribuciones a estas probabilidades pueden interferir entre sí como las ondas en la superficie de un estanque, lo que aumenta la probabilidad de obtener la respuesta correcta y reduce la probabilidad de cualquier otro resultado.

Debido a que la interferencia tiene que funcionar correctamente, no todas las tareas computacionales son susceptibles de una aceleración cuántica y, de hecho, los investigadores están todavía trabajando donde los algoritmos cuánticos pueden ayudar, décadas después de que se propusiera por primera vez la computación cuántica. Pero han tenido algunos éxitos notables. En 1994, Peter Shor desarrolló un algoritmo cuántico para factorizar números grandes, una tarea cuya aparente dificultad para las computadoras clásicas subyace en gran parte de la criptografía moderna. El algoritmo de Shor podía factorizar rápidamente números tan grandes que todos los algoritmos clásicos conocidos serían prácticamente inútiles.

En 1996, el informático Lov Grover encontró un segundo ejemplo potencialmente práctico: un algoritmo cuántico para un problema de búsqueda muy genérico, similar a encontrar un solo elemento escondido dentro de una de muchas cajas idénticas.

“Clásicamente, lo que podrías hacer es simplemente probar uno al azar y ver si es bueno, y luego intentarlo de nuevo y ver si es bueno, y sigues intentándolo hasta que encuentres un buen elemento”, dijo Apers. Este enfoque lleva un tiempo proporcional al número de cajas. Multiplique ese número por 100 y la búsqueda será 100 veces más lenta.

Con un algoritmo cuántico, puedes hacerlo mejor. Grover demostró que si configura una superposición de todas las casillas, puede explotar la interferencia para garantizar prácticamente que el algoritmo seleccionará la casilla correcta al final. Todo el proceso lleva un tiempo proporcional a la raíz cuadrada del número de cajas: aumentar ese número por un factor de 100 solo aumenta el tiempo de ejecución por un factor de 10.

El algoritmo de Grover fue una ilustración notablemente simple del valor de la superposición cuántica, pero la aceleración que logró fue relativamente modesta: las tareas que estaban mucho más allá del alcance de los mejores algoritmos clásicos también dejarían perplejo al algoritmo de Grover. El algoritmo de factorización de Shor había ofrecido un vistazo de un abismo dramático entre las capacidades de las computadoras cuánticas y clásicas. ¿Había una variante del problema de búsqueda de Grover que fuera como la factorización, prácticamente intratable para las computadoras clásicas pero fácil para las computadoras cuánticas?

A fines de la década de 1990, los investigadores comenzaron a explorar esta pregunta reformulándola como una pregunta sobre gráficos: redes de puntos o nodos conectados por líneas, llamados bordes. Cualquier problema de búsqueda se puede enmarcar en el lenguaje de la teoría de grafos, con un nodo que representa el punto de partida, otro nodo que representa el destino y los bordes que representan las posibles opciones en cada paso del camino.

El problema de Grover, por ejemplo, corresponde a buscar un gráfico en el que cada nodo está conectado a todos los demás nodos (porque puedes abrir cajas en cualquier orden). Diferentes algoritmos clásicos para un problema de búsqueda dado equivalen a diferentes estrategias para explorar el gráfico correspondiente un nodo a la vez, mientras que los algoritmos cuánticos pueden moverse a lo largo de múltiples bordes en superposición.

Ramificación hacia fuera

En 2002, un equipo de informáticos finalmente no haber aun identificado una solucion para el problema un problema de búsqueda clásicamente intratable que un algoritmo cuántico podría resolver fácilmente. Comenzaron con un gráfico simple llamado árbol, en el que de cada nodo brotan dos aristas que conducen a dos nodos más, cada uno de los cuales se divide en dos ramas más, y así sucesivamente. A partir de un solo nodo "raíz", un gráfico de árbol se ramifica muchas veces antes de terminar en una capa final de nodos llamados "hojas". El equipo imaginó tomar dos árboles idénticos y "soldarlos" colocándolos con las hojas una frente a la otra y luego usar un proceso aleatorio para conectar cada hoja de un árbol con dos hojas del otro. Luego plantearon la siguiente pregunta: Comenzando en una raíz del gráfico de árbol soldado, ¿puedes encontrar el camino hacia la otra?

Sin una vista de pájaro del gráfico, cualquier algoritmo clásico que intente resolver este problema de búsqueda se perderá irremediablemente después de llegar a las capas intermedias del gráfico: todos los bordes se ven idénticos y no hay forma de distinguir los que apuntan hacia adelante de los que apuntan hacia atrás. Un algoritmo puede tropezar con el nodo de salida accidentalmente, pero el tiempo promedio que pasa deambulando crece exponencialmente con la cantidad de capas en el árbol.

Los autores del artículo de 2002 demostraron que un algoritmo cuántico simple, una "caminata cuántica" que se extiende a través del gráfico de manera uniforme al tomar muchos caminos en superposición, puede encontrar su camino hacia la salida mucho más rápido. Esto se debe a que el diseño simétrico del gráfico de árbol soldado conduce a una interferencia entre las rutas que concentra el flujo en la dirección de avance. El nodo de salida es "como un punto de enfoque del algoritmo", dijo Alejandro Belov, informático de la Universidad de Letonia.

Hay una buena posibilidad de que este algoritmo de caminata cuántica converja en la salida en el tiempo que es meramente proporcional al número de capas. Eso lo hace exponencialmente más rápido que cualquier algoritmo clásico, una aceleración comparable a la del algoritmo de factorización de Shor. Pero la interferencia que provoca la aceleración cuántica también borra todo registro de los caminos que recorre el algoritmo en su camino hacia la salida.

Los investigadores se preguntaron si había alguna forma de obtener lo mejor de ambos mundos: un algoritmo rápido que identifica un camino desde la entrada hasta la salida.

"Si es solo la caminata cuántica básica que de alguna manera encuentra la salida, eso no va a funcionar", dijo andres niño, científico informático de la Universidad de Maryland, College Park, coautor del artículo de 2002 como estudiante graduado y que trabajó con Coudron en el nuevo resultado. “Pero tal vez podrías mejorarlo de alguna manera”.

Sopandolo

Entre los primeros en abordar el problema estuvo ansis rosmanis, científico informático que ahora trabaja en la Escuela de Graduados en Matemáticas de la Universidad de Nagoya. En un artículo de 2010, Rosmanis desarrolló un clase de algoritmos que denominó "caminatas cuánticas de serpientes", que complementan el algoritmo estándar de caminata cuántica con un recuerdo de dónde han estado.

A medida que el algoritmo de caminata cuántica estándar fluye a través del gráfico, su próximo paso depende únicamente de dónde se encuentre actualmente; no importa cómo llegó allí. En los paseos de serpientes de Rosmanis, por el contrario, es necesario conocer el pasado para predecir el futuro. Específicamente, la evolución de la caminata de la serpiente está determinada por "serpientes", cadenas de nodos adyacentes por los que la caminata ha pasado previamente. Hay muchas variedades de caminatas de serpientes, que difieren, entre otros aspectos, en cómo cambia la longitud de esas serpientes en el transcurso de la caminata.

Rosmanis demostró que las caminatas cuánticas de serpientes usando superposiciones de múltiples serpientes aún podrían exhibir una interferencia útil, a pesar de recordar sus trayectorias, y que algunas caminatas de serpientes podrían, en principio, encontrar un camino hacia la salida. Pero no pudo encontrar un algoritmo de caminata de serpiente específico que lo hiciera tan rápido, y tampoco pudo probar que tal algoritmo no existiera. Los caminos de serpiente, al parecer, eran prometedores, pero demasiado resbaladizos para precisarlos. El trabajo de Rosmanis fue la última palabra sobre el problema de la búsqueda de caminos durante casi una década.

Luego, en 2019, Coudron encontró el gráfico de árbol soldado en un contexto diferente: él y un colega demostrado que todos los algoritmos de caminata cuántica que encuentran la salida carecen de una propiedad universal entre los algoritmos que se sabe que producen aceleraciones cuánticas exponenciales para otros problemas. El resultado no estaba directamente relacionado con la búsqueda de caminos, pero Coudron comenzó a sospechar que las técnicas matemáticas que le permitieron probar esta declaración radical sobre las propiedades de todos los algoritmos de gráficos de árboles soldados también podrían ayudar a resolver la cuestión de si las caminatas de serpientes (u otros algoritmos) podrían encontrar un camino. Después de mudarse a Maryland más tarde ese año, inició una colaboración con Childs, con la esperanza de resolver esa cuestión de manera decisiva.

Childs, Coudron y su estudiante de posgrado Amin Shiraz Gilani Comenzó haciendo dos supuestos para limitar el alcance del problema. Primero, decidieron ignorar los algoritmos extravagantes que intentarían teletransportarse a puntos aleatorios en el gráfico con la esperanza de tropezar con la salida. Esta estrategia es como tratar de ganarle a un videojuego buscando un problema técnico para explotar, técnicamente posible, tal vez, pero en contra del espíritu del problema. También es difícil imaginar que tal comportamiento podría ser útil, ya que las probabilidades de aterrizar en el lugar correcto se vuelven minúsculas en gráficos grandes. Ignorar los algoritmos que saltaban al azar facilitó el análisis de los algoritmos restantes, que los autores llamaron algoritmos "genuinos"; estos incluían los algoritmos de paso de serpiente de Rosmanis y quizás otros que nadie había descubierto aún.

La segunda suposición más importante de los autores fue que un algoritmo rápido de búsqueda de caminos permanecería "enraizado", es decir, construiría un camino hacia el nodo de salida sin perder nunca el rastro de la entrada. Muchos caminos de serpiente están enraizados, pero en principio es posible que un camino de serpiente no enraizado pueda encontrar un camino hacia la salida; tendría que separarse del nodo de entrada y luego encontrar tanto la entrada como la salida más adelante.

Los tres investigadores demostraron que para cada algoritmo cuántico enraizado genuino, podían crear un algoritmo clásico que imitaría su comportamiento observable. Dado que también pudieron demostrar que ningún algoritmo clásico podía encontrar la salida rápidamente, eso fue suficiente para descartar esta amplia clase de posibles algoritmos cuánticos de búsqueda de caminos. Los algoritmos enraizados genuinos simplemente no pueden generar suficiente interferencia para encontrar un camino a través del laberinto.

El camino hacia adelante

El nuevo resultado no es necesariamente el final de la historia. “Incluso después de estudiar los algoritmos cuánticos durante bastante tiempo, continúan sorprendiéndome”, shelby kimmel, un científico informático de Middlebury College, escribió en un correo electrónico. Todavía puede haber un ingenioso algoritmo de búsqueda de caminos fuera de la clase que consideraron los investigadores, esperando a ser descubierto.

Si bien los algoritmos que no son genuinos parecen muy poco probables de funcionar, un algoritmo no rooteado quizás podría construir un camino de entrada a salida comenzando desde algún punto intermedio. “Tal vez puedas configurarlo de tal manera que la serpiente entre y se desenraice, pero luego de alguna manera decida estirarse”, dijo Childs. “Eso aún no está descartado”.

Los investigadores aún tienen que encontrar aplicaciones prácticas para la aceleración cuántica exponencial que Childs y sus colegas descubrieron hace 20 años, en parte porque depende de la simetría especial del gráfico de árbol soldado, que es poco probable que exista en cualquier red del mundo real. Pero a menudo hay mucho valor en comprender lo que los algoritmos cuánticos no pueden hacer. El descubrimiento de Shor de un algoritmo cuántico rápido para factorizar números grandes, que amenaza con socavar criptografía de última generación, subrayó la necesidad de problemas que también son difíciles para los algoritmos cuánticos.

Un tipo de criptografía que no es vulnerable al algoritmo de Shor se basa en la suposición de que es difícil encontrar rutas entre puntos en gráficos específicos. La evidencia de que la búsqueda de rutas a través de árboles soldados es realmente difícil para los algoritmos cuánticos puede motivar a los investigadores a desarrollar nuevos protocolos criptográficos basados ​​en el gráfico del árbol soldado, aunque hasta ahora no han tenido suerte.

“Tal vez eso signifique que el tipo de estructura que hay en este problema simplemente no es adecuada para codificar los problemas que nos preocupan”, dijo Childs. “O tal vez solo tienes que verlo de la manera correcta”.