Hace mas de 30 anos, los investigadores descubrieron que computadores hipoteticos basados en las leyes de la fisica cuantica podrian resolver rapidamente problemas matematicos dificiles. Desde entonces, han buscado identificar los casos en que un computador cuantico es mas poderoso que sus primos "clasicos" ordinarios.
Casi desde el mismo tiempo, un pequeno grupo de cientificos de la computacion persigue una pregunta relacionada que recibe menos atencion: las pruebas que explotan la fisica cuantica, son tambien mas poderosas que las clasicas?
En este contexto, una "prueba" no es una serie de enunciados logicos que llevan a un teorema, como en matematicas. Es, mas bien, un certificado que confirma que un problema se resolvio correctamente. Por ejemplo, si resuelves un sudoku dificil, tu propia solucion es una prueba: un computador puede recorrer la grilla y verificar que es correcta.
Los investigadores han identificado problemas en los que ese proceso de verificacion probablemente requiere un computador cuantico. Para algunos, las pruebas siguen siendo clasicas, documentos escritos ordinarios. Pero para otros, las unicas pruebas conocidas son objetos matematicos fundamentalmente distintos, llamados estados cuanticos.
Por que no basta una prueba clasica
Los investigadores quieren entender si esas pruebas cuanticas exoticas son realmente necesarias. En los casos donde un problema parece exigir una prueba cuantica, es de verdad imposible dar con una prueba clasica ordinaria? O existe alguna forma ingeniosa de reemplazarla que simplemente no se ha descubierto?
Por mas de 20 anos, esta pregunta ha figurado entre los mayores problemas abiertos de la teoria de complejidad cuantica, que estudia la dificultad intrinseca de los problemas cuanticos. Ahora, en un paper de 100 paginas que recibio el premio al mejor trabajo en el Simposio de Teoria de la Computacion 2026 en junio, cuatro investigadores finalmente la resolvieron, o al menos se acercaron tanto a una respuesta completa como nadie espera lograr. Identificaron un problema computacional especial que de verdad requiere una prueba cuantica. Ninguna prueba clasica sirve.
"Es un resultado hermoso", dijo Anand Natarajan, teorico de la informacion cuantica del Instituto Tecnologico de Massachusetts. "Salen de el un monton de ideas frescas y nuevas."
Que es exactamente una prueba cuantica
Supongamos que quieres demostrar que un material tiene cierta propiedad, digamos que es magnetico. Es un problema dificil salvo que tengas acceso al estado cuantico del material: un objeto matematico que especifica la configuracion de sus electrones. Con una copia de ese estado, un computador cuantico puede verificar facilmente que el material es magnetico. Es decir, el estado cuantico del material puede servir como prueba cuantica para ese problema.
El inconveniente es que los estados cuanticos pueden ser extraordinariamente complicados, por un fenomeno llamado superposicion, en el que muchas configuraciones distintas de un sistema coexisten en un solo estado. Incluso en un sistema relativamente simple, el numero de configuraciones posibles que contribuyen a una superposicion cuantica puede superar la cantidad de atomos en el universo, lo que hace imposible escribir una descripcion clasica del estado.
Para confirmar esta intuicion, los teoricos necesitaban hallar un problema que cumpliera dos condiciones: primero, tener una prueba cuantica; segundo, no tener una prueba clasica. Esa segunda parte es la dificil, y se complica aun mas porque los problemas con pruebas clasicas podrian usar de todos modos computadores cuanticos en su verificacion. Para lograrlo, hay que descartar cada combinacion posible de prueba clasica y algoritmo cuantico de verificacion.
Es notoriamente dificil demostrar afirmaciones que apliquen a todos los algoritmos. En 2006 se logro un avance parcial, pero no la meta ultima: una forma especialmente codiciada de evidencia que evita hacer suposiciones inusuales.
"Eso parecia un problema mucho, mucho mas dificil", dijo Scott Aaronson, teorico de la complejidad de la Universidad de Texas en Austin, coautor del paper de 2006 junto al matematico Greg Kuperberg.
Como lo demostraron
La historia del nuevo resultado empezo con Mark Zhandry, investigador en criptografia cuantica. En 2024 comenzo a sospechar que una caracteristica de la fisica cuantica, central en muchos esquemas criptograficos, tambien podria ayudar a distinguir las pruebas cuanticas de las clasicas.
"Fue medio por accidente que empece a pensar en esto", dijo Zhandry, hoy en la Universidad de Stanford.
Para poner a prueba su idea, Zhandry necesitaba un candidato a problema con prueba cuantica pero sin prueba clasica. El que eligio, llamado problema de forrelacion espectral, consiste en comparar dos formas distintas de medir un estado cuantico. Zhandry y sus colegas comparan los posibles resultados de esas dos mediciones con las sombras que proyecta un objeto iluminado desde dos angulos diferentes. Te dan un par de sombras y tu objetivo es determinar si de verdad pudieron provenir de mediciones distintas del mismo estado.
"Es un problema forense", dijo Chinmay Nirkhe, cientifico de la computacion de la Universidad de Washington que colaboro con Zhandry. "Existe acaso un objeto que pudiera haber proyectado ambas sombras?"
Sin informacion extra, ese problema es dificil incluso para un computador cuantico. Pero con el estado cuantico apropiado, un computador cuantico puede confirmar facilmente que es consistente con ambas sombras. Ese estado es, entonces, una prueba cuantica valida.
Zhandry necesitaba mostrar que las pruebas clasicas no pueden existir, y lo intento con una estrategia de demostracion por contradiccion. Primero asumiria lo contrario de lo que queria probar: que si es posible una prueba clasica. Luego mostraria que esa suposicion termina llevando a una contradiccion. Esa contradiccion, sospechaba, vendria de una propiedad de las pruebas clasicas que damos por sentada: se pueden leer mas de una vez.
Fuera de las peliculas de espias, los documentos rara vez se autodestruyen tras leerse, y las pruebas no son la excepcion. Pero en el mundo cuantico las cosas son distintas: medir un estado cuantico puede perturbarlo de forma irreversible, alterando los resultados de cualquier medicion posterior. Esa perturbacion por medicion es central en muchos esquemas de criptografia cuantica, pero no se habia aprovechado en los intentos previos por separar pruebas cuanticas de clasicas.
Zhandry mostro rapidamente que, si existiera una prueba clasica para el problema de forrelacion espectral, cualquiera con una copia podria usarla una y otra vez para lograr una tarea aparentemente dificil: adivinar la forma de las sombras a partir de informacion parcial. Solo faltaba un paso. Si lograba probar que esa tarea de adivinanza era tan dificil que ni siquiera una prueba clasica ayudaba, tendria su contradiccion, y su suposicion inicial seria falsa.
No pudo cerrar solo ese ultimo paso, asi que a fines de 2024 se unio con John Bostanci, hoy en el Simons Institute de Berkeley, y Jonas Haferkamp, de la Universidad del Ruhr en Bochum, Alemania. Pronto el trio creyo tener una demostracion terminada, pero el paso final resulto tener una falla fatal. Quedar tan cerca los dejo aun mas determinados.
Nirkhe, que venia peleando con el problema por su cuenta desde hacia anos, se sumo a comienzos de 2025 y propuso ajustar el enfoque de Zhandry. Podian usar la misma estrategia general, pero casi cada detalle tendria que cambiar. La propuesta abrio nueve meses de correos interminables y viajes entre Nueva York, el estado de Washington, California y Alemania.
"Realmente domino mi ano", dijo Bostanci. "Basicamente no hice mucho mas."
Los cuatro fueron desgastando el problema apoyandose en ideas de otras areas de la fisica y la computacion, incluida la teoria del aprendizaje cuantico y la matematica de los bosones. Un avance crucial llego a comienzos del otono, mientras Bostanci corria 32 kilometros por el Central Park de Nueva York, como parte de su entrenamiento para una maraton.
