可逆定点算术（Fixed-Point Arithmetic）

English · 简体中文

类别 C1 · 模块 oracq.algorithms.common.arithmetic · 阶段 V1

概述

定点格式下的可逆算术族：加、减、乘（以及取负、绝对值、除法、倒数、开方、比较与按位逻辑等）。定点数由 FixedFormat(width, fraction, signed) 描述——width 位字长、低 fraction 位为小数、signed 时最高位为补码符号位。输出采用 XOR 语义并附带两位 status 标志：status[0] 标记定义域失效（除零、负数开方），status[1] 标记结果越出字长（而非精度界内的舍入）；取整口径为向零舍入加模回绕（rounding = "toward_zero; modular_wrap"）。线路由布尔网络的 compute/XOR/uncompute 模式生成，全程无脏工作区。

接口与输入模型

FixedFormat(width=8, fraction=3, signed=True)
fixed_arithmetic(kind, fmt=DEFAULT_FIXED_FORMAT)

API 入口：FixedFormat、fixed_arithmetic

  • FixedFormat：要求 \(2 \le \text{width} \le 64\) 且 \(0 \le \text{fraction} < \text{width} - \text{signed}\)（小数位不占用符号位），违例抛 ValidationError；encode(value) / decode(value) 在实数与补码整数间换算。DEFAULT_FIXED_FORMAT 即默认的 (8, 3, 有符号)。

  • fixed_arithmetic(kind, fmt)：kind 取 add / sub / neg / abs / mul / div / reciprocal / sqrt / lt / eq / select / and / or / xor 之一，未知值抛 ValidationError；结果按 (kind, fmt) 以 lru_cache 缓存复用。

返回 Operation，寄存器为输入 a（一元 kind 只有 a；select 另有 1 位 select）加输出 out（lt / eq 为 1 位，其余 width 位）与 status: Bits(2)。本入口不消费 oracle 输入（CP：定点格式与操作种类直接参数化）。模块属性：

属性

含义

arithmetic_kind / fixed_width / fixed_fraction / fixed_signed

调用参数回显

rounding

"toward_zero; modular_wrap"

arithmetic_network

布尔网络 payload（原生执行入口使用）

实现要点

生成策略是先在布尔 SSA 上搭建经典组合逻辑（见布尔网络），再整体编译为可逆线路。有符号乘除走幅度域路线：两侧取绝对值，在加宽的幅度域完成乘（\(2n\) 位移位累加后取 [fraction:] 段）或带恢复余数的除法，再按异或出来的符号位回贴符号并取负；status[0] 由分母是否全零（或开方输入符号位）驱动，失效时输出 mux 到全零。溢出判据 status[1]：无符号加减用进位/借位，有符号加减用符号一致性判据（同号相加变号 / 异号相减变号），乘除与开方检查幅度是否侵入符号位。除法与倒数共用 1 / b 的除法核（倒数的分子固定为 \(2^{2f}\)）。

适用边界：结果在字长内截断并模回绕，status 位是调用方判断溢出的唯一途径；精度由 fraction 事先决定，线路内无增长字长的机制。

验证方案

类别 C1（精确离散语义，判定准则见 ../development/validation-plan.md §2）：作用算子须与经典求值逐点相等。三层证据：

  • 结构：tests/core/test_stage2.py:Stage2StructureTests——test_arithmetic_construction_and_basis 对全部 14 种 kind × FixedFormat(4, 1) 逐一检查：模块含私有工作区、程序 JSON 往返相等、Toffoli/U3/CZ 基导出只含三种基门且无 controlled_by。

  • 数值：Stage2StructureTests.test_gate_network_is_executable_small_example——无符号 2 位 add 在 a = 1, b = 2 上模拟，幅度精确集中在 (a, b, out, status) = (1, 2, 3, 0)；同一模块的 arithmetic_network payload 经 from_payload 复原后经典求值 evaluate(a=1, b=2) == {"out": 3, "status": 0}，电路与经典语义对拍。其余 kind 由结构见证与 payload 经典求值一致性覆盖，电路级数值对拍集中在 add 小实例。

  • 绑定：本算法无独立绑定见证（矩阵口径为 —）。真实后端上的原生执行（arithmetic_native_registry）另由 tests/integration/test_stage2_native.py:Stage2NativeTests 在 PySparQ 上与参考模拟器对拍（L4 冒烟，非矩阵口径）。

数值验证

实验设计（tests/verification/verify_arithmetic.py，产物 out/verification/arithmetic.json，20 案例）：原语算术走「OriginIR-ext 全振幅（1–8 bit）+ UniQC Circuit.to_matrix 幺正（3–4 bit）+ PySparQ RIR 宽寄存器（16/32/64 bit）」三条路径；定点编译函数（compile_function 的 Boolean SSA 降低）用叠加态一次穷举全部输入编码，对照独立经典语义逐分支核对；初等函数把「实现误差（对照模块属性 math_approximation 中的 Chebyshev 系数）」与「方法误差（系数多项式 vs 真函数）」分开报告。复现：PYTHONPATH=src <含 pysparq+uniqc 的解释器> tests/verification/verify_arithmetic.py。

案例

规模

路径

指标

add_const 叠加穷举

w=1..8 × 4 常量

originir-ext + reference/rir/adapter 对拍

max_error ≤ 1.2e-16

add_const 幺正

w=3/4

originir-ext + to_matrix

与经典置换矩阵逐元素差 = 0.0

add_const 宽寄存器

w=16/32/64 抽样基态

rir-pysparq

failures = 0；w=12 全叠加 max_error = 1.6e-17

xor/swap/受控算术

4+4+2 bit 结构化程序

四路径两两对拍

max_pairwise_deviation = 0.0

编译多项式 x*x+0.5

FixedFormat(4,1)/(6,2)/(8,3) 全域

rir-pysparq

无旗标输出误差 ≤ 1 量子（判据 2 量子）；status 越界集合与预测一致

编译 sin(x)（degree=3）

FixedFormat(8,4)，区间 [−1,1]

rir-pysparq

实现误差 0.055 ≤ 2 量子；方法误差 0.0453（信息性）；misflagged = 0

编译函数叠加对拍

FixedFormat(4,1) 全输入

四路径

max_pairwise_deviation = 0.0

已知缺口与计划阶段

无已知缺口（验证矩阵缺口列为 —），阶段 V1。

相关链接