¿Qué problemas SÍ tienen ventaja cuántica probada?

Estado a: 10 de agosto de 2026. El Quantum Algorithm Zoo — el catálogo estándar del campo — lista más de 450 algoritmos cuánticos distintos. Pregunta cuántos de esos cargan una ventaja probada, en el sentido matemático de la palabra, y el catálogo colapsa a un puñado. Pregunta cuántos han demostrado esa ventaja end-to-end en hardware, en un problema útil, contra un rival clásico fuerte — y el número, a hoy, es cero. Este post es el mapa de ese colapso: qué significa realmente "probado", qué entradas sobreviven a cada definición, y por qué la brecha entre el catálogo y la lista ES el estado del arte.

¿Qué cuenta como "probado"?

"Ventaja cuántica probada" se usa para al menos tres cosas distintas, y la diferencia es toda la historia:

1. Teorema incondicional. Una prueba matemática, sin supuestos no demostrados, de que lo cuántico le gana a lo clásico en alguna tarea. Es el estándar de oro, se ha logrado exactamente una vez para una separación computacional — y es chica.
2. Teorema en un modelo restringido. Una prueba que vale dentro de un modelo formal (usualmente complejidad de consultas/oráculo: el algoritmo cuenta llamadas a una caja negra, no tiempo de reloj). Pruebas reales — el speedup cuadrático de Grover no solo está probado: está probado óptimo — pero el modelo puede esconder el costo de construir la caja.
3. Ventaja asintótica condicional. El runtime cuántico está probado; que no exista un algoritmo clásico rápido es una conjetura. El algoritmo de Shor — la ventaja "probada" más famosa del campo — vive aquí: nadie ha probado que factorizar sea clásicamente difícil.

Y hay un cuarto nivel que ninguno de los anteriores confiere: ventaja medida — una victoria end-to-end en hardware, en un problema útil, misma instancia, contra el baseline clásico más fuerte. Ese nivel está vacío. Las demostraciones sobre tareas de muestreo ("supremacía cuántica") son resultados de física reales sobre tareas sin uso conocido — esa línea la trazamos en ventaja cuántica vs. supremacía cuántica.

¿Qué entradas sobreviven?

La lista honesta, una fila por clase, con lo que está probado y lo que no:

Tres notas que la tabla obliga:

Shor es condicional — y sigue siendo la carta más fuerte. El lado cuántico es un teorema; el lado clásico ("factorizar no tiene algoritmo clásico rápido") es una observación empírica de 50 años, no una prueba. Mientras tanto, el récord genuino en hardware es humillante: un survey de 2024 sobre factorización en computadores cuánticos reales encuentra que "solo enteros muy pequeños N ≤ 35 han sido factorizados exitosamente con el algoritmo de Shor en un QC digital", y nota que muchos claims de factorizaciones mayores "dependen de un tipo de sobresimplificación que las hace equivalentes a tirar una moneda" (Willsch et al., 2024). La amenaza a RSA es real y está agendada — pero vive en estimaciones de recursos y roadmaps, no en factorización demostrada.

Grover es el único speedup famoso probadamente óptimo — y puede no pagar. BBBV (1997) probó que ningún algoritmo cuántico puede buscar en un espacio no estructurado con menos de ~√N consultas, así que la ganancia cuadrática de Grover es exacta y final. Pero Babbush et al. (2021) mostraron que los speedups cuadráticos no rinden ventaja neta en las primeras generaciones de máquinas tolerantes a fallos una vez pagado el sobrecosto de corrección de errores. Un speedup probado puede igual perder en hardware — prueba y rendimiento son monedas distintas.

HHL es la fábula del modelo de acceso. El teorema es real (BQP-completo), pero da por pagado un oráculo de preparación de estados. "Read the fine print" de Aaronson (2015) marcó la brecha; Tang (2018) y sucesores mostraron después que, para datos low-rank, algoritmos clásicos con acceso por muestreo emparejado cierran la brecha exponencial por completo. El teorema queda en pie; la ventaja que parecía prometer para cargas de machine learning, en su mayoría, no — la autopsia completa está en qué tumbó la dequantización.

¿Por qué la lista honesta es tan corta?

Porque un computador cuántico no es un probador paralelo de fuerza bruta — la medición devuelve UN resultado, y los speedups solo existen donde se puede coreografiar estructura de interferencia para que los caminos incorrectos se cancelen (el primer sobre qubits explica el mecanismo). Se sabe que esa estructura existe para pocas formas de problema: hallar períodos (Shor), búsqueda no estructurada (Grover, cuadráticamente), y simular la propia mecánica cuántica. Para todo lo demás del catálogo, el claim es asintótico, condicional a un modelo de acceso, o fue igualado clásicamente cuando alguien construyó el baseline correcto — el mecanismo que documentamos en por qué un baseline clásico débil arruina un benchmark cuántico. La revisión de la década en SSRN lo dice sin vueltas: la ventaja cuántica "se ha estrechado a un conjunto de problemas más pequeño y más claramente definido de lo que el campo imaginó hace diez años" (Khan, abr 2026).

¿Qué subiría una entrada de nivel?

Tres eventos observables, en orden ascendente de dificultad: (1) una victoria medida end-to-end — misma instancia, baseline clásico más fuerte, costos publicados — que es exactamente la vara que ningún problema útil ha superado (qué significa el punto de cruce); (2) hardware lo bastante barato y rápido para que los speedups polinomiales sobrevivan sus factores constantes — la vara de Babbush; (3) una prueba de dureza clásica para factorización o simulación — que sería uno de los resultados más profundos de la historia de la computación, y que nadie espera pronto.

¿Dónde queda Rosetta en este mapa? En ningún lugar halagador, y lo publicamos igual: nuestras corridas selladas son de optimización de portafolios a escala chica — una clase que no está en la lista probada — y ahí el baseline clásico ha ganado todas las comparaciones selladas a la fecha (el veredicto de portafolios). No tenemos corridas en factorización, búsqueda ni álgebra lineal cuántica, y no reclamamos ninguna.

Qué sabemos / qué no sabemos

Sabemos: el Zoo lista 450+ algoritmos (accedido ago 2026); exactamente un teorema de ventaja es incondicional (circuitos poco profundos, Science 2018); el speedup cuadrático de Grover está probado óptimo en el modelo de consultas (BBBV 1997); el runtime de Shor está probado polinomial (1994); el récord genuino de factorización en hardware es N ≤ 35 (arXiv:2410.14397); las ventajas de álgebra lineal cuántica low-rank fueron dequantizadas 2018–2020 (Tang 2018 y sucesores); los speedups cuadráticos no pagan en el hardware tolerante a fallos temprano (PRX Quantum 2021).

No sabemos: si factorizar es realmente difícil clásicamente — no existe prueba, y un avance clásico borraría la ventaja de Shor de un día para otro; qué speedups polinomiales, si alguno, sobreviven los costos end-to-end en máquinas reales — ninguno ha sido medido; dónde queda el cruce por instancia para simulación cuántica — cada número publicado es una estimación de recursos sobre hardware que no existe; si más entradas del Zoo caerán ante dequantización futura — la frontera sigue moviéndose; y si el "puñado" actual es la lista final o un artefacto de dónde los teóricos han mirado con más fuerza. Rosetta no tiene corridas selladas en ninguna clase de la lista probada; nuestra única clase medida es optimización a escala chica, donde el lado clásico está invicto.

Rosetta Q publica veredictos con datos crudos reproducibles. Esto es contenido educativo, no un claim de producto.