From Period Finding to Lattice Sampling: Experimental Insights into Shor's and Regev's Factoring Algorithms

Resumen Técnico: Del hallazgo de periodos al muestreo de redes

Planteamiento del problema
Si bien el algoritmo de Shor resuelve teóricamente la factorización de enteros en tiempo polinomial, su implementación práctica en el hardware actual de Escala Intermedia con Ruido (NISQ) está severamente limitada por la profundidad del circuito, los errores de puerta y la decoherencia. Estas limitaciones han impulsado el interés en algoritmos de factorización alternativos, como el algoritmo de Regev, que reformula el problema como una tarea de muestreo de redes de mayor dimensión en lugar de un problema de hallazgo de periodos unidimensional. Sin embargo, los análisis experimentales existentes a menudo carecen de comparaciones sistemáticas entre múltiples backends bajo condiciones estrictamente controladas para comprender cómo estas distintas estructuras algorítmicas interactúan con el ruido realista del hardware. Este estudio aborda esta brecha comparando experimentalmente los algoritmos de Shor y de Regev en hardware cuántico real para caracterizar su robustez relativa y sus modos de fallo.

Metodología
Los autores llevaron a cabo un estudio experimental controlado utilizando la instancia de referencia $N = 15$. Ambos algoritmos se implementaron utilizando Qiskit y se ejecutaron en dos backends cuánticos distintos: la computadora cuántica QMIO en el Centro de Supercomputación de Galicia (CESGA) y un procesador cuántico de acceso abierto de IBM (ibm_torino). Las simulaciones ideales (sin ruido) sirvieron como línea de base de referencia.

• Configuración de los algoritmos:
  • Algoritmo de Shor: Utilizó una base $a=2$ con un registro de control de $k=3$ qubits para hallar el orden $r=4$. El circuito utilizó construcciones de exponenciación modular especializadas y de poca profundidad basadas en permutaciones, en lugar de aritmética genérica, para minimizar la profundidad.
  • Algoritmo de Regev: Configurado como una instancia bidimensional ($d=2$) con bases $a_1=4, a_2=49$. Empleó una superposición gaussiana sobre $\mathbb{Z}^d$ seguida de un muestreo de Fourier para aproximar vectores en la red dual.
• Compilación y ejecución: Los circuitos fueron transpiled utilizando Qiskit con parámetros ajustados para los conjuntos de puertas nativas y la conectividad de cada backend. Todas las ejecuciones en hardware utilizaron 4,096 disparos (shots).
• Métricas de evaluación: Para cuantificar el impacto del ruido sin depender de una reconstrucción clásica completa para cada ejecución, los autores introdujeron métricas basadas en la distribución:
  • Entropía de Shannon ($H(p)$): Mide la dispersión de la distribución de probabilidad.
  • Tamaño de soporte efectivo ($N_{eff}$): Estima el número de resultados que contribuyen significativamente a la distribución.
  • Masa Top-K ($M_4$): La fracción de la probabilidad total contenida en los cuatro resultados más frecuentes.

Contribuciones clave

1. Benchmark experimental controlado: El artículo proporciona una comparación directa y de bajo nivel de los algoritmos de Shor y de Regev sobre la misma instancia del problema ($N=15$) a través de múltiples plataformas de hardware y simulaciones ideales.
2. Evaluación multi-backend: Los resultados se reportan tanto para los dispositivos de IBM como para los de QMIO, ofreciendo una visión de cómo las diferentes arquitecturas de hardware afectan el rendimiento algorítmico.
3. Interpretación de la codificación de información: El estudio interpreta los resultados experimentales a través de la lente de la "concentración de información" (Shor) frente a la "distribución de información" (Regev). Demuestra cómo estas diferencias estructurales conducen a degradaciones inducidas por el ruido cualitativamente distintas en los histogramas de medición.
4. Reproducibilidad: Los autores reportan los parámetros algorítmicos específicos y los procesos de compilación utilizados para generar las distribuciones experimentales.

Resultos
Los datos experimentales revelan modos de fallo distintos para los dos algoritmos bajo las restricciones de NISQ:

• Algoritmo de Shor (Concentración de información):

  • En simulaciones ideales, la masa de probabilidad está altamente concentrada en un pequeño número de picos espectrales (baja entropía, $N_{eff} \approx 4$, $M_4 = 1.0$).
  • En el hardware de IBM, la distribución se ensancha pero mantiene picos dominantes ($M_4 = 0.921$), lo que permite un éxito parcial en la recuperación del orden.
  • En el dispositivo QMIO, que es más ruidoso, los picos espectrales se aplanan y oscurecen significativamente ($M_4 = 0.564$, $N_{eff} \approx 7.8$), lo que provoca una pérdida de la estructura periódica necesaria para la reconstrucción clásica.
  • Observación: El algoritmo de Shor es altamente sensible a los errores de fase; una vez que los picos agudos se ensanchan debido al ruido, el algoritmo deja de proporcionar información útil.

• Algoritmo de Regev (Distribución de información):

  • En simulaciones ideales, la distribución es inherentemente más dispersa que la de Shor, pero aún exhibe un subconjunto de vectores dominantes consistentes con la red dual ($N_{eff} \approx 2.34$, $M_4 = 0.944$).
  • En el hardware de IBM, la distribución se vuelve más extendida ($M_4 = 0.645$), aunque un subconjunto de resultados sigue siendo lo suficientemente dominante como para soportar potencialmente la reducción de redes.
  • En QMIO, la señal geométrica se diluye fuertemente ($M_4 = 0.29$, $N_{eff} \approx 15.8$), con la masa de probabilidad extendiéndose uniformemente a través de muchos vectores, lo que efectivamente oscurece la estructura de la red.
  • Observación: El algoritmo de Regev depende de un sesgo estadístico a través de múltiples muestras correlacionadas. Aunque utiliza circuitos con una profundidad compilada menor (la Tabla 2 muestra que la profundidad compilada de Regev es menor que la de Shor en ambas plataformas), la etapa de muestreo multidimensional introduce una sensibilidad al ruido que causa una rápida dispersión de la señal geométrica.

• Profundidad de circuito vs. Robustez: A pesar de que el algoritmo de Regev tiene una profundidad de circuito compilado más baja (por ejemplo, 147 frente a 210 en IBM), esta reducción no se tradujo en una mayor robustez en el hardware actual. Las distribuciones de medición de Regev se dispersaron más rápidamente bajo el ruido en comparación con las de Shor.

Significancia y afirmaciones
El artículo afirma modestamente que ninguno de los dos algoritmos demuestra una ventaja práctica sobre el otro en el régimen de $N$ pequeño ($N=15$) en los dispositivos NISQ actuales. En su lugar, el estudio destaca un compromiso fundamental:

• El algoritmo de Shor se beneficia de salidas altamente estructuradas y concentradas cuando el ruido es bajo, pero falla catastróficamente cuando se pierde la coherencia de fase.
• El algoritmo de Regev distribuye la información en un espacio de mayor dimensión, lo que puede ofrecer propiedades de escalado diferentes para problemas más grandes, pero actualmente sufre de una mayor sensibilidad al ruido en el muestreo multidimensional.

Los autores concluyen que estos resultados subrayan el valor de la evaluación experimental para comprender las implicaciones prácticas de las elecciones de diseño algorítmico. Enfatizan que las relaciones asintóticas en el entorno de tolerancia a fallos no garantizan un comportamiento similar en el hardware NISQ, donde la codificación específica de la información aritmética (concentración vs. distribución) dicta cómo se manifiesta el ruido y cómo fallan los algoritmos. Se propone como trabajo futuro extender estos benchmarks a un $N$ mayor y explorar estrategias de mitigación de errores dirigidas a estos compromisos específicos.