Квантовый алгоритм дискретного логарифмирования на эллиптических кривых с эффективным по пространству сложением точек

Этот репозиторий содержит код на Qiskit для оценки ресурсов схем эффективного по пространству квантового модулярного обращения и аффинного сложения точек, используемых в контексте дискретного логарифмирования на эллиптических кривых.

Текущая кодовая база сосредоточена на трёх рабочих процессах:

рекурсивный подсчёт схемы модулярного обращения по частям с контрольными точками;
опциональная локальная NCT-шаблонная оптимизация схемы;
ресурсная оценка скомпилированной обёрнутой схемы аффинного сложения точек по блокам.

Структура репозитория

.
├── README.md
│
├── eea_model/: оригинальная классическая эталонная реализация EEA, используемая для прототипирования алгоритма и проверки корректности.
│
├── 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
Подсчитывает шаги EEA Algorithm-3 рекурсивно, с контрольными точками по частям.
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: строит обёрнутую схему аффинного сложения точек, соответствующую расписанию Fig.14.
quadratic_fig15_inplace_s835_fastdual_wrapped.py: строит структуру Fig.15 для деления и умножения на месте с EEA, умножением, измерением, сбросом и фазовой коррекцией с прямым управлением.
quadratic_modular_arithmetic.py: инструкции модульного сложения/вычитания, умножения, обратного умножения, удвоения и деления пополам, используемые счётчиком сложения точек.
quadratic_gidney_arithmetic.py: примитивы арифметики в стиле Гидни и помощники для измерения и прямого управления, используемые слоем квадратичной модульной арифметики.
quadratic_squ_minus.py: блок square-minus, используемый в расписании аффинного сложения точек.
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

Для более быстрой проверки сложения точек (smoke test):

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: необязательное переопределение количества шагов Algorithm-3; по умолчанию используется значение из eea.get_n_config(n).
--chunk-size: количество шагов Algorithm-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}. Он спроектирован как ограниченный счётчик с отказоустойчивостью: если оптимизация шага завершается по таймауту или вызывает исключение, этот шаг подсчитывается точно без шаблонных раундов и затем сохраняется в контрольной точке, так что итоговые подсчитанные значения остаются полными.

Полезные аргументы в дополнение к стандартным аргументам EEA:

--templates {small-nct,all-nct}: выбор библиотеки шаблонов.
--rounds: количество раундов шаблонной оптимизации.
--max-nct-segment-gates: максимальный размер обратимого сегмента, отправляемого на шаблонную оптимизацию.
--max-nct-segment-qubits: максимальное количество кубитов в сегменте.
--segment-timeout-s: таймаут для оптимизации отдельного сегмента.
--step-timeout-s: таймаут для всего шага Algorithm-3 перед откатом к неизменённому подсчёту.
--fallback-step-timeout-s: таймаут для точного запасного подсчёта.
--force: пересчитывать, даже если контрольные точки шагов/частей уже существуют.
--ignore-policy-mismatch: повторно использовать старые контрольные точки, даже если политика оптимизации отличается; в основном для отладки.

Оптимизированный рабочий процесс записывает контрольные точки на уровне шагов в:

<workdir>/steps/

и сводки на уровне частей в:

<workdir>/

Quantum-Algorithm-for-Elliptic-Curve-Discrete-Logarithms-with-Space-Efficient-Point-Addition

Популярное