Hace más de 30 años, los investigadores descubrieron que computadores hipotéticos basados en las leyes de la física cuántica podrían resolver rápidamente problemas matemáticos difíciles. Desde entonces, han buscado identificar los casos en que un computador cuántico es más poderoso que sus primos "clásicos" ordinarios.
Casi desde el mismo tiempo, un pequeño grupo de científicos de la computación persigue una pregunta relacionada que recibe menos atención: las pruebas que explotan la física cuántica, ¿son también más poderosas que las clásicas?
En este contexto, una "prueba" no es una serie de enunciados lógicos que llevan a un teorema, como en matemáticas. Es, más bien, un certificado que confirma que un problema se resolvió correctamente. Por ejemplo, si resuelves un sudoku difícil, tu propia solución 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 verificación probablemente requiere un computador cuántico. Para algunos, las pruebas siguen siendo clásicas, documentos escritos ordinarios. Pero para otros, las únicas pruebas conocidas son objetos matemáticos fundamentalmente distintos, llamados estados cuánticos.
Por qué no basta una prueba clásica
Los investigadores quieren entender si esas pruebas cuánticas exóticas son realmente necesarias. En los casos donde un problema parece exigir una prueba cuántica, ¿es de verdad imposible dar con una prueba clásica ordinaria? ¿O existe alguna forma ingeniosa de reemplazarla que simplemente no se ha descubierto?
Por más de 20 años, esta pregunta ha figurado entre los mayores problemas abiertos de la teoría de complejidad cuántica, que estudia la dificultad intrínseca de los problemas cuánticos. Ahora, en un paper de 100 páginas que recibió el premio al mejor trabajo en el Simposio de Teoría de la Computación 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 cuántica. Ninguna prueba clásica sirve.
"Es un resultado hermoso", dijo Anand Natarajan, teórico de la información cuántica del Instituto Tecnológico de Massachusetts. "Salen de él un montón de ideas frescas y nuevas."
Qué es exactamente una prueba cuántica
Supongamos que quieres demostrar que un material tiene cierta propiedad, digamos que es magnético. Es un problema difícil salvo que tengas acceso al estado cuántico del material: un objeto matemático que especifica la configuración de sus electrones. Con una copia de ese estado, un computador cuántico puede verificar fácilmente que el material es magnético. Es decir, el estado cuántico del material puede servir como prueba cuántica para ese problema.
El inconveniente es que los estados cuánticos pueden ser extraordinariamente complicados, por un fenómeno llamado superposición, en el que muchas configuraciones distintas de un sistema coexisten en un solo estado. Incluso en un sistema relativamente simple, el número de configuraciones posibles que contribuyen a una superposición cuántica puede superar la cantidad de átomos en el universo, lo que hace imposible escribir una descripción clásica del estado.
Para confirmar esta intuición, los teóricos necesitaban hallar un problema que cumpliera dos condiciones: primero, tener una prueba cuántica; segundo, no tener una prueba clásica. Esa segunda parte es la difícil, y se complica aún más porque los problemas con pruebas clásicas podrían usar de todos modos computadores cuánticos en su verificación. Para lograrlo, hay que descartar cada combinación posible de prueba clásica y algoritmo cuántico de verificación.
Es notoriamente difícil demostrar afirmaciones que apliquen a todos los algoritmos. En 2006 se logró un avance parcial, pero no la meta última: una forma especialmente codiciada de evidencia que evita hacer suposiciones inusuales.
"Eso parecía un problema mucho, mucho más difícil", dijo Scott Aaronson, teórico de la complejidad de la Universidad de Texas en Austin, coautor del paper de 2006 junto al matemático Greg Kuperberg.
Cómo lo demostraron
La historia del nuevo resultado empezó con Mark Zhandry, investigador en criptografía cuántica. En 2024 comenzó a sospechar que una característica de la física cuántica, central en muchos esquemas criptográficos, también podría ayudar a distinguir las pruebas cuánticas de las clásicas.
"Fue medio por accidente que empecé 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 cuántica pero sin prueba clásica. El que eligió, llamado problema de forrelación espectral, consiste en comparar dos formas distintas de medir un estado cuántico. Zhandry y sus colegas comparan los posibles resultados de esas dos mediciones con las sombras que proyecta un objeto iluminado desde dos ángulos 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, científico de la computación de la Universidad de Washington que colaboró con Zhandry. "¿Existe acaso un objeto que pudiera haber proyectado ambas sombras?"
Sin información extra, ese problema es difícil incluso para un computador cuántico. Pero con el estado cuántico apropiado, un computador cuántico puede confirmar fácilmente que es consistente con ambas sombras. Ese estado es, entonces, una prueba cuántica válida.
Zhandry necesitaba mostrar que las pruebas clásicas no pueden existir, y lo intentó con una estrategia de demostración por contradicción. Primero asumiría lo contrario de lo que quería probar: que sí es posible una prueba clásica. Luego mostraría que esa suposición termina llevando a una contradicción. Esa contradicción, sospechaba, vendría de una propiedad de las pruebas clásicas que damos por sentada: se pueden leer más de una vez.
Fuera de las películas de espías, los documentos rara vez se autodestruyen tras leerse, y las pruebas no son la excepción. Pero en el mundo cuántico las cosas son distintas: medir un estado cuántico puede perturbarlo de forma irreversible, alterando los resultados de cualquier medición posterior. Esa perturbación por medición es central en muchos esquemas de criptografía cuántica, pero no se había aprovechado en los intentos previos por separar pruebas cuánticas de clásicas.
Zhandry mostró rápidamente que, si existiera una prueba clásica para el problema de forrelación espectral, cualquiera con una copia podría usarla una y otra vez para lograr una tarea aparentemente difícil: adivinar la forma de las sombras a partir de información parcial. Solo faltaba un paso. Si lograba probar que esa tarea de adivinanza era tan difícil que ni siquiera una prueba clásica ayudaba, tendría su contradicción, y su suposición inicial sería falsa.
No pudo cerrar solo ese último paso, así que a fines de 2024 se unió con John Bostanci, hoy en el Simons Institute de Berkeley, y Jonas Haferkamp, de la Universidad del Ruhr en Bochum, Alemania. Pronto el trío creyó tener una demostración terminada, pero el paso final resultó tener una falla fatal. Quedar tan cerca los dejó aún más determinados.
Nirkhe, que venía peleando con el problema por su cuenta desde hacía años, se sumó a comienzos de 2025 y propuso ajustar el enfoque de Zhandry. Podían usar la misma estrategia general, pero casi cada detalle tendría que cambiar. La propuesta abrió nueve meses de correos interminables y viajes entre Nueva York, el estado de Washington, California y Alemania.
"Realmente dominó mi año", dijo Bostanci. "Básicamente no hice mucho más."
Los cuatro fueron desgastando el problema apoyándose en ideas de otras áreas de la física y la computación, incluida la teoría del aprendizaje cuántico y la matemática de los bosones. Un avance crucial llegó a comienzos del otoño, mientras Bostanci corría 32 kilómetros por el Central Park de Nueva York, como parte de su entrenamiento para una maratón.
