Algorithme quantique pour les logarithmes discrets sur courbes elliptiques avec addition de points économe en espace

Ce dépôt contient du code Qiskit pour l'estimation des ressources des circuits quantiques économes en espace d'inversion modulaire et d'addition de points affine, utilisés dans le cadre des logarithmes discrets sur courbes elliptiques.

La base de code actuelle est centrée sur trois flux de travail :

1. le comptage récursif par blocs du circuit d'inversion modulaire ;
2. l'optimisation locale facultative par modèles NCT du circuit ;
3. l'estimation compilée bloc par bloc des ressources du circuit enveloppé d'addition de points affine.

---

Structure du dépôt

.
├── README.md
│
├── eea_model/: original classical EEA reference implementation used for algorithm prototyping and correctness validation.
│
├── run_eea_s835_fastdual_recursive_chunks_checkpoint.py
├── run_eea_s835_fastdual_recursive_chunks_checkpoint_nctopt.py
├── count_s835_fastdual_wrapped_point_addition_blocks_compiled.py
│
├── eea_circuit.py
├── eea_circuit_s835_fastdual.py
├── eea_circuit_s835_lowaux.py
├── eea_circuit_updated.py
├── under1000_eea_shared_s835_fastdual_wrapped.py
├── under1000_modular_arithmetic_base.py
│
├── point_addition_fig14_s835_fastdual_wrapped_quadratic.py
├── quadratic_fig15_inplace_s835_fastdual_wrapped.py
├── quadratic_gidney_arithmetic.py
├── quadratic_lazy_instruction.py
├── quadratic_modular_arithmetic.py
├── quadratic_squ_minus.py
│
├── ccx_recursive_block_counter.py
├── nct_template_segment_optimizer.py
│
├── test_eea_strict_main.py
└── test_point_addition_strict_main.py

Scripts d'entrée principaux

• run_eea_s835_fastdual_recursive_chunks_checkpoint.py
  Compte récursivement les étapes de l'algorithme 3 de l'EEA, par blocs avec points de contrôle.

• run_eea_s835_fastdual_recursive_chunks_checkpoint_nctopt.py
  Même flux de travail de comptage EEA, mais avec optimisation locale par modèles NCT.

• count_s835_fastdual_wrapped_point_addition_blocks_compiled.py
  Compte le circuit enveloppé d'addition de points en comptant récursivement les sous-blocs compilés réutilisables et en assemblant les composants arithmétiques répétés avec des multiplicités exactes.

Fichiers EEA

• eea_circuit_s835_fastdual.py: Implémentation principale du circuit EEA de production.
• eea_circuit_s835_lowaux.py: Routines d'assistance à faible nombre de qubits auxiliaires utilisées par l'implémentation principale.
• eea_circuit_updated.py: Blocs de construction EEA partagés et utilitaires récursifs de comptage des ressources.
• eea_circuit.py: Wrapper de rétrocompatibilité pour les tests.

Fichiers d'addition de points et d'arithmétique

• point_addition_fig14_s835_fastdual_wrapped_quadratic.py : construit le circuit enveloppé d'addition de points affine correspondant à l'ordonnancement de la Fig.14.
• quadratic_fig15_inplace_s835_fastdual_wrapped.py : construit la structure de division en place et de multiplication en place de la Fig.15 avec EEA, multiplication, mesure, réinitialisation (reset) et correction de phase par anticipation.
• quadratic_modular_arithmetic.py : instructions d'addition/soustraction modulaire, de multiplication, de multiplication inverse, de doublement et de division par deux utilisées par le compteur d'addition de points.
• quadratic_gidney_arithmetic.py : primitives arithmétiques de style Gidney et outils de mesure et d'anticipation (feed-forward) utilisés par la couche arithmétique modulaire quadratique.
• quadratic_squ_minus.py : bloc square-minus utilisé dans l'ordonnancement de l'addition de points affine.
• under1000_eea_shared_s835_fastdual_wrapped.py : wrapper EEA partagé et outil d'assistance utilisés par le circuit d'addition de points.
• under1000_modular_arithmetic_base.py : petits utilitaires partagés d'arithmétique modulaire.

Utilitaires de comptage et d'optimisation

• ccx_recursive_block_counter.py : compteur récursif pour les circuits Qiskit, avec des politiques d'expansion MCX et d'expansion SWAP.
• nct_template_segment_optimizer.py : optimiseur local basé sur des modèles pour les segments {X, CX, CCX}.

---

Prérequis

Environnement recommandé :

• Python 3.10+
• Qiskit

Installez la dépendance principale avec :

python -m pip install --upgrade pip
python -m pip install qiskit

---

Démarrage rapide

Exécutez la suite de tests :

python test_eea_strict_main.py
python test_point_addition_strict_main.py

Pour un test de fumée plus rapide de l'addition de points :

python test_point_addition_strict_main.py --skip-n256 --skip-report

---

1. Comptage récursif par blocs de l'EEA

Le point d'entrée standard du comptage EEA est :

python run_eea_s835_fastdual_recursive_chunks_checkpoint.py \
  --n 192 \
  --chunk-size 25 \
  --measurement-uncompute \
  --resume \
  --workdir eea_s835_fastdual_chunks25 \
  --out eea_s835_fastdual_algorithm3_recursive_chunks_n192_measurement.json

Arguments importants :

• --n : largeur en bits.
• --T-max : remplacement facultatif du nombre d'étapes de l'algorithme 3 ; par défaut, la valeur de eea.get_n_config(n) est utilisée.
• --chunk-size : nombre d'étapes de l'algorithme 3 comptées par bloc de point de contrôle.
• --aux-size : remplacement facultatif du pool de qubits auxiliaires ; s'il est omis, la taille du registre auxiliaire de la disposition est calculée automatiquement.
• --measurement-uncompute : active la décomputation basée sur la mesure dans les blocs EEA comptés.
• --resume : réutilise les fichiers JSON de blocs non vides existants dans --workdir.
• --workdir : répertoire des fichiers de point de contrôle par bloc.
• --out : résumé JSON cumulatif écrit après chaque bloc.

Le script écrit des fichiers par bloc, par exemple :

eea_s835_fastdual_chunks25/eea_s835_fastdual_n192_T0001_0025.json

ainsi qu'un JSON de sortie cumulatif contenant des champs tels que :

mode
n
T_max
num_qubits
len_width
shift_width
aux_size
measurement_based
ops
chunks
elapsed_s_so_far

---

2. Comptage EEA avec optimisation par modèles NCT

Le point d'entrée du comptage optimisé est :

python run_eea_s835_fastdual_recursive_chunks_checkpoint_nctopt.py \
  --n 128 \
  --chunk-size 25 \
  --measurement-uncompute \
  --templates small-nct \
  --rounds 1 \
  --max-nct-segment-gates 40 \
  --segment-timeout-s 10 \
  --timeout-mode auto \
  --resume \
  --workdir eea_s835_fastdual_chunks_nctopt_failopen_r1_128_seg40_to10 \
  --out eea_s835_fastdual_algorithm3_recursive_chunks_n128_measurement_nctopt_failopen_r1_seg40_to10.json

Ce flux de travail tente une optimisation locale par modèles sur les segments {X, CX, CCX}. Il est conçu comme un compteur fail-open borné : si une étape optimisée expire ou lève une exception, cette étape est comptée exactement, sans rondes de modèles, puis enregistrée dans un point de contrôle ; les comptes finaux rapportés restent ainsi complets.

Arguments utiles en plus des arguments EEA standard :

• --templates {small-nct,all-nct} : sélection de la bibliothèque de modèles.
• --rounds : nombre de rondes d'optimisation par modèles.
• --max-nct-segment-gates : taille maximale d'un segment réversible envoyé à l'optimisation par modèles.
• --max-nct-segment-qubits : nombre maximal de qubits dans un segment.
• --segment-timeout-s : délai d'expiration (timeout) pour l'optimisation d'un segment individuel.
• --step-timeout-s : délai d'expiration pour une étape entière de l'algorithme 3 avant de revenir au comptage sans modification.
• --fallback-step-timeout-s : délai d'expiration pour le comptage de repli exact.
• --force : force le recalcul même si les points de contrôle d'étapes/blocs existent déjà.
• --ignore-policy-mismatch : réutilise les anciens points de contrôle même lorsque la politique d'optimisation diffère ; principalement pour le débogage.