Durante veinte años, los científicos de la computación han lidiado con una pregunta engañosamente simple: ¿puede una computadora cuántica verificar soluciones a problemas que una computadora clásica ni siquiera puede describir?
La respuesta, resulta, es sí, y la prueba tiene 96 páginas.
Un equipo de cuatro investigadores, John Bostanci (Simons Institute / Columbia), Jonas Haferkamp (Universidad del Ruhr en Bochum), Chinmay Nirkhe (Universidad de Washington) y Mark Zhandry (Stanford), ha demostrado que las pruebas cuánticas son categóricamente más poderosas que las pruebas clásicas para al menos un problema computacional. El artículo ganó el premio al mejor artículo en STOC 2026, la conferencia principal en ciencias de la computación teórica.
“Este es un resultado hermoso”, dijo Anand Natarajan, teórico de la información cuántica del MIT que no participó en el trabajo. “Surgen muchas ideas frescas y nuevas”.
Lo que realmente demuestra la prueba
El problema pertenece a una rama de las ciencias de la computación teórica llamada teoría de la complejidad, que estudia cómo escalan los recursos necesarios para resolver un problema a medida que este crece. En su centro están las clases QMA (Merlin-Arthur Cuántico) y QCMA (Merlin-Arthur Clásico-Cuántico).
Piénselo de esta manera: imagine a un estudiante (Merlin) tratando de convencer a un profesor (Arthur) de que una determinada afirmación matemática es verdadera. En el escenario QMA, Merlin puede presentar un estado cuántico, una colección frágil de qubits, como evidencia. En el escenario QCMA, Merlin solo puede presentar una cadena clásica de bits. La pregunta, planteada por primera vez por Dorit Aharonov y Tomer Naveh en 2002, era si la versión cuántica es estrictamente más poderosa.
El equipo demostró que lo es, construyendo un problema llamado problema de forrelación espectral para el cual un testigo cuántico funciona pero uno clásico no. El problema es una especie de rompecabezas forense: dados dos conjuntos de datos de medición, determinar si provienen del mismo objeto cuántico subyacente o de dos objetos diferentes. Un testigo cuántico puede codificar directamente la relación entre los dos conjuntos de datos; un testigo clásico simplemente no puede transportar suficiente información.
La prueba utiliza una estrategia llamada “prueba por contradicción”. Los investigadores primero asumieron que existía una prueba clásica para el problema. Luego demostraron que dicha prueba sería reutilizable, se podría usar el mismo testigo clásico para responder muchas consultas diferentes. Pero esta reutilización, demostraron, permitiría resolver una tarea de adivinación difícil que es demostrablemente imposible. La contradicción significa que la suposición original era falsa: no puede existir ninguna prueba clásica.
“Fue un poco por accidente que empecé a pensar en esto”, dijo Zhandry a Quanta Magazine. Su trabajo en solitario en noviembre de 2024 resolvió la mitad del problema pero no pudo terminarlo. Los cuatro se unieron y, después de nueve meses de trabajo intenso, “Realmente dominó mi año. Básicamente no hice mucho más”, dijo Bostanci, produjeron la prueba completa.
Una segunda prueba independiente
Notablemente, un segundo equipo llegó independientemente a la misma conclusión utilizando un método completamente diferente. Andrew Huang y Vinod Vaikuntanathan del MIT, junto con Bostanci, produjeron una segunda separación de oráculo en febrero de 2026 (arXiv:2602.09385) que es conceptualmente más simple y también produce la primera separación entre las clases BQP/qpoly y BQP/poly, un área relacionada sobre el asesoramiento cuántico.
Tener dos pruebas independientes, una ingeniosa pero intrincada y la otra más simple y extensible, fortalece la solidez del resultado.
La advertencia del oráculo
Ambas pruebas son “separaciones de oráculo”: muestran que QMA y QCMA difieren con respecto a una función de caja negra (un oráculo) que la computadora puede consultar pero cuyo funcionamiento interno no puede ver. Una prueba incondicional, sin oráculo, requeriría avances revolucionarios en la teoría de la complejidad, equivalentes a demostrar que P no es igual a PSPACE.
No obstante, las separaciones de oráculo se consideran evidencia muy sólida. Cada separación conocida entre clases de complejidad principales comenzó como un resultado de oráculo antes de ser refinada. La historia del campo muestra que cuando dos clases difieren con respecto a un oráculo, casi siempre difieren en la realidad.
“Lo que tenemos es la evidencia más sólida hasta la fecha de que la respuesta es sí, las pruebas cuánticas son más poderosas”, señalan los investigadores en su artículo.
Por qué es importante
Para el físico especializado en computación cuántica, este resultado puede no cambiar las operaciones cotidianas. El problema que separa las dos clases, el problema de forrelación espectral, está cuidadosamente construido y es artificial. Pero las técnicas desarrolladas en la prueba, particularmente los métodos de oráculo comprimido de “segunda cuantización” que tratan el problema en términos de bosones, se espera que encuentren aplicaciones en criptografía y diseño de algoritmos cuánticos.
El resultado también cierra una de las preguntas abiertas más importantes en la teoría de la complejidad cuántica, un campo que plantea preguntas fundamentales sobre qué se puede y qué no se puede computar con recursos cuánticos. Para los investigadores que han pasado dos décadas trabajando en el problema QMA vs QCMA, la respuesta finalmente está aquí.
Traducido por Alessandra
Fuentes
- Quanta Magazine: “Researchers Reveal the Power of ‘Quantum Proofs'” (6 de julio de 2026). https://www.quantamagazine.org/researchers-reveal-the-power-of-quantum-proofs-20260706/
- Bostanci, J., Haferkamp, J., Nirkhe, C., Zhandry, M. “Separating QMA from QCMA with a Classical Oracle.” arXiv:2511.09551. STOC 2026 Best Paper.
- Bostanci, J., Huang, A., Vaikuntanathan, V. “Separating Quantum and Classical Advice with Good Codes.” arXiv:2602.09385 (febrero de 2026).