⚛️ quantum physics

Can PCE solve the factorisation problem via optimisation?

Este artículo explora la viabilidad de adaptar el algoritmo de Codificación de Correlación de Pauli (PCE) al problema de la factorización de enteros como un método para reducir drásticamente los requisitos de cúbits, ofreciendo un análisis preliminar de su potencial y limitaciones para el hardware cuántico de corto plazo sin reclamar una ventaja computacional.

Autores originales: Fernando Alonso, Colomán Samprón, Jacobo Veiga, Andrés Gómez

Publicado 2026-07-28

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Fernando Alonso, Colomán Samprón, Jacobo Veiga, Andrés Gómez

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que estás intentando descifrar un código secreto que protege tu cuenta bancaria, tus correos electrónicos y casi todo lo que haces en línea. Este código depende de un juego matemático simple pero truculento: toma dos números primos enormes (números que solo pueden dividirse por sí mismos y por 1), multiplícalos y entrega el resultado al mundo. Es fácil multiplicarlos, pero si solo tienes el número gigante final, averiguar qué dos primos lo crearon es como intentar des-hornear un pastel para encontrar la cantidad exacta de huevos y tazas de harina que se utilizaron. Para nuestros ordenadores actuales, esto es casi imposible para números muy grandes. Este es el problema de la "factorización de enteros", y es la columna vertebral de la seguridad digital moderna.

Ahora, imagina un nuevo tipo de ordenador que no solo calcula; sino que explora muchas posibilidades a la vez utilizando las extrañas reglas de la física cuántica. Los científicos han estado intentando enseñar a estas máquinas cuánticas a resolver este problema de "des-hornear". Un método famoso, inventado por Peter Shor, es teóricamente perfecto, pero requiere un ordenador cuántico tan potente y silencioso que aún no tenemos la tecnología para construirlo. Por ello, los investigadores están buscando atajos "inspirados en la cuántica" (quantum-inspired): métodos que utilicen un poco de magia cuántica pero que puedan ejecutarse en las máquinas ruidosas e imperfectas que tenemos hoy en día. La gran pregunta es: ¿Podemos comprimir este problema matemático masivo en un rompecabezas pequeño y manejable que estos primeros ordenadores cuánticos realmente puedan resolver?

Este artículo explora exactamente esa pregunta utilizando un truco ingenioso llamado Codificación de Correlación de Pauli (PCE, por sus siglas en inglés). Piensa en la PCE como un algoritmo de compresión súper eficiente. Normalmente, para representar un problema complejo con muchas variables (como los bits de un número enorme), necesitas un gran número de bits cuánticos (qubits). La PCE actúa como una cremallera mágica, permitiendo a los investigadores empaquetar miles de variables en un número mucho menor de qubits. El equipo de Fernando Alonso y su equipo del Centro de Supercomputación de Galicia se preguntaron: "Si utilizamos esta cremallera para comprimir el problema de la factorización, ¿podemos entonces utilizar técnicas de optimización para encontrar la respuesta?".

No se limitaron a adivinar; construyeron dos "mapas" diferentes para guiar la búsqueda. El primer mapa, llamado el enfoque Básico, era como intentar encontrar los factores adivinando directamente el código binario de los dos números primos. Lo probaron con números de hasta 25 bits de longitud. Los resultados fueron algo mixtos: funcionaba bien para números pequeños, pero a medida que los números se hacían más grandes, la tasa de éxito disminuía y el ordenador a menudo se quedaba estancado en soluciones "triviales" (como decir que un número es simplemente él mismo por uno).

El segundo mapa, llamado DoTS (Diferencia de Dos Cuadrados), era una estrategia más inteligente. En lugar de buscar los factores directamente, buscaba dos números cuyos cuadrados difieran por un múltiplo del número objetivo. Es como buscar a dos personas que, al subirlas a una báscula, tienen una diferencia de peso que coincide perfectamente con un patrón específico. Este enfoque fue mucho más exitoso. En sus simulaciones, el método DoTS logró factorizar números de hasta 36 bits de longitud.

El equipo utilizó tres diferentes "motores de búsqueda" (optimizadores) para navegar por sus mapas: Evolución Diferencial (DE), Optimización de Enjambre de Partículas (PSO) y una versión de inspiración cuántica llamada QDPSO. Los resultados mostraron que el optimizador DE fue el claro ganador, encontrando consistentemente las respuestas correctas donde los otros tuvieron dificultades.

Sin embargo, los autores son muy cuidadosos de no afirmar que han "roto" el código. Enfatizan que, aunque su método utiliza muchos menos qubits que otros enfoques cuánticos (lo que lo hace viable para el hardware actual), sigue siendo una simulación que se ejecuta en ordenadores clásicos. Descubrieron que para números mayores de 36 bits, su método actual empieza a fallar, lo que sugiere que la "función de coste" (el libro de reglas que escribieron para el ordenador) podría necesitar ser reescrita para capturar la matemática de manera más efectiva. También señalaron que, si ejecutaran esto en hardware cuántico real, el ruido podría ayudar al ordenador a escapar de callejones sin salida, o podría arruinar el cálculo por completo.

En resumen, este artículo sugiere que la PCE es una herramienta prometedora que podría hacer que los problemas de factorización sean mucho más pequeños y manejables para los ordenadores cuánticos. Todavía no resuelve el problema de los números masivos utilizados en la criptografía del mundo real, pero abre una nueva puerta. Demuestra que, con la compresión adecuada y la estrategia de búsqueda correcta, podríamos lograr que los ordenadores cuánticos hagan un trabajo serio de procesamiento de números antes de lo que pensábamos, incluso si todavía nos queda un largo camino por recorrer antes de poder des-hornear los pasteles más grandes del mundo.

Resumen Técnico: ¿Puede el PCE resolver el problema de la factorización mediante la optimización?

Planteamiento del Problema
La factorización de enteros, particularmente de números semiprimos ( $N = p \cdot q$ ), es un problema fundamental en la teoría de números computacional y la base de seguridad para la criptografía RSA. Aunque el algoritmo de Shor ofrece una solución cuántica de tiempo polinomial, el hardware actual de Escala Intermedia con Ruido (NISQ) carece de la cantidad de cúbits y la coherencia necesarias para una implementación práctica. Otros enfoques, como los Algoritmos Cuánticos Variacionales (VQA) que convierten la factorización en problemas de optimización binaria, enfrentan problemas de escalabilidad, requiriendo típicamente un número de cúbits que escala linealmente con el número de variables binarias. Esta escalabilidad lineal los hace inviables para instancias de gran escala en el hardware actual. El artículo investiga si la Codificación de Correlación de Pauli (PCE, por sus siglas en inglés), un marco capaz de codificar $m$ variables binarias utilizando un número polinomial de cúbits ( $n \ll m$ ), puede adaptarse para resolver el problema de la factorización mediante la optimización con recursos limitados.

Metodología
El estudio reformula el problema de la factorización como una tarea de optimización binaria y aplica PCE para reducir los requisitos de cúbits. La metodología consiste en:

Estrategias de Codificación: Se desarrollaron dos enfoques distintos para mapear las restricciones de factorización en una función de costo:
- Enfoque Básico: Codifica directamente las representaciones binarias de los factores desconocidos $p$ y $q$ . La función de costo minimiza la distancia de Hamming al cuadrado entre el entero objetivo $N$ y el producto candidato $x_p \cdot x_q$ , con penalizaciones para evitar soluciones triviales (por ejemplo, $N \cdot 1$ ).
- Enfoque de Diferencia de Dos Cuadrados (DoTS): Reformula el problema como la búsqueda de enteros $a$ y $b$ tales que $a^2 \equiv b^2 \pmod N$ (con $a \not\equiv \pm b$ ). Los factores se recuperan mediante $\gcd(a-b, N)$ y $\gcd(a+b, N)$ . La función de costo combina un término que impone la congruencia modular con un término que verifica la factorización resultante.
Circuito Cuántico: Se empleó un ansatz de tipo "brickwork" eficiente para el hardware, que consiste en capas alternas de rotaciones de un solo cúbit ( $R_X, R_Y, R_Z$ ) y puertas de entrelazamiento ( $R_{XX}, R_{YY}, R_{ZZ}$ ). El orden de compresión de la PCE, $k$ , determina la profundidad del circuito y el número de cúbits requeridos ( $n \approx m/k$ ).
Optimización: Los circuitos cuánticos parametrizados fueron simulados clásicamente utilizando Qiskit Aer. La optimización se realizó utilizando tres algoritmos libres de gradiente: Evolución Diferencial (DE), Optimización por Enjambre de Partículas (PSO) y Optimización por Enjambre de Partículas Delta Cuántica (QDPSO). Se utilizó la función signo para aproximar las variables binarias, evitando la relajación de la tangente hiperbólica para prevenir soluciones de valores reales infinitos.

Contribuciones Clave y Resultados

Reducción de Recursos: El estudio demuestra que la PCE puede reducir drásticamente el número de cúbits necesarios para la factorización. Para longitudes de clave RSA típicas, los cúbits requeridos permanecen dentro de un rango "asequible" para el hardware actual o cercano, y para órdenes de compresión $k > 2$ , el problema puede resolverse enteramente en computadoras clásicas mediante la emulación de circuitos cuánticos.
Comparación de Rendimiento:
- DoTS vs. Básico: El enfoque DoTS superó consistentemente al enfoque Básico. La función de costo de DoTS, que captura la estructura aritmética de la relación de diferencia de cuadrados, produjo tasas de éxito más altas y un paisaje de optimización más favorable.
- Sensibilidad del Optimizador: La Evolución Diferencial (DE) demostró ser el optimizador más robusto, logrando factorizaciones exitosas en diversas longitudes de bits. Los métodos basados en enjambres (PSO, QDPSO) exhibieron tasas de éxito significativamente menores, lo que sugiere que el paisaje de optimización es desafiante para estos algoritmos específicos.
- Límites de Escalabilidad: El método factorizó exitosamente semiprimos de hasta 36 bits utilizando el enfoque DoTS con $k=4$ y DE. Las tasas de éxito disminuyeron para enteros mayores a 25–36 bits, indicando limitaciones intrínsecas en las formulaciones actuales de las funciones de costo para instancias más grandes.
Eficiencia de Búsqueda: El análisis del número de evaluaciones de la función objetivo mostró que el algoritmo no depende de una exploración de fuerza bruta. El número de evaluaciones se mantuvo varios órdenes de magnitud por debajo del tamaño del espacio de búsqueda combinatoria ( $2^n$ ), lo que indica un proceso de búsqueda guiada.

Significancia y Reivindicaciones
El artículo posiciona este trabajo como una contribución preliminar y exploratoria en lugar de una solución definitiva o una reivindicación de ventaja computacional sobre algoritmos existentes.

Factibilidad: El hallazgo principal es que los algoritmos basados en PCE son un marco plausible para estudiar la factorización como un problema de optimización con recursos cuánticos limitados. Ofrece una perspectiva alternativa a los métodos establecidos como VQF y QAOA al desacoplar el número de variables del número de cúbits.
Limitaciones: Los autores declaran explícitamente que las formulaciones actuales no escalan con éxito hacia tamaños de enteros criptográficamente relevantes (por ejemplo, RSA de 2048 bits). El éxito del método depende fuertemente del diseño de la función de costo clásica y de la elección del optimizador.
Direcciones Futuras: El estudio sugiere que la investigación futura debería centrarse en:
- Diseñar funciones de costo más informativas que capturen mejor la estructura aritmética de la factorización (potencialmente incorporando variables de acarreo).
- Explorar suposiciones de factores balanceados (comunes en RSA) para reducir el conteo de variables.
- Investigar estrategias de inicio en caliente (warm-start) y arquitecturas de ansatz alternativas.
- Evaluar el rendimiento bajo modelos de ruido realistas.

En conclusión, aunque el método no amenaza actualmente la seguridad de RSA, establece un marco viable y eficiente en recursos para investigar la factorización mediante la optimización de inspiración cuántica, lo que justifica una mayor investigación en el diseño de funciones de costo y refinamientos algorítmicos.

Resumen Técnico: ¿Puede el PCE resolver el problema de la factorización mediante la optimización?

Más como este