خوارزمية كمومية للوغاريتمات المتقطعة على المنحنيات الإهليلجية مع جمع نقاط موفِّر للمساحة

يحتوي هذا المستودع على كود Qiskit لتقدير الموارد لدوائر المعكوس المعياري الكمومي الموفرة للمساحة ودوائر جمع النقاط الأفينية المستخدمة في سياقات اللوغاريتمات المتقطعة على المنحنيات الإهليلجية.

ترتكز قاعدة الكود الحالية على ثلاثة مسارات عمل:

1. العد التكراري المجزّأ لدائرة المعكوس المعياري؛
2. التحسين المحلي الاختياري للدائرة باستخدام قوالب NCT؛
3. تقدير الموارد المجمَّع على مستوى الكتل لدائرة جمع النقاط الأفينية المغلفة.

بنية المستودع

.
├── 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

سكربتات الإدخال الرئيسية

• run_eea_s835_fastdual_recursive_chunks_checkpoint.py
  يعدّ خطوات الخوارزمية 3 لـ EEA بشكل تكراري، في أجزاء بنقاط حفظ.

• run_eea_s835_fastdual_recursive_chunks_checkpoint_nctopt.py
  نفس مسار عمل عد EEA، لكن مع تحسين محلي باستخدام قوالب NCT.

• count_s835_fastdual_wrapped_point_addition_blocks_compiled.py
  يعدّ دائرة جمع النقاط المغلفة عبر العد التكراري للكتل الفرعية المجمَّعة القابلة لإعادة الاستخدام وتجميع المكونات الحسابية المتكررة بأعداد تكرار مضبوطة.

ملفات EEA

• eea_circuit_s835_fastdual.py: التنفيذ الرئيسي لدائرة EEA الإنتاجية.
• eea_circuit_s835_lowaux.py: روتينات مساعدة منخفضة الكيوبتات الإضافية يستخدمها التنفيذ الرئيسي.
• eea_circuit_updated.py: اللبنات المشتركة لدائرة EEA وأدوات العد التكراري للموارد.
• eea_circuit.py: غلاف توافق رجعي للاختبارات.

ملفات جمع النقاط والحساب

• point_addition_fig14_s835_fastdual_wrapped_quadratic.py: يبني دائرة جمع النقاط الأفينية المغلفة المطابقة لجدول الشكل 14.
• quadratic_fig15_inplace_s835_fastdual_wrapped.py: يبني بنية القسمة الموضعية والضرب الموضعي للشكل 15 مع EEA والضرب والقياس وإعادة الضبط وتصحيح الطور بالتغذية الأمامية.
• quadratic_modular_arithmetic.py: تعليمات الجمع/الطرح المعياري والضرب والضرب العكسي والمضاعفة والتنصيف المستخدمة بواسطة عداد جمع النقاط.
• quadratic_gidney_arithmetic.py: الأوليات الحسابية بأسلوب Gidney ومساعدات القياس والتغذية الأمامية المستخدمة بواسطة طبقة الحساب المعياري التربيعي.
• quadratic_squ_minus.py: كتلة التربيع-الطرح المستخدمة في جدول جمع النقاط الأفينية.
• under1000_eea_shared_s835_fastdual_wrapped.py: غلاف EEA المشترك والأداة المساعدة المستخدمة بواسطة دائرة جمع النقاط.
• under1000_modular_arithmetic_base.py: أدوات صغيرة مشتركة للحساب المعياري.

أدوات العد والتحسين

• ccx_recursive_block_counter.py: عداد تكراري لدوائر Qiskit، مع سياسات لتوسيع MCX وتوسيع SWAP.
• nct_template_segment_optimizer.py: محسِّن محلي قائم على القوالب لمقاطع {X, CX, CCX}.

المتطلبات

البيئة الموصى بها:

• Python 3.10+
• Qiskit

ثبّت الاعتماد الرئيسي باستخدام:

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

بدء سريع

شغّل مجموعة الاختبارات:

python test_eea_strict_main.py
python test_point_addition_strict_main.py

لإجراء اختبار إقلاع أسرع لجمع النقاط:

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

1. العد التكراري المجزّأ لـ EEA

نقطة الدخول القياسية لعد EEA هي:

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

الوسائط المهمة:

• --n: عرض البت.
• --T-max: تجاوز اختياري لعدد خطوات الخوارزمية 3؛ افتراضيًا تُستخدم القيمة من eea.get_n_config(n).
• --chunk-size: عدد خطوات الخوارزمية 3 المعدودة لكل جزء بنقطة حفظ.
• --aux-size: تجاوز اختياري لمجموعة كيوبتات المساعدة؛ إذا حُذف، يُحسب حجم مساعدة التخطيط تلقائيًا.
• --measurement-uncompute: يفعّل إلغاء الحساب القائم على القياس في كتل EEA المعدودة.
• --resume: يعيد استخدام ملفات JSON غير الفارغة الموجودة للأجزاء في --workdir.
• --workdir: دليل ملفات نقاط الحفظ لكل جزء.
• --out: ملخص JSON التراكمي المكتوب بعد كل جزء.

يكتب السكربت ملفات لكل جزء مثل:

eea_s835_fastdual_chunks25/eea_s835_fastdual_n192_T0001_0025.json

وملف إخراج JSON تراكمي يحتوي على حقول مثل:

mode
n
T_max
num_qubits
len_width
shift_width
aux_size
measurement_based
ops
chunks
elapsed_s_so_far

2. عد EEA مع تحسين قوالب NCT

نقطة الدخول للعد المحسَّن هي:

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

يحاول مسار العمل هذا إجراء تحسين محلي بالقوالب على مقاطع {X, CX, CCX}. وهو مصمم كعداد fail-open محدود: إذا انتهت مهلة خطوة محسَّنة أو أثارت استثناءً، تُعدّ تلك الخطوة بدقة دون جولات قوالب ثم تُحفظ كنقطة حفظ، بحيث تبقى الأعداد النهائية المبلغ عنها كاملة.

وسائط مفيدة إضافة إلى وسائط EEA القياسية:

• --templates {small-nct,all-nct}: اختيار مكتبة القوالب.
• --rounds: عدد جولات تحسين القوالب.
• --max-nct-segment-gates: الحد الأقصى لحجم المقطع القابل للعكس المرسل إلى تحسين القوالب.
• --max-nct-segment-qubits: الحد الأقصى لعدد الكيوبتات في المقطع.
• --segment-timeout-s: المهلة الزمنية لتحسين المقطع الفردي.
• --step-timeout-s: المهلة الزمنية لخطوة الخوارزمية 3 كاملة قبل التراجع إلى العد غير المحسَّن.
• --fallback-step-timeout-s: المهلة الزمنية لعد الرجوع الدقيق.
• --force: إعادة الحساب حتى لو كانت نقاط حفظ الخطوات/الأجزاء موجودة بالفعل.
• --ignore-policy-mismatch: إعادة استخدام نقاط الحفظ القديمة حتى عندما تختلف سياسة التحسين؛ هذا أساسًا للتنقيح.

يكتب مسار العمل المحسَّن نقاط حفظ على مستوى الخطوات تحت:

<workdir>/steps/

وملخصات على مستوى الأجزاء تحت:

<workdir>/

3. العد المجمَّع على مستوى الكتل لجمع النقاط المغلفة

يعتمد عداد جمع النقاط على ملف JSON لخوارزمية EEA 3 ناتج عن أحد مسارات عمل EEA أعلاه. يجب أن تطابق قيمة --n لعداد جمع النقاط حقل n في ملف JSON الخاص بـ EEA.

مثال لـ n=64:

python run_eea_s835_fastdual_recursive_chunks_checkpoint.py \
  --n 64 \
  --chunk-size 25 \
  --measurement-uncompute \
  --resume \
  --workdir eea_s835_fastdual_chunks25_n64 \
  --out eea_s835_fastdual_algorithm3_recursive_chunks_n64_measurement.json

ثم شغّل:

python count_s835_fastdual_wrapped_point_addition_blocks_compiled.py \
  --n 64 \
  --eea-steps-json eea_s835_fastdual_algorithm3_recursive_chunks_n64_measurement.json \
  --out point_addition_s835_fastdual_wrapped_blocks_compiled_counts_n64.json

مثال لمخرجات EEA المحسَّنة لـ n=128:

python count_s835_fastdual_wrapped_point_addition_blocks_compiled.py \
  --n 128 \
  --eea-steps-json eea_s835_fastdual_algorithm3_recursive_chunks_n128_measurement_nctopt_failopen_r1_seg40_to10.json \
  --out point_addition_s835_fastdual_wrapped_blocks_compiled_counts_n128.json

الوسائط المهمة:

• --n: عرض البت.
• --p: المعامل؛ الافتراضي هو العدد الأولي لمنحنى secp256k1.
• --s-qubits: تجاوز اختياري لحجم سجل الحساب المشترك لـ EEA.
• --point-constant {secp256k1-generator,zero,custom}: اختيار ثابت النقطة لتحديثات الإحداثيات الثابتة للشكل 14.
• --x2, --y2: إحداثيات نقاط مخصصة؛ مطلوبتان عند استخدام --point-constant custom.
• --eea-steps-json: ملف JSON يحتوي على أعداد EEA التكرارية للخوارزمية 3.
• --allow-eea-n-mismatch: تجاوز خاص بالتنقيح فقط يسمح بأن يختلف n في JSON الخاص بـ EEA عن القيمة المطلوبة في --n.
• --mcx-policy {clean-vchain,keep}: سياسة توسيع MCX للعد التكراري.
• --validate-full-mul: لـ صغيرة، عدّ تعريفات الضرب/التربيع الكاملة بشكل تكراري وقارنها بأعداد الكتل المجمَّعة.

يتضمن تقرير الإخراج:

counting_mode
n
p
point_constant_kind
qiskit_width_report
eea_meta
block_summaries
raw_block_counters
key_ccx
validation
elapsed_s

يبني عداد جمع النقاط دوائر Qiskit قابلة لإعادة الاستخدام، ويعدّها بشكل تكراري في الأساس {CCX, CX, X}، ثم يجمع كتلًا متكررة أكبر مثل الضرب، والضرب العكسي، والقسمة الموضعية، والضرب الموضعي، والتربيع-الطرح، وكتلة جمع النقاط الكلية للشكل 14.

الاختبارات

يتضمن هذا المستودع سائقَي اختبار بسيطين بلغة Python. كُتبا عمدًا دون pytest أو Aer أو محاكاة كاملة لمتجه الحالة. توسّع الاختبارات تعريفات Qiskit بشكل تكراري حيثما كان ذلك مناسبًا وتحاكي حالات الأساس الحسابي لكتل شبكات Toffoli.

اختبارات EEA الصارمة

توجد اختبارات EEA في:

test_eea_strict_main.py

شغّل مجموعة اختبارات EEA الافتراضية باستخدام:

python test_eea_strict_main.py

تتحقق المجموعة الافتراضية من:

• أن التنفيذ ليس اختصارًا لنقاط النهاية عند n صغيرة؛
• وجود جدول الكتل المتقطعة للخوارزمية 3؛
• صيغ النافذة النشطة عبر عدة عروض صغيرة؛
• التكرار الأحادي، والإزاحة قبل/بعد، وتحديث الطور، والتبديل المتحكم به بالموقع، وكتل تحديث الطول؛
• نقاط نهاية الخوارزمية 3 للأعداد الأولية الافتراضية 3, 5, 7, 11, 13, 17، باستخدام كل من أعداد الخطوات الدقيقة وT_max الثابتة؛
• غلاف الخوارزمية 1 الكامل للأعداد الأولية الصغيرة الافتراضية 3, 5, 7.

نسخ مفيدة:

# Fast structural + block tests only.
python test_eea_strict_main.py --skip-endpoint --skip-alg1

# Include the heavier PDF/Table-4 p=37, x=13 trace benchmark.
python test_eea_strict_main.py --table4

# Test all x values for primes above 13 as well.
python test_eea_strict_main.py --primes 3 5 7 11 13 17 --mid-all-x --verbose

اختبارات جمع النقاط الصارمة

توجد اختبارات جمع النقاط في:

test_point_addition_strict_main.py

شغّل مجموعة اختبارات جمع النقاط الافتراضية باستخدام:

python test_point_addition_strict_main.py

تتحقق مجموعة اختبارات جمع النقاط الافتراضية من:

• تخطيط سجلات جمع النقاط المغلفة؛
• متطابقة العرض n=256 وهي 835 = 1 + 3*256 + 66؛
• ترتيب العمليات عالي المستوى للشكل 14/الشكل 15؛
• بنية الدائرة الديناميكية الصريحة التي تتضمن عمليات H وmeasure وreset وZ المتحكم بها كلاسيكيًا وswap؛
• تجميع الكتل الفرعية الحسابية المجمَّعة لمعامل صغير؛
• تقرير عداد جمع نقاط متكامل صغير يستخدم JSON اصطناعيًا للخوارزمية 3، بحيث يُختبر مسار التقرير دون تشغيل عد EEA كبير.

تغطي مصفوفة اختبارات الانحدار للأعداد الأولية الكبيرة أزواجًا تمثيلية من عرض بت الحقل n والمعامل الأولي p، بدءًا من الحقول الأولية بعرض 12 بت حتى 512 بت. تشمل الحالات المختبرة، على سبيل المثال، n=16, p=65521 وn=32, p=4294967291 والعدد الأولي لمنحنى secp256k1 عند n=256، وأعدادًا أولية تمثيلية عند n=128, 160, 192, 224, 384, 512.

لكل زوج (n,p)، تتضمن الاختبارات تتبعات EEA حدية ومتناظرة وعشوائية وطويلة نسبيًا. يُشغَّل التجميع الحسابي المجمَّع الكامل فقط لحالات مختارة متوسطة العرض، بينما تُستخدم أزواج (n,p) الأكبر للتحقق من بناء الدائرة وتخطيط السجلات والجدولة ومسارات العد التكراري للموارد.

نسخ مفيدة:

# Skip the tiny integrated report and only check construction/schedule/assembly.
python test_point_addition_strict_main.py --skip-report

# Fast smoke test that also skips the n=256 width construction check.
python test_point_addition_strict_main.py --skip-n256 --skip-report

# Use a different small prime/width for compiled-block validation.
python test_point_addition_strict_main.py --n 5 --p 17

إذا لم يكن Qiskit مثبتًا، يطبع test_point_addition_strict_main.py رسالة تخطي وينتهي بنجاح. يتطلب اختبار EEA الصارم Qiskit لأنه يبني بوابات كتل EEA/PDF.

إعادة إنتاج الإحصاءات الرئيسية

تورد ورقتنا نتائج تقدير الموارد العددية لـ:

n = 64, 128, 160, 192, 224, 256, 384, 512

مسار العمل النموذجي هو:

1. تشغيل عداد الخوارزمية 3 لـ EEA لقيمة n معينة؛
2. تشغيل النسخة المحسَّنة بـ NCT اختياريًا لنفس قيمة n؛
3. تمرير ملف JSON الناتج لـ EEA إلى عداد جمع النقاط المغلفة؛
4. جمع الحقول key_ccx وblock_summaries وqiskit_width_report من تقرير الإخراج.

بالنسبة للعروض الكبيرة، استخدم --resume واحتفظ بدلائل --workdir، لأن نقاط حفظ الأجزاء والخطوات مصممة لدعم التشغيل الطويل المتقطع.

الاستشهاد

إذا استخدمت قاعدة الكود هذه في بحثك، يرجى الاستشهاد بما يلي:

@misc{luo2026quantumalgorithmellipticcurve,
      title={Quantum Algorithm for Elliptic Curve Discrete Logarithms with Space-Efficient Point Addition}, 
      author={Han Luo and Ziyi Yang and Jingquan Luo and Ziruo Wang and Yuexin Su and Xiaoming Sun and Lvzhou Li and Tongyang Li},
      year={2026},
      eprint={2607.13816},
      archivePrefix={arXiv},
      primaryClass={quant-ph},
      url={https://arxiv.org/abs/2607.13816}, 
}