稀疏矩阵块编码（Sparse Matrix Block Encoding）

English · 简体中文

类别 C2 · 模块 oracq.algorithms.input_model.sparse · 阶段 V1

概述

把稀疏访问 oracle（位置与元素分离，input model 为 SO）适配为块编码。正式入口 real_symmetric_sparse_encoding 面向实对称（Hermitian）、非负对角矩阵，构造 CKS 型 \(T^\dagger S T\)（Childs–Kothari–Somma, arXiv:1511.02306，接口约定见 QFVM 输入模型审查）：先做幅度转导制备 \(T\)——在 neighbor 上制备稀疏位置的前缀均匀叠加、查位置 oracle 得行索引、查元素 oracle 得条目字、按 \(\sqrt{|v|/a_{\max}}\) 旋转成功旗标；再交换两侧坐标与两侧失败旗标得到 \(S\)。若每列枚举 \(s\) 个结构位置且 \(a_{\max}\) 确实约束元素幅值，则 \(T^\dagger S T\) 的零信号块为 \(A/(s \cdot a_{\max})\)。

接口与输入模型

real_symmetric_sparse_encoding(access, fmt, amax, *, diagonal_nonnegative=False, rotation=None)

API 入口：real_symmetric_sparse_encoding

  • access：SparseAccess——location（column/index/work 原地置换）与 entry（row/column/data XOR）两个操作。

  • fmt：FixedFormat 条目定点格式，宽度须等于 access.value_width；fmt.signed 决定是否叠加符号相位。

  • amax：元素幅值上界 \(a_{\max}\)，有限正数。

  • diagonal_nonnegative：必须显式传 True，否则报"当前对称稀疏适配要求非负对角"。

  • rotation：幅度转导操作，缺省 magnitude_rotation(fmt, amax)。

返回 BlockEncoding，模块属性：

属性

含义

be_alpha

\(s \cdot a_{\max}\)（\(s\) 为 access.sparsity）

construction

"CKS_Tdag_S_T"

self_adjoint_extension

True（Chebyshev walk 的前置条件）

correctness

"pending"

辅助入口：magnitude_rotation(fmt, amax)（值宽 ≤ 12 位给显式门实现，超宽返回带 amplitude_contract 属性的待绑定声明）、prefix_state(width, count)（前缀均匀叠加）、compare_words(width, kind)（eq/lt 布尔网络，缓存复用）、chebyshev_block(a, degree)（见下）。旧入口 sparse_block_encoding 已标注 legacy（legacy_input_model=True、matrix_contract 声明"legacy transduction unspecified"），仅供旧目录描述，不是一般稀疏输入适配器。

实现要点

寄存器布局：target = Bits(n)、signal = Bits(n+2)；signal[:n] 为 neighbor，signal[n] / signal[n+1] 为两侧失败旗标，条目字与位置 work 是局部寄存器、复净后交还。制备序列为叠加 → 位置查询 → 元素查询 → 幅度旋转（→ 带符号格式的方向相位）；外层 swap(target, signal[:n]) 与 swap(signal[n], signal[n+1]) 实现 \(S\)，两侧旗标交换是必要部分，只换索引不换旗标会破坏自伴性。负非对角元素按 target < neighbor 的方向约定叠加 \(\pi\) 相位（sign_convention 属性记录）。

chebyshev_block(a, degree)：要求输入 BE 显式声明 self_adjoint_extension（普通 BE 不足以保证 Chebyshev 语义），Repeat(degree) 交替"信号零态正反射 + 调用 a"，返回 be_alpha = 1.0、argument_scale = a.alpha 的行走幂，其零信号块实现 \(T_k(A/\alpha)\)。

适用边界：仅实 Hermitian 加非负对角；一般矩阵须先做显式 Hermitian dilation。值宽超过 12 位时幅度转导是开放声明，绑定前程序不可执行。

验证方案

类别 C2（近似连续语义，判定准则见 ../development/validation-plan.md §2）。与验证覆盖矩阵 sparse.py / block_encoding.py 行一致：

  • 结构：tests/core/test_language.py:BlockEncodingTests（BE 构造与属性断言）。

  • 数值：本入口的直接见证登记于 qlss.py 行——tests/core/test_qlss_input_models.py:QLSSInputTests.test_signed_sparse_encoding_and_chebyshev：2×2 含负非对角矩阵（\(s = 2\)、\(a_{\max} = 1\)）逐列读出零信号块乘回 alpha = 2 与经典矩阵对拍（places = 11），且 chebyshev_block(be, 3) 的零信号块与 \(4h^3 - 3h\)（\(h = A/\alpha\)，即 \(T_3\)）逐元素对拍。

  • 绑定：tests/core/test_language.py:BlockEncodingTests.test_alpha_survives_ir_serialization（JSON 往返保留 be_alpha）。

已知缺口与计划阶段

无已知缺口，阶段 V1（验证覆盖矩阵 sparse.py / block_encoding.py 行缺口列为空）。符号相位约定与 alpha 换算已有小实例见证；大字长幅度转导以显式待绑定声明的形式保留，其量化误差界未单列见证。

相关链接

数值验证

论文级数值验证脚本：tests/verification/verify_blockencoding.py（真实后端执行，无 mock、无 skip；2026-09-16 共 73 个案例全部通过），产物 out/verification/blockencoding.json。本页对应 sparse-be-*、chebyshev-walk-*、cross-tridiagonal-*、cross-qram-be-* 共 14 个案例。

实验设计：

  1. 稀疏 BE 多矩阵多规模：三对角矩阵 \(\alpha I + \beta T\)（带符号格式 \(\beta<0\) 检验方向相位约定、无符号格式检验无符号路径），dim ∈ {2, 4, 8, 16}，每列 \(s\) 个结构位置、边界列以零条目位置补足。零信号块逐列提取（reference 全列 + rir-pysparq / adapter-pysparq 交叉），乘回 \(\alpha = s\cdot a_{\max}\) 后与经典矩阵逐元对拍；dim = 2（15 qubits）与无符号 dim = 4（12 qubits）另走 OriginIR-ext 态向量逐列提取，带符号 dim = 4 达 24 qubits OriginIR 预算、dim = 8 为 34 qubits 超预算，均按预算只走 pysparq/reference 路径并在案例参数注明。

  2. QRAM 数据绑定稀疏 BE（dim = 4）：位置正/反表与元素表全部经 memory 绑定（不进 IR），reference 与 rir 逐振幅一致。

  3. Chebyshev 行走：2×2 稀疏 BE 的 chebyshev_block 阶数 \(k=1..4\)，零信号块对照 \(T_k(A/\alpha)\)。

  4. 与 pysparq 自带块编码的独立交叉验证：同一三对角矩阵分别经 oracq 稀疏 BE（及 dim ≤ 8 时的 Pauli LCU BE 第二路径）与 pysparq BlockEncodingTridiagonal 编码，各自提取有效块乘自身归一化后互相对拍（dim ∈ {2, 4, 8, 16}）；另以 pysparq BlockEncodingViaQRAM（C++ 判据配置 data_size=50、rational=51、exponent=15，矩阵 Frobenius 归一化入表）对拍三对角与非三对角（对匹配稀疏图 \(s=2\)）两个 dim = 4 实例。

案例

规模

后端路径

指标

数值

sparse-be-signed-tridiagonal-d2

dim 2，s=2，α=3.0

originir-ext + 三路径

max_error

4.4e-16

sparse-be-signed-tridiagonal-d4

dim 4，s=3，α=4.5

三路径

max_error

1.3e-16

sparse-be-signed-tridiagonal-d8

dim 8，s=3，α=4.5

reference + rir

max_error

1.3e-16

sparse-be-unsigned-unitary-d4

dim 4，s=3，α=4.5

originir-ext + 三路径

max_error

1.1e-16

sparse-be-unsigned-d16

dim 16，s=3，α=4.5

reference + rir

max_error

1.1e-16

sparse-be-qram-access-d4

dim 4，QRAM 绑定

reference + rir

max_error / 后端偏差

1.3e-16 / 0

chebyshev-walk-k1..k4

dim 2，\(\alpha=3.0\)

三路径

max_error

1.7e-16 / 2.5e-16 / 5.6e-16 / 6.7e-16

cross-tridiagonal-*（5 组）

dim 2–16

reference × pysparq

qecc / pysparq / 交叉误差

≤4.4e-16 / ≤4.4e-16 / ≤6.7e-16

cross-qram-be-tridiagonal-d4

dim 4，s=3

reference × pysparq QRAM

qecc 误差 / pysparq 量化误差

1.3e-16 / 2.8e-5

cross-qram-be-matched-pairs-d4

dim 4，s=2 非三对角

同上

交叉误差

2.8e-15

交叉验证发现（如实记录，非断言库缺陷）：pysparq BlockEncodingTridiagonal 的 (0,0) 块归一化在主寄存器 1 位（dim = 2）且 \(\beta \neq 0\) 时实测为 \(|\alpha|+2|\beta|\)，而非其构造文档的 Frobenius 范数（1 位寄存器上加一/减一都触发溢出分支，anc==0 角块失去 Frobenius 归一；\(\beta=0\) 时无移位分支、仍等于 \(A/\lVert A\rVert_F\)）。其 C++ 正确性测试域 randint(2,5)（dim 4–16）不覆盖该规模；脚本按实证归一化对拍并在案例参数 psparq_alpha_effective 记录两种口径。

复现命令：

PYTHONPATH=src <含 pysparq+uniqc 的解释器> tests/verification/verify_blockencoding.py

产物：out/verification/blockencoding.json。