量子算法实现验证计划（审阅稿）

English · 简体中文

本文档系统规划 oracq 的算法验证体系：先按"正确的判定方式"对全部算法分类，再为每一类规定标准见证技术，最后给出全算法验证矩阵与实施路线。审阅重点：第 2 节的分类是否完整、第 4 节的横切机制是否值得作为基础设施投入、第 5 节的阶段划分与优先级。

1. 验证总原则

  • 验证对象是 RIR 程序的语义。算法是生成器，见证必须作用在生成的程序上（经参考模拟器或真实后端执行），而不是作用在生成器的内部数据结构上。

  • 每个算法至少三层证据：结构合法（IR 校验、签名、契约属性）、小规模数值见证（参考模拟器对拍解析解或经典参考）、可绑定性（抽象声明经 bind 绑定后语义不变）。

  • input model 三层一致性是本仓库的特有不变量：同一算法的 abstract / gate / qram 绑定必须产生一致的可观察语义（允许 QRAM 字宽量化误差，需给出误差界）。

  • 确定性优先：概率性断言必须落在分布层面（闭式期望、支撑集、矩），禁止单一样本阈值断言；模拟必须使用固定种子或精确态矢量。

  • 现有层级保持：L0 静态检查（ruff、布局、文档 warning-as-error）→ L1 结构 → L2 数值见证（tests/core）→ L3 对拍目录（applications/catalog.py）→ L4 真实后端（tests/integration，uniqc/pysparq 真机对拍，不用 mock）→ L5 文档 doctest。

2. 算法分类（按"正确"的判定方式）

类别

判定准则

标准见证技术

主要风险

C1 精确离散语义

输出分布/作用酉与真值表或精确构造逐点相等

穷举小实例全输入对拍；酉性恒等式 W†W=I；零空间/秘密串精确恢复

基本无 flaky

C2 近似连续语义

作用算子 ≈ 目标连续函数，误差有显式上界

与经典参考（解析解/矩阵指数/高精度数值）在容差内比较；收敛性扫描：误差 vs 度数/κ/Δt 拟合理论率

容差选取掩盖系统误差；数值病态（如 QSP 高阶合成）

C3 概率分布语义

输出分布等于闭式期望（均值、方差、支撑集）

精确态矢量求分布，逐结果概率对拍闭式（Krawtchouk/二项等）；QAE 类验证估计值落在理论置信区间

采样抖动 → 禁止样本断言，只用精确分布

C4 启发式/优化语义

严格优于随机基线，且小实例达到已知最优/理论分数

与随机猜测期望的分布级比较；小实例穷举最优解对拍；理论分数公式对拍

边界断言抖动（C3 类 DQI 已发生一次：恰好等于基线时 assertGreater 失败）

C5 数据访问层

查询语义逐点正确 + 三层绑定一致 + 复净

逐地址真值表对拍；abstract/gate/qram 三绑定一致性；LocalExit 强制复净检查；叠加态查询边缘分布检查

QRAM 量化误差需显式误差界

C6 组合骨架

组件契约满足 + 端到端小实例语义正确 + bind 不变

端到端模拟 + 绑定前后结果一致 + 结构属性（寄存器布局、Repeat 不展开）检查

组件各自正确但组合语义错位（寄存器映射错误）

3. 全算法验证矩阵

状态：✅ 已有充分见证；🟡 有见证但有缺口；❌ 缺见证。模块按分层列出。

infrastructure / 数据访问层（C5）

模块

内容

状态

缺口与计划

oracles.py

XorDatabase、StatePreparation、SparseAccess、BlockEncoding 三层

✅

补"三绑定一致性"参数化测试（同一声明逐绑定对拍），目前各绑定独立见证

data_loading.py

QROM / Select-Swap

✅

资源公式已对拍；建议把 qrom_cost 纳入目录报告属性

mathfunc/

经典函数→可逆线路

✅

补定点量化误差界的显式见证

prepare_select.py

PREPARE/SELECT、alias

✅

alias 的 clean_work=False 已诚实标注；补 alias 三绑定一致性

精确离散算法（C1）

模块

算法

状态

缺口与计划

oracle_algorithms.py

DJ/BV/Simon

✅

—

fourier.py

QFT、QFT 加法

✅

—

arithmetic.py

定点加减乘、布尔网络

✅

—

number_theory.py

模乘、order finding

✅

小规模见证已注明不可外推为完整 Shor

error_correction.py

重复码

✅

—

walks.py

coined cycle walk

✅

—

graph_walks.py

邻接 oracle、Szegedy、MNRS

✅

环的失败已证实为理论结果；补 Johnson 图后需新见证（element distinctness）

近似连续算法（C2）

模块

算法

状态

缺口与计划

transforms.py

qubitization walk、QSVT 序列、OAA

✅

序列约定已由 qsvt.py 钉死（逐点一致 1e-10）

qsvt.py

相位合成、求逆、过滤、HS 模拟、定点搜索

✅

收敛性扫描缺失：误差 vs 度数/κ 的批量曲线未自动化；合成度数病态边界（≳16）已有负例覆盖：tests/core/test_qsvt.py:PhaseSynthesisTests.test_input_validation 与 TransformWitnessTests.test_transform_input_validation（含奇偶性违例、

hamiltonian.py

Trotter、Taylor、hamsim

✅

Trotter 阶数误差率未做扫描

sparse.py / block_encoding.py

稀疏 BE、BE 代数

✅

—

qlss.py

CKS、Costa

🟡

有范式见证；缺与 HHL 论文参考值的端到端对拍案例（可入目录）

ode.py / lchs.py / cbmd.py / schrodingerization.py / carleman.py

ODE/PDE 求解器

🟡

各自有见证；缺统一的"解析可解 ODE 族"收敛性基准（同一问题过全部求解器）

sde.py

Fokker–Planck

✅

OU 矩对拍；补 SDE 求解器与 LCHS 的端到端目录案例

density.py

纯化、Gibbs

✅

收敛扫描已补：tests/core/test_density.py:GibbsTests.test_error_convergence_decreases（error ∈ {0.4,0.2,0.1} 单调不增+每档≤error，实测 5.6e-4/8.7e-5/8.7e-5）与 test_error_bound_uniform_in_beta（β ∈ {0.2,0.5,1.0} 网格每点 ≤0.1）

lowrank.py

DF/THC → BE

✅

α 上界紧性已补：tests/core/test_lowrank.py:DoubleFactorizationTests.test_alpha_matches_closed_form_eigenvalues（2×2 闭式独立对拍 places=10）、test_df_alpha_tighter_than_pauli（DF α=1.4 ≤ Pauli α=1.5）；ThcTests.test_thc_alpha_matches_hand_computed_bound（THC α=1.996 独立手算）

概率分布算法（C3）

模块

算法

状态

缺口与计划

estimation.py

QPE、QAE、量子计数、Hadamard/SWAP test

✅

QAE 置信区间声明未见证（只验证了点估计）

search.py

Grover、振幅放大

✅

—

integration.py

Heinrich 求和/积分

✅

闭式均值对拍 + heinrich_rate 参数校验已有见证（tests/core/test_integration.py:SumPreparationTests / QuantumSumTests / RateTests）

gradient.py

Jordan 梯度

✅

线性精确 + 扰动收敛已有见证（tests/core/test_gradient.py:GradientTests.test_perturbed_linear_concentrates_with_grid_bits 含失败概率衰减率 q_{m+1} ≤ 0.34·q_m）

qpca.py

QPCA、密度矩阵指数化

✅

特征值读出峰对拍 + Δt 一阶误差率已有见证（tests/core/test_qpca.py:DensityMatrixExponentiationTests / QpcaTests）

启发式/优化算法（C4）

模块

算法

状态

缺口与计划

variational.py

QAOA-MaxCut、VQE、ansatz

✅

单边见证；补"达到小实例最优割"的强见证

dqi.py

DQI

✅

分布逐点对拍闭式（Krawtchouk）；identity 译码器基线断言已修为允许边界等值

应用层

模块

内容

状态

缺口与计划

qfvm.py / qham/

QFVM、QHAM

✅

目录对拍已有

catalog.py / gallery.py

33 案例对拍目录

✅

新算法（qsvt 求逆、graph_walks 搜索、data_loading、integration、qpca）未登记

4. 横切验证机制（基础设施投入项）

  1. 不变量测试库（新建议，tests/core/witness.py 或类似）：

    • assert_unitary(program)：参考模拟器上 W†W=I（抽样基态）。

    • assert_uncomputation(program, work_regs)：工作位复原（复用 LocalExit 机制）。

    • assert_bind_invariant(abstract_program, bindings)：同一开放声明的各绑定产生一致语义（误差界参数化）。

    • assert_block_equals(be, matrix, alpha)：BE 的 (0,0) 块对拍。 收益：新算法见证从"各写一套"变为声明式组合，且回归口径统一。

  2. 确定性策略（规则化）：所有概率断言必须是对精确模拟分布的闭式对拍；理论值恰好落在断言边界时用 ≥/≤ 加数值容差，不允许严格不等（DQI 边界案例已按此修复）。

  3. 收敛性扫描框架：对 C2 类算法提供参数扫描工具（误差 vs 度数/κ/Δt），断言拟合斜率 ≥ 理论率的下界；结果存 JSON 供 validation.json 汇总。

  4. 资源估算对拍：凡提供成本函数（qrom_cost、QSP 度数公式、Trotter 步数）的模块，生成程序的结构属性必须与成本公式一致（双向检查）。

  5. 目录登记规范：新算法完成后必须登记 catalog 案例（gate/qram 两版输入），并接入 tests/integration 的真实后端对拍（不用 mock）。

5. 实施路线

阶段

内容

前置

V1

不变量测试库（4 个断言原语）+ 在途模块（density/gradient/lowrank/integration/qpca）的见证按矩阵要求补齐（已完成，0.x 迭代）

无

V2

收敛性扫描框架 + qsvt/hamsim/ODE 求解器的收敛基准接入 validation.json

V1

V3

catalog 登记新算法（qsvt 求逆、MNRS 搜索、Select-Swap、Heinrich 积分、QPCA）+ tests/integration 真实后端对拍扩展

V1

V4

三绑定一致性参数化测试铺开（oracles/prepare_select/graph_walks/data_loading）

V1

6. 与现有验收的关系

validation.md / validation.json 继续作为版本验收记录；本计划落地后，V1–V4 的产物按版本写入其中。算法覆盖工作板（algorithm-coverage.md）记录"实现了什么"，本文档记录"如何证明正确"，两者行级对应。