Modular Multiplication

English · 简体中文

Category C1 · Module oracq.algorithms.basics.number_theory · Stage —

Overview

Given a multiplier \(a\) coprime with the modulus \(m\), implement the reversible map on a \(w\)-bit register

\[\begin{split} U_{a,m}\,|x\rangle = \begin{cases} |a \cdot x \bmod m\rangle, & x < m,\\ |x\rangle, & x \ge m, \end{cases} \end{split}\]

that is, a finite-size version of the modular-multiplication unitary required by Shor order finding. It is the underlying building block of order finding; see that page for classical factor post-processing.

Interface and input model

modular_multiply(multiplier, modulus, *, width=None, max_width=8)

API entry point: modular_multiply

• multiplier: a positive integer coprime with modulus (input model CP; multiplier and modulus are given directly as classical parameters, no oracle input).

• modulus: the modulus, at least 2.

• width: the target bit width; when omitted, the smallest bit width that can hold modulus - 1.

• max_width: the permutation synthesis budget, default 8, at most 12.

Returns an Operation with register target: Bits(width). Module attributes:

Attribute	Meaning
algorithm	"modular_multiply"
implementation_scope	"bounded permutation synthesis"
modulus	echo of the call parameters

Implementation notes

The generation strategy enumerates the full permutation on the \(2^w\) basis states, decomposes it into disjoint cycles, and synthesizes pairwise transpositions (_transposition), so the action on any basis state agrees pointwise with the definition. The multiplier is reduced modulo the modulus at generation time; modulus > 2^width or \(\gcd(a, m) \neq 1\) raises ValidationError directly.

Applicability boundary: the number of enumerated permutations grows exponentially with the bit width; the max_width default of 8 and cap of 12 is a deliberate synthesis budget. The current modular multiplication uses capped permutation synthesis, at most 8 bits by default; it is used to check the order-finding interface and circuits and does not represent implemented scalable Shor modular arithmetic (following the established wording of the algorithm catalog page). Scenarios that need large-scale modular arithmetic should switch to scalable constructions, which this module does not provide.

Validation approach

Category C1 (exact discrete semantics; acceptance criteria in ../../development/validation-plan.md §2): the acting unitary must equal the truth table pointwise. Evidence:

• Structure: construction and property assertions of tests/core/test_algorithm_expansion.py:AlgorithmExpansionTests; test_bad_inputs_fail_at_generation covers generation-time violations such as a multiplier not coprime with the modulus (modular_multiply(2, 4)).

• Numerical: AlgorithmExpansionTests.test_modular_multiplication_total_permutation_and_order — for modular_multiply(2, 5) (bit width 3) all 8 basis states are enumerated, verifying pointwise that \(x<5\) maps to \(2x\bmod 5\) and \(x\ge 5\) is unchanged, with the target basis-state amplitude exactly 1.

• Binding: this algorithm has no separate binding witness (no open declaration entry point).

Known gaps and planned stages

Gap per the validation-matrix wording: the small-scale witnesses are explicitly noted as not extrapolable to full Shor (preserving the original wording); scalable modular-arithmetic constructions are not implemented. The stage is listed as — (not in any of the V1–V4 tiers).

Related links

• Same module: order finding and factor post-processing

• Source: src/oracq/algorithms/basics/number_theory.py

• API reference: Modular multiplication and order finding

• Validation matrix: Validation coverage matrix

Numerical validation

Paper-grade numerical experiments are in tests/verification/verify_nt_qlss_sde.py (nt_qlss_sde group), all executed on real backends; the classical oracle is independent number-theoretic permutation ground truth (\(x \mapsto ax \bmod m\) for \(x<m\), other basis states unchanged), not going through any helper of the implementation under test.

Experimental design: (a) For 5 instances \((a, m) \in \{(2,5), (3,5), (2,7), (2,9), (7,100)\}\) (bit widths 3–7), a superposition state (H on target, then the modular multiplication) exhausts all \(2^w\) basis-state inputs in a single run, and the output is cross-checked amplitude by amplitude against the uniform superposition relabeled by the classical permutation; the paths are reference, rir-pysparq, adapter-pysparq, and OriginIR-ext (UniQC full-amplitude state vector, workspace 0). (b) For \((2,5)\), an OriginIR-ext Circuit.to_matrix full-unitary check: the effective block after workspace uncomputation must equal the classical permutation matrix, and the leakage into the workspace is zero.

Key metrics:

Case	Scale	Path	max_error
modmul-superposition-2-5 / 3-5 / 2-7	\(2^3\) basis states, exhaustive	four paths	5.6e-17
modmul-superposition-2-9	\(2^4\) basis states, exhaustive	four paths	8.3e-17
modmul-superposition-7-100	\(2^7\) basis states, exhaustive	four paths	4.2e-17
modmul-unitary-2-5	\(8 \times 8\) full unitary	originir-ext + to_matrix	0.0 (leakage 0.0)

Reproduce:

PYTHONPATH=src /home/agony/projects/qcfd-dev/quantum-cfd-software/.venv/bin/python tests/verification/verify_nt_qlss_sde.py

Output: out/verification/nt_qlss_sde.json (modmul-*, 6 cases in total).