giancarlolelli/quantumCe dépôt contient le code et les détails de soumission pour le défi du prix QDay par https://www.projecteleven.com/
Solveur quantique pour le problème du logarithme discret sur courbe elliptique (ECDLP), construit pour le Q-Day Prize Challenge par Project Eleven. L'objectif : récupérer des clés privées ECC sur du matériel quantique réel en utilisant l'algorithme de Shor.
Toutes les courbes du défi utilisent y^2 = x^3 + 7 sur F_p (a = 0, b = 7), correspondant à la famille secp256k1. Le solveur implémente la variante à deux registres de l'algorithme de Shor pour l'ECDLP :
La clé privée d est récupérée en collectant plusieurs échantillons (j, k) qui satisfont la même relation linéaire modulo l'ordre du groupe n. Le solveur prend en charge six stratégies d'oracle pour les additions de points contrôlées, sélectionnées automatiquement en fonction de la taille de la courbe ou manuellement via --oracle.
Utilisée pour les courbes avec un ordre de groupe jusqu'à ~6 bits. Implémentée dans projecteleven.py.
Chaque addition de point contrôlée "add S" est représentée comme une matrice de permutation 2^(n+1) x 2^(n+1) appliquée via qc.unitary(). La matrice encode l'action complète du groupe : le bloc supérieur gauche est l'identité (contrôle=0), le bloc inférieur droit permute les états de base selon l'application P -> P+S (contrôle=1).
Utilisée pour les courbes plus grandes. Implémentée dans quantum_arithmetic.py.
Au lieu de construire des matrices denses, chaque permutation "add S" est décomposée en cycles, puis en transpositions. Chaque transposition (échange de deux états de base |a> <-> |b>) est implémentée avec :
Le MCX utilise une décomposition en chaîne en V avec (n-2) qubits ancilla dédiés, donnant O(n) portes Toffoli par MCX au lieu de O(n^2) sans ancillas. Chaque addition contrôlée est construite comme un sous-circuit isolé et ajoutée comme une porte opaque unique, évitant une croissance quadratique du DAG dans Qiskit.
--oracle coordinate)Disponible pour les courbes jusqu'à ~6 bits. Implémentée dans quantum_oracle.py.
Au lieu d'encoder les points comme des indices de groupe, le registre quantique contient les coordonnées de champ (x, y) réelles en binaire plus un indicateur d'identité. La disposition du registre de points est :
x_reg : f_bits qubits (f_bits = ceil(log2(p)))y_reg : f_bits qubitsid_flag : 1 qubit (1 = point à l'infini)Chaque "add S" contrôlé est calculé à partir de la formule d'addition EC sur tous les encodages de coordonnées valides, produisant une permutation sur le registre de coordonnées. Cette permutation est décomposée en cycles puis en transpositions en utilisant la même infrastructure de réduction CNOT + MCX que la Stratégie 2.
--oracle arithmetic)Cadre pour l'addition de points à mise à l'échelle polynomiale. Implémentée dans quantum_oracle.py et quantum_arithmetic.py.
Utilise l'encodage par coordonnées (identique à la Stratégie 3) avec des primitives arithmétiques modulaires basées sur la QFT comme éléments de base pour l'addition de points entièrement arithmétique. La base de code comprend des implémentations testées de :
Les primitives arithmétiques atteignent une mise à l'échelle O(n^3) par addition de point contre O(N*n) pour l'approche par permutation. Cependant, les opérations basées sur la QFT ont un facteur constant environ 150 fois plus grand, rendant l'approche arithmétique plus efficace uniquement pour les courbes au-delà de ~20 bits d'ordre de groupe. Pour les tailles de défi actuelles (jusqu'à 12 bits), l'additionneur par permutation reste plus rapide et est utilisé par défaut.
--oracle google)Implémentée dans google_semiclassical.py. Inspirée de la technique d'estimation de phase à recyclage de qubits de Griffiths & Niu (1996), appliquée à grande échelle dans Babbush et al. (2026) pour les estimations de ressources ECDLP secp256k1. L'article de Babbush et al. a été publié le 30 mars 2026.
Remplace les deux registres de comptage multi-qubits (j, k) et la QFT inverse globale par deux qubits recyclés uniques et des corrections de phase conditionnées classiquement. Chaque bit du registre de comptage est traité séquentiellement : préparer en |+>, appliquer l'addition de point contrôlée, corriger la phase en fonction de tous les bits précédemment mesurés, puis mesurer. Les primitives de circuit dynamique reset + if_test dans Qiskit permettent cela sur le matériel IBM Quantum.
L'oracle pour les additions de points contrôlées est délégué à l'infrastructure existante (unitaire dense pour <= 6 bits, permutation efficace pour > 6 bits), donc les économies de qubits proviennent entièrement de la suppression des registres de comptage.