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 (Ruhr University Bochum), Chinmay Nirkhe (University of Washington) y Mark Zhandry (Stanford), ha demostrado que las pruebas cuánticas son categóricamente más potentes 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 más importante en ciencias de la computación teórica.
“Este es un resultado hermoso”, dijo Anand Natarajan, un teórico de la información cuántica del MIT que no participó en el trabajo. “Hay un montón de ideas frescas y nuevas que surgen de esto”.
Lo que realmente muestra 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 el problema crece. En su centro están las clases QMA (Quantum Merlin-Arthur) y QCMA (Quantum-Classical Merlin-Arthur).
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 potente.
El equipo demostró que sí, construyendo un problema llamado el 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 la relación entre los dos conjuntos de datos directamente; 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 mostraron 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 reunieron, 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 usando 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 consejos cuánticos.
Tener dos pruebas independientes, una que es 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 en relación con 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 un oráculo, requeriría avances revolucionarios en teoría de la complejidad, equivalente 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 las 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 en relación con 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 potentes”, señalan los investigadores en su artículo.
Por qué es importante
Para el físico especializado en computación cuántica, este resultado podría no cambiar las operaciones diarias. 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 principales preguntas abiertas en la teoría de la complejidad cuántica, un campo que plantea preguntas fundamentales sobre qué se puede y qué no se puede calcular con recursos cuánticos. Para los investigadores que han pasado dos décadas trabajando en el problema QMA vs QCMA, la respuesta finalmente ha llegado.
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).