En la era de la computación cuántica de escala intermedia y con ruido (NISQ, por Noisy Intermediate-Scale Quantum), la ventaja cuántica se muestra como ventaja de escalado. Solo se ilustra que el crecimiento asintótico de los recursos cuánticos es más lento que el del mejor método clásico; sin ninguna demostración matemática rigurosa de dicho orden de complejidad algorítmica. Se publica en Nature Computational Science este tipo de ventaja cuántica para un algoritmo NP-completo, el problema one-in-three SAT, una variante del problema de la satisfacibilidad booleana en la que cada cláusula de tres literales se satisface cuando uno de ellos es verdadero. Se construyen versiones optimizadas de los algoritmos VQE (Variational Quantum Eigensolver), QAOA (Quantum Approximate Optimization Algorithm) y QAA (Quantum Adiabatic Algorithm) que muestran una ventaja de escalado frente a los algoritmos clásicos modernos; en concreto, 1.0070n para QAA-RSRA y 1.0077n para QAOA-RSRA frente a 1.0128n para el mejor algoritmo clásico ensayado, estimaciones obtenidas con simulaciones clásicas de los algoritmos cuánticos con hasta n=70. Nótese que para QAA una ventaja cuántica con un factor de 10 ≅ (1.0128/1.0070)n requiere n = 401, es decir, unos 200 cúbits, y para QAOA unos 228 cúbits; para un factor de 100 serían 601 y 684 cúbits, resp. Por ello solo se ilustra la viabilidad experimental de los algoritmos cuánticos con ejecuciones de los algoritmos en un ordenador cuántico con 8 y 13 cúbits.
La novedad es el uso de un algoritmo de reducción por restricción del espacio (RSRA por Restricting Space Reduction Algorithm). Así se relaja cada condición “uno de tres” (one-in-three) a “un número impar de tres” en aritmética módulo 2. Si k es el rango de las cláusulas linealmente independientes módulo 2, la dimensión del espacio de búsqueda disminuye de 2n a 2n−k; en las instancias aleatorias estudiadas, k ≈ m (el número de cláusulas del problema SAT), por lo que se reduce la dimensión a 2n−m. Las soluciones que satisfacen la relajación módulo 2, pero no el problema original, se codifican como un problema 2-SAT dentro de dicho subespacio. Para reducir el número n de cúbits necesario para procesar las n variables booleanas, se selecciona un subconjunto mínimo G de las variables originales que contenga al menos dos de las tres variables de cada cláusula; como el hamiltoniano cuántico restringido solo depende de las variables en G, el circuito cuántico necesita |G| cúbits en vez de n (las variables fuera de G pueden reconstruirse mediante las ecuaciones de paridad). Para una densidad crítica m/n = 0.626 se logra la reducción máxima de |G| ≅ 0.5 n. Por ejemplo, para n=100 y k≅63 el espacio permitido tiene 2³⁷ configuraciones y se implementa con |G|≅50 cúbits.
Sin lugar a dudas, lograr una ventaja cuántica para un algoritmo NP-completo es un resultado muy llamativo, aunque solo sea una ventaja cuántica tipo NISQ. En cierto sentido es hacer trampa, por que la ventaja que se logra es ridícula c comparada con la obtenida usando algoritmos cuánticos que generan ruido cuántico. Pero los problemas NP-completo tienen gran interés aplicado, así que desde el punto de vista aplicado es una ventaja cuántica tramposa mucho más útil. El artículo es Quanfeng Lu, Shijie Wei, …, Gui-Lu Long, «Evidence of scaling advantage on an NP-complete problem with enhanced quantum solvers,» Nature Computational Science (19 Jun 2026), doi: https://doi.org/10.1038/s43588-026-01007-8, arXiv:2508.08869 [quant-ph] (12 Aug 2025).
Esta figura ilustra la topología usada en los experimentos y el algoritmo de optimización de los circuitos cuánticos. Sin embargo, los resultados más interesantes se han obtenido mediante simulaciones clásicas. Para una instancia VQE de 150 variables y 94 cláusulas se obtuvieron 166 éxitos en 2000 inicializaciones (8.3 %, con un intervalo binomial aproximado 7.1–9.5 % al 95 %). Para una instancia de 100 variables y 63 cláusulas, la probabilidad de éxito del QAA aumentó desde casi cero hasta más de 0.8 al pasar de 2 a 53 capas, mientras que la del QAOA superó 0.4 con 16 capas.
En la región crítica y para tamaños de hasta n=70, el QAA mejorado con 150 capas escaló como 1.0070n ([1.0068,1.0071]n con confianza al 95 %) y el QAOA con 40 capas como 1.0077n ([1.0077,1.0078]n), frente a 1.0128n ([1.0127,1.0129]n) para el mejor algoritmo clásico; la pequeña diferencia en la base representa una separación exponencial creciente con n.
Los pequeños experimentos en el ordenador cuántico muestran que los métodos VQE-RSRA y QAOA-RSRA alcanzaron probabilidades de éxito del 43.04 % y 36.40 %, resp., frente al 25 % del muestreo aleatorio restringido, mientras que las versiones sin RSRA tuvieron un éxito casi nulo. Las curvas experimentales de la figura son medias de cinco optimizaciones y sus barras de error representan una desviación estándar. Repito que estos resultados experimentales son simples ilustraciones de viabilidad (con solo 13 cúbits, su simulación en un ordenador clásico sería casi instantánea).
En resumen, lo que más me ha llamado la atención de este artículo, más allá del NP-completo en su título, es que la idea de base, reducir de forma «inteligente» la dimensionalidad del espacio de búsqueda, es muy general y con seguridad se puede aplicar a muchos otros problemas NP-completos. Pero la ventaja de escalado es cuántica, pues cuando se emplea el RSRA con los algoritmos clásicos equivalentes no se logra ninguna ventaja de escalado (usar RSRA escala peor que no usarlo). Creo que este tipo de ventajas de escalado cuánticas se descubrirán en muchos otros algoritmos NP-completos y podrían tener un impacto real en las futuras aplicaciones prácticas de los ordenadores cuánticos. Tiempo al tiempo.
Pero no veo el avance si solo se experiment con simulaciónes falsas no reales asi de simple eso es un video juego que escalaste pero de mentira y digo mas fácil es hacer Quantum real que simulación de fantasy