Estrategias de Oráculo

Estrategia 1: Unitario Denso (predeterminada para n_bits <= 6)

Usada para curvas con orden de grupo de hasta ~6 bits. Implementada en projecteleven.py.

Cada adición de punto controlada "añadir S" se representa como una matriz de permutación de 2^(n+1) x 2^(n+1) aplicada mediante qc.unitary(). La matriz codifica la acción completa del grupo: el bloque superior izquierdo es identidad (control=0), el bloque inferior derecho permuta los estados base según el mapa P -> P+S (control=1).

• Codificación: Índice de grupo (0..n-1)
• Memoria: O(2^{2n}) por matriz
• Qubits: 2t + n (dos registros de conteo + registro de punto)
• Limitación: La descomposición unitaria de Qiskit es O(4^n), lo que hace esto inviable más allá de ~6 bits

Estrategia 2: Descomposición Eficiente de Permutaciones (predeterminada para n_bits > 6)

Usada para curvas más grandes. Implementada en quantum_arithmetic.py.

En lugar de construir matrices densas, cada permutación "añadir S" se descompone en ciclos como transposiciones. Cada transposición (intercambio de dos estados base |a> <-> |b>) se implementa con:

1. Reducción CNOT -- CNOTs desde un bit pivote a todos los demás bits diferentes, reduciendo la diferencia de múltiples bits a una diferencia de un solo bit
2. X multicontrolada -- Una puerta MCX en el bit pivote, condicionada a que todos los demás bits coincidan con el patrón objetivo
3. Deshacer CNOTs -- Invertir el paso 1 para restaurar los bits no pivote

La MCX utiliza descomposición en cadena V con (n-2) qubits ancilla dedicados, proporcionando O(n) puertas Toffoli por MCX en lugar de O(n^2) sin ancillas. Cada adición controlada se construye como un subcircuito aislado y se agrega como una sola puerta opaca, evitando el crecimiento cuadrático del DAG en Qiskit.

• Codificación: Índice de grupo (0..n-1)
• Memoria: O(N) por adición (N = orden del grupo)
• Qubits: 2t + n + (n-2) ancillas
• Puertas por adición: O(N * n)

Estrategia 3: Oráculo Cuántico Basado en Coordenadas (--oracle coordinate)

Disponible para curvas de hasta ~6 bits. Implementada en quantum_oracle.py.

En lugar de codificar puntos como índices de grupo, el registro cuántico contiene coordenadas reales (x, y) de elementos de campo en binario más una bandera de identidad. El diseño del registro de punto es:

• x_reg: qubits f_bits (f_bits = ceil(log2(p)))
• y_reg: qubits f_bits
• id_flag: 1 qubit (1 = punto en el infinito)

Cada "añadir S" controlado se calcula a partir de la fórmula de adición EC sobre todas las codificaciones de coordenadas válidas, produciendo una permutación en el registro de coordenadas. Esta permutación se descompone en ciclos como transposiciones utilizando la misma infraestructura de reducción CNOT + MCX que la Estrategia 2.

• Codificación: Coordenadas (x, y, id_flag)
• Qubits: 2t + 2f_bits + 1 + max(0, 2f_bits - 1) ancillas
• Puertas por adición: O(N * f_bits)

Estrategia 4: Oráculo Aritmético (--oracle arithmetic)

Marco para la adición de puntos con escalado polinomial. Implementada en quantum_oracle.py y quantum_arithmetic.py.

Utiliza codificación de coordenadas (igual que la Estrategia 3) con primitivas de aritmética modular basadas en QFT como componentes básicos hacia la adición de puntos completamente aritmética. El código base incluye implementaciones probadas de:

• Sumador modular de Beauregard -- basado en QFT (target + constante) mod p con descomputación de ancilla adecuada
• Multiplicación modular cuántico-cuántico -- |a>|b>|0> -> |a>|b>|a*b mod p> mediante shift-and-add con duplicación modular explícita, O(n^3) puertas
• Permutación de inverso modular -- |x> -> |x^{-1} mod p> mediante transposiciones de tabla de consulta
• Suma modular cuántico-cuántico controlada -- |a> controlado -> |a + b mod p> con reducción de Beauregard

Las primitivas aritméticas logran un escalado O(n^3) por adición de punto frente a O(N*n) para el enfoque de permutación. Sin embargo, las operaciones basadas en QFT conllevan un factor constante ~150 veces mayor, lo que hace que el enfoque aritmético sea más eficiente solo para curvas por encima del orden de grupo de ~20 bits. Para los tamaños de desafío actuales (hasta 12 bits), el sumador basado en permutación sigue siendo más rápido y se utiliza por defecto.

Estrategia 5: Estimación de Fase Semiclásica de Google (--oracle google)

Implementada en google_semiclassical.py. Inspirada en la técnica de estimación de fase con reciclaje de qubits de Griffiths & Niu (1996), aplicada a escala en Babbush et al. (2026) para estimaciones de recursos de ECDLP en secp256k1. El artículo de Babbush et al. fue publicado el 30 de marzo de 2026.

Reemplaza los dos registros de conteo multiqubit (j, k) y la QFT inversa masiva con dos qubits reciclados individuales y correcciones de fase condicionadas clásicamente. Cada bit del registro de conteo se procesa secuencialmente: preparar en |+>, aplicar adición de punto controlada, corregir fase según todos los bits medidos previamente, luego medir. Los primitivos de circuito dinámico reset + if_test en Qiskit permiten esto en hardware IBM Quantum.

El oráculo para las adiciones de puntos controladas se delega en la infraestructura existente (unitario denso para <= 6 bits, permutación eficiente para > 6 bits), por lo que el ahorro de qubits proviene completamente de eliminar los registros de conteo.

• Codificación: Igual que la estrategia subyacente (índice de grupo)
• Qubits: 2 + n_bits + ancillas (vs 2t + n_bits + ancillas)
• Compensación: Requiere circuitos dinámicos (medición en medio del circuito, reset, puertas condicionadas clásicamente). Funciona en IBM Heron r2 hasta 7 bits; a partir de 8 bits, la sobrecarga de sincronización de retroalimentación clásica excede el presupuesto de tiempo de la QPU

Estrategia 6: Suma Modular con Ripple-Carry (--oracle ripple)

Implementada en ripple_carry_shor.py. Utiliza sumadores ripple-carry CDKM (Cuccaro et al. 2004) para las adiciones de puntos controladas, reemplazando tanto las matrices unitarias densas como los circuitos de transposición descompuestos en ciclos.

En la codificación de índice de grupo, el punto P = kG se representa por su índice k en el grupo cíclico. Añadir S = sG se convierte en suma modular de la constante clásica s (mod n). La idea clave: cada adición de punto controlada se reduce a una única suma modular controlada de una constante conocida, implementada mediante CDKMRippleCarryAdder e IntegerComparator de Qiskit.

El oráculo consiste en 2m sumas modulares controladas (m por registro de conteo), donde cada suma modular controlada realiza:

1. Cargar constante en el registro ancilla mediante CX desde el qubit de control
2. Medio sumador CDKM para añadir ancilla al acumulador (solo puertas de vecino más cercano)
3. Comparador de enteros para detectar desbordamiento (acc >= n)
4. Resta condicional de n mediante adición controlada por bandera de 2^m1 - n
5. Descomputación de bandera mediante sondeo basado en acarreo

No se utiliza conocimiento de la clave privada d en la construcción del circuito. Los índices de grupo para las potencias de G se calculan como 2^i mod n (públicos). Los índices de grupo para las potencias de Q se derivan de la enumeración pública del grupo cíclico generado por G — el punto Q se busca en esta enumeración.

• Codificación: Índice de grupo (0..n-1)
• Qubits: 4m + 5 donde m = ceil(log2(n))
• Puertas por adición: O(m) operaciones CDKM, cada una con O(m) puertas CX
• Escalado total CX: O(m^3)
• Mapeo a hardware: CDKM utiliza solo puertas de vecino más cercano, dando una sobrecarga de enrutamiento de ~1x en la topología heavy-hex de IBM (frente a 26-33x para sumadores basados en QFT)

Comparación

Primitivas Aritméticas QFT

El código base incluye componentes básicos de aritmética modular basados en QFT (sumadores Beauregard/Draper, multiplicación modular cuántico-cuántico, inverso/negación modular) como base hacia la codificación de coordenadas completamente aritmética a 256 bits. Estas primitivas han sido verificadas correctas mediante simulación Statevector para primos hasta p=13.

Resultados

Se recuperaron con éxito claves privadas en hardware IBM Quantum para curvas de desafío de hasta 17 bits:

Todas las ejecuciones se realizaron en el plan de instancia abierta de IBM Quantum, que otorga 10 minutos de computación cuántica gratuita por mes. Los registros completos de ejecución se encuentran en la carpeta executions/.

La estrategia ripple-carry (Estrategia 6) permitió un gran salto: de 10 bits (40 qubits, 2M puertas) a 17 bits (69 qubits, 112K puertas) — un incremento de 7 bits en el tamaño de clave con una reducción de 18x en el recuento de puertas de dos qubits. La estructura de puertas de vecino más cercano del sumador CDKM se mapea eficientemente a la topología heavy-hex de IBM, manteniendo la sobrecarga de enrutamiento cerca de 1x.

PE Semiclásica: Circuitos Dinámicos en Hardware IBM

La estrategia semiclásica (--oracle google) recuperó con éxito claves a 4, 6 y 7 bits utilizando circuitos dinámicos (reset en medio del circuito, puertas p condicionadas clásicamente mediante if_test) en procesadores IBM Heron r2. A 7 bits, el circuito utiliza solo 14 qubits (frente a 26 para el enfoque de permutación estándar) mientras produce recuentos de puertas 2Q comparables después de la transpilación.

A 8 bits y más, el enfoque semiclásico se vuelve impracticable en el hardware actual de IBM. Aunque if_else y reset son compatibles en Heron r2 (confirmado mediante inspección del backend objetivo), cada punto de retroalimentación clásica requiere una sincronización completa de la QPU — los 156 qubits físicos deben estar inactivos mientras el controlador clásico procesa la condicional para los ~16 qubits activos. Con ~295K puertas CZ divididas en 16+ puntos de retroalimentación, la sobrecarga de ejecución por disparo hace que los trabajos excedan el presupuesto de tiempo de la QPU. El enfoque de permutación estándar, que ejecuta el mismo recuento de puertas como un solo lote continuo sin circuitos dinámicos, se completa con éxito a esta escala.

Una truncación aproximada de QFT (parámetro max_corrections) reduce el número de bloques if_else de O(n^2) a O(n) al retener solo las k correcciones de fase más cercanas por paso de medición (los ángulos más allá de k contribuyen < pi/2^{k+1}, por debajo del piso de ruido del hardware). Con max_corrections=1, el circuito de 8 bits tiene 16 bloques if_else — aún suficiente para causar tiempo de espera en hardware IBM con este recuento de puertas.

Análisis de Ruido y Fidelidad

Fidelidad Estimada del Circuito

Suponiendo una fidelidad típica de puerta de dos qubits (CX) de ~99.5% en IBM Quantum, la fidelidad estimada del circuito cae exponencialmente con el recuento de puertas:

La fidelidad del circuito se calcula como F ≈ (0.995)^{CX_count}. Para todo más allá de 4 bits, la fidelidad estimada es astronómicamente pequeña — la distribución de salida está abrumadoramente dominada por ruido.

Por Qué Sigue Funcionando

Para 8 bits y más, cada disparo produce una cadena de bits casi única (8,128 resultados únicos de 8,192 disparos a 8 bits; los 20,000 únicos a 16 y 17 bits). La salida es indistinguible de un muestreo aleatorio uniforme a nivel de cadena de bits. Sin embargo, el algoritmo aún recupera la clave privada correcta.

La idea clave es que el postprocesamiento de Shor es robusto al ruido de una manera que el análisis bruto de cadenas de bits no lo es. Cada disparo produce un triple de medición (j, k, r). La extracción calcula d_cand = (r - j) · k^{-1} mod n y verifica mediante d_cand · G == Q. Solo la verdadera d pasa la verificación EC, por lo que incluso un único candidato correcto entre miles de disparos ruidosos es suficiente.

Un triple (j, k, r) puramente aleatorio produce el d_cand correcto con probabilidad ~1/n. Con S disparos, el número esperado de aciertos verificados del ruido solo es ~S/n. A 17 bits (n=65,173, S=20,000), esto da ~0.3 aciertos de ruido esperados — cualquier recuperación exitosa a esta escala proporciona evidencia de señal cuántica más allá del piso de ruido clásico.

Para las curvas más pequeñas donde disparos >> n (por ejemplo, 10 bits con n=547 y 1,024 disparos), el piso de ruido es ~1,024/547 ≈ 1.9 votos por candidato. Incluso un puñado de disparos que contienen señal empuja la d correcta por encima del piso de ruido. Esto explica cómo el algoritmo tiene éxito a pesar de fidelidades de circuito que harían parecer imposible la computación.

Señal Cuántica vs Ruido Clásico

A escala de juguete, el paso de verificación de la extracción (d_cand * G == Q) actúa como un filtro que acepta solo la d verdadera. Esto significa que incluso los triples (j, k, r) puramente aleatorios producirán candidatos válidos a una tasa de aproximadamente disparos / n por ejecución. Cuando disparos >> n, el ruido aleatorio solo puede recuperar d con alta probabilidad.

Para probar si el circuito cuántico contribuye con señal más allá de este piso de ruido clásico, ejecutamos el desafío de 6 bits (n=31) con solo 8 disparos (muy por debajo del orden del grupo) 10 veces en ibm_kingston:

Resultado: 4/10 éxitos (40%) frente a una línea base de ruido clásico de ~20% (calculada mediante simulación Monte Carlo: 8 cadenas de bits aleatorias con (r-j)*k_inv mod 31 filtradas por verificación). Prueba binomial de una cola: P(X >= 4 | n=10, p=0.20) = 0.121, indicando una mejora de 2x sobre el piso de ruido. Aunque no es estadísticamente significativa individualmente a p < 0.05 (que requeriría 5+ éxitos), la tasa observada es consistente con una señal cuántica que contribuye aproximadamente 1-2 pares (j, k) adicionales válidos por ejecución más allá de lo que proporciona el azar.

Este resultado se sitúa entre el piso de ruido clásico y el régimen de ventaja cuántica teórica. En tamaños de curva más grandes donde n >> disparos, la línea base de ruido cae por debajo del 1% y cualquier recuperación exitosa de clave se convierte en evidencia sólida de computación cuántica.

Inicio Rápido```bash

git clone https://github.com/GiancarloLelli/quantum.git cd quantum

python -m venv . Scripts\Activate.ps1 # For Windows only

pip install -r requirements.txt

Opciones de CLI

Estructura del proyecto```

projecteleven.py # Shor solver — dense unitary approach + CLI entry point quantum_arithmetic.py # Efficient permutation decomposition + QFT arithmetic primitives quantum_oracle.py # Coordinate-based oracle + arithmetic oracle framework google_semiclassical.py # Google semiclassical PE — qubit-recycled phase estimation ripple_carry_shor.py # Ripple-carry modular addition oracle (CDKM) — best for 8-bit+ input_curves.json # Challenge curves (4-bit to 30-bit) problem/curves.py # Curve generation utility requirements.txt # qiskit, qiskit-ibm-runtime