La complejidad cuántica es ineludible. Cuatro investigadores —Mark Zhandry, John Bostanci, Jonas Haferkamp y Chinmay Nirkhe— han demostrado, mediante un elaborado tour de force matemático, que ciertos problemas requieren obligatoriamente pruebas (o testigos) cuánticos. El trabajo, galardonado con el premio al mejor artículo en el congreso STOC 2026 y recogido por Quanta Magazine, resuelve una cuestión abierta de la teoría de la complejidad que llevaba más de dos décadas sin respuesta.
El quid de la cuestión es si una computadora cuántica podría verificar una solución con un «certificado» clásico —un documento, un procedimiento— en lugar de un estado cuántico complejo. Hasta ahora, se sospechaba que no, pero demostrarlo de forma rigurosa era endiabladamente difícil. Los investigadores han dado con un problema, la forrelación espectral, cuyo único certificado válido es cuántico. Cualquier intento clásico conduce a una contradicción.
El problema de las sombras cuánticas
Imaginen un objeto tridimensional iluminado desde dos ángulos distintos. Cada iluminación proyecta una sombra. El problema de la forrelación espectral consiste en, dadas dos sombras, decidir si proceden del mismo objeto. Sin pistas adicionales, incluso un ordenador cuántico lo encuentra difícil. Pero si se dispone de una copia del estado cuántico del objeto, la verificación es sencilla: ese estado es la prueba cuántica.
La clave está en la fragilidad del testigo. Medir un estado cuántico lo altera irreversiblemente. Una hipotética prueba clásica, en cambio, sería un procedimiento escrito que cualquiera podría ejecutar una y otra vez, generando copias frescas del estado cuántico. Mark Zhandry, experto en criptografía cuántica, intuyó que esa reutilización escondía una contradicción profunda.
El equipo demostró que si existiera una prueba clásica para el problema, cualquiera con acceso a ella podría usarla para adivinar las sombras con muy poca información, una tarea que se sabe imposible incluso con la ayuda del mejor ordenador clásico. Esa contradicción forzó la conclusión: la prueba clásica no puede existir. «Fue un año que dominó nuestras vidas —recuerda Bostanci—. Prácticamente no hicimos otra cosa».
Si una prueba clásica para el problema existiera, cualquiera podría adivinar las sombras con sólo un puñado de datos, una hazaña que la teoría prohíbe.
Un hito oracular que redefine los límites
Formalmente, el equipo ha demostrado una separación oracular entre las clases de complejidad QMA (problemas con prueba cuántica verificable por un ordenador cuántico) y QCMA (problemas con prueba clásica verificable cuánticamente). Aunque la demostración se apoya en ciertos supuestos (el oráculo), es el indicio más sólido jamás obtenido de que las pruebas cuánticas son intrínsecamente más poderosas que las clásicas.
La idea partió de la criptografía. Zhandry y su equipo explotaron la perturbación de la medida, un fenómeno que en los protocolos cuánticos de seguridad impide que un espía lea un mensaje sin ser detectado. Aquí sirvió para demostrar que un testigo clásico reutilizable genera copias que acaban por quebrar la imposibilidad de adivinar las sombras. El trabajo, de casi 100 páginas, combina ideas de la teoría del aprendizaje cuántico, la matemática de bosones y la propia criptografía.
El hallazgo no significa que los ordenadores cuánticos vayan a destronar a los clásicos mañana, pero sí traza una frontera fundamental. Incluso en un mundo donde los ordenadores cuánticos fuesen omnipresentes, ciertas verificaciones seguirían necesitando testigos cuánticos. La naturaleza cuántica de la información es, en ese sentido, ineludible.
Poco después de que el preprint viera la luz en noviembre de 2025, un estudiante del MIT, Andrew Huang, y su asesor Vinod Vaikuntanathan construyeron una segunda separación oracular basada en otro problema, confirmando la robustez del resultado. Con dos demostraciones independientes, la comunidad acepta ya que QMA y QCMA son genuinamente distintos.
«Es un resultado hermoso —declaró Anand Natarajan, teórico de la información cuántica del Instituto Tecnológico de Massachusetts (MIT)—. Aporta un montón de ideas frescas». La pregunta que ahora se abre es si, eliminando las asunciones oraculares, se podrá demostrar la separación sin apelar a ellas, un desafío que, admiten los autores, requeriría una revolución en la teoría de la complejidad.
🔬 Ficha del Descubrimiento
- Qué se ha descubierto: Una demostración de que las pruebas cuánticas son estrictamente más poderosas que las clásicas (separación oracular entre QMA y QCMA).
- Dónde: Ciberespacio (preprint en arXiv) y presentación en el congreso STOC 2026.
- Institución responsable: Equipo internacional liderado por Mark Zhandry (Stanford), John Bostanci (Simons Institute), Jonas Haferkamp (Ruhr-Universität Bochum) y Chinmay Nirkhe (Universidad de Washington).
- Cuándo: Publicado en noviembre de 2025; galardonado en junio de 2026.
- Impacto a futuro: Redefine los límites de lo que se puede verificar eficientemente con ordenadores cuánticos y consolida la necesidad de testigos cuánticos en criptografía y teoría de la computación.
