La IA demostró la conjetura de Aaronson-Ambainis: los computadores cuánticos están limitados en problemas sin estructura

Editado por: Svitlana Velhush

Un computador cuántico no podrá superar exponencialmente a uno clásico al resolver problemas donde los datos de entrada son casi aleatorios y carecen de una estructura matemática especial. No se trata de una limitación más: es una demostración obtenida por inteligencia artificial.

En noviembre de 2026, la startup Physical Superintelligence (PSI), con sede en EE. UU., anunció la demostración de una conjetura que en 2011 formularon Scott Aaronson, de la Universidad de Texas en Austin, y Andris Ambainis, de la Universidad de Letonia. La conjetura afirmaba que, para polinomios de bajo grado que toman valores entre 0 y 1 en el cubo booleano, siempre existe una variable con una influencia notable. La demostración la encontró el sistema de investigación interno de PSI basado en un modelo no público de Anthropic. El texto completo pasó la verificación en el sistema Lean, y la exposición la prepararon los investigadores de Stanford Guy Blanc, Jordan Docter, Carmen Strassle y Li-Yang Tan.

El sistema trabajó durante cuatro días: primero obtuvo una demostración completa, luego la mejoró dos veces, y Lean aceptó cada variante sin errores. No es un experimento en un procesador cuántico, sino una demostración puramente matemática en el ámbito de la teoría de la complejidad de consultas. Muestra que un algoritmo cuántico que realiza T consultas a la entrada puede simularse clásicamente con alta precisión en la mayoría de las entradas aleatorias, utilizando solo un número polinómico de consultas.

Imagínese un almacén enorme con miles de millones de cajas, donde el objeto buscado está en un lugar aleatorio sin pistas. La búsqueda clásica revisa las cajas una por una. Un computador cuántico podría, en apariencia, mirar dentro de todas a la vez, pero la demostración muestra que, sin una estructura especial, como en el algoritmo de Shor para la factorización, esa «mirada» solo ofrece una aceleración polinómica, no exponencial. La influencia de una variable en el polinomio garantiza que una entrada aleatoria casi siempre pueda predecirse a partir de un pequeño número de bits.

El resultado cambia las ideas sobre los límites de la supremacía cuántica. Ahora está claro que, para problemas sin estructura incorporada —grafos aleatorios, funciones aleatorias—, no cabe esperar una ventaja exponencial. Los computadores cuánticos conservan su ventaja allí donde hay estructura, como en la criptografía o en la optimización con propiedades especiales. Esto no anula la construcción práctica de dispositivos, pero orienta los esfuerzos hacia la búsqueda de precisamente ese tipo de problemas estructurados.

Un artículo en New Scientist del 12 de noviembre de 2026 y un preprint en arXiv del 8 de noviembre describen en detalle el desarrollo de la demostración y sus consecuencias para la relación entre las clases BPP y BQP en el mundo de los oráculos aleatorios.

La supremacía cuántica queda ahora más claramente delimitada: es real, pero requiere no aleatoriedad, sino una regularidad oculta.

3 Vues

Fuentes

  • AI confirms a long-suspected limit on quantum computers’ advantages

  • psi.inc

  • arxiv.org

Comentarios

¿Encontró un error o inexactitud?Consideraremos sus comentarios lo antes posible.