Select-Swap QROM（Select-Swap QROM）

English · 简体中文

类别 C5 · 模块 oracq.algorithms.input_model.data_loading · 阶段 V4

概述

Select-Swap QROM 是 QROM 查找的资源优化实现（Low–Kliuchnikov–Schaeffer 2018；Babbush et al. 2018，模块 docstring 引用）：把地址拆为高位 h（k 位）与低位 y（l 位），\(\lambda = 2^l\) 个窗口分区共享高位地址并行加载子表 \(T[h\cdot\lambda + i]\)，再按 \(y = i\) 受控交换归并，以 T 计数约 \(4(2^k + \lambda b)\)（b 为数据位宽）在查询深度与辅助比特之间权衡（input model 词汇中的 QRAM）。

接口与输入模型

select_swap_qrom(table, *, partitions, data_bits=None, name=None)
qrom_cost(n_addresses, data_bits, partitions=1)

API 入口：select_swap_qrom、qrom_cost

  • table：字序列或稀疏字典，缺失地址按 0 处理。

  • partitions：分区数 λ，必须是二的幂且不超过地址数 \(2^{\lceil\log_2 N\rceil}\)。

  • data_bits：数据位宽，缺省取最大表字的位宽。

返回 XorDatabase（implementation="select_swap"），对外接口仍是 address / data 两个 bits 寄存器，XOR 语义与基线完全一致。模块属性附带 qrom_cost 估算（字段表见 QROM 查找），其中 work_qubits = λ·b 为窗口寄存器、fanout_qubits = (λ-1)·l 为低位扇出副本（可用 dirty qubit）。

实现要点

三个阶段：select——λ 个 clean 局部窗口寄存器 window_i 各自执行子表查询 window_i ^= T[h·λ+i]，全部窗口共享高位地址，因此一元迭代只支付一次 \(2^k - 1\)（k = 0 时子表为常数，退化为 X 门）；merge——按 y == i 对 (window_i, data) 施加受控 swap–xor–swap 复合，净效果是受控的 data ^= window_i，在 data 任意初值下保持 XOR 语义且窗口内容不被破坏；uncompute——伴随重放子查询把全部窗口复净为零。

以测试基线（N = 16、b = 3）为例，qrom_cost 给出的权衡曲线：

λ

select

swap

t_count

t_depth

work

fanout

辅助比特

1

15

0

60

15

3

0

3

2

7

3

40

8

6

1

7

4

3

9

48

6

12

6

18

8

1

21

88

8

24

21

45

16

0

45

180

15

48

60

108

t_count 在 λ = 4 处取谷（测试 test_cost_model_matches_formulas_and_tradeoff_curve 断言的两个不等式），t_depth 同样在中间分区最小；λ = 16 时高位耗尽、select 段退化为纯交换。适用边界：λ 增大降低 T 深度但线性增加辅助比特，最优 λ 依赖硬件的比特 / 深度折算。

验证方案

类别 C5（数据访问层，判定准则见 ../development/validation-plan.md §2）。三层证据位于 tests/core/test_data_loading.py:DataLoadingTests（16 地址表 TABLE16，b = 3）：

  • 结构：test_generated_operations_carry_cost_attributes——select_toffoli / swap_toffoli / t_count / work_qubits / dirty_fanout_qubits 等属性与 qrom_cost(16, 3, 4) 逐项一致。

  • 数值：test_select_swap_matches_gate_database_per_address——λ ∈ {1, 2, 4, 8, 16} 下全部 16 个地址的读出与 gate_database 基线逐点相等；test_xor_semantics_with_nonzero_data_register（data 初值 5 时输出为 T[a] XOR 5）；test_superposition_query_restores_clean_work（地址均匀叠加上查询后边缘分布均匀，places = 12，窗口由 LocalExit 强制复净）；test_cost_model_matches_formulas_and_tradeoff_curve——λ = 4 处于曲线谷底（curve[4] < curve[1] = 4·15 且 < curve[16] = 4·45），并断言曲线与闭式 \(4(N/\lambda - 1 + b(\lambda - 1))\) 逐点一致。

  • 绑定：gate / QRAM 两绑定由 test_result_invariant_across_partitions_and_qrom_lookup_baseline 间接覆盖（结果不随分区与实现变化）；三绑定一致性参数化待 V4。

  • 负例：test_invalid_inputs_fail_at_generation——partitions 非二的幂 / 越界、空表、负值、字宽越界等在生成期抛 ValidationError。

已知缺口与计划阶段

三绑定参数化（V4）：同一声明的 gate / QRAM 绑定统一参数化对拍未铺开；validation-plan §5 另建议把 qrom_cost 纳入目录报告属性。与 validation-coverage.md 的 data_loading.py 行一致。

相关链接

数值验证

论文级数值验证脚本：tests/verification/verify_blockencoding.py（真实后端执行，无 mock、无 skip；2026-09-16 共 73 个案例全部通过），产物 out/verification/blockencoding.json。本页对应 select-swap-lambda{1,2,4,8,16} 与 select-swap-as-sparse-entry 共 6 个案例。

实验设计：16 地址、3 位随机数据字（固定种子），分区数 λ 全扫描 {1, 2, 4, 8, 16}；每个 λ 下对全部 16 个地址 × 两种 data 初值（0 与非零 5，检验 XOR 语义）逐基态读出，与 gate_database 真值表基线逐振幅对拍（reference 路径）。端到端案例：select_swap（λ = 2）作为 CKS 稀疏块编码的元素数据库，组装 2×2 带符号稀疏矩阵的 \(T^\dagger S T\) 块编码，零信号块乘 α 后与经典矩阵逐元对拍（见稀疏矩阵块编码数值验证节）。

案例

规模

后端路径

指标

数值

select-swap-lambda1

16 地址 × 2 初值

reference

与基线最大偏差

0

select-swap-lambda2

同上

reference

同上

0

select-swap-lambda4

同上

reference

同上

0

select-swap-lambda8

同上

reference

同上

0

select-swap-lambda16

同上

reference

同上

0

select-swap-as-sparse-entry

dim 2，s=2，α=3.0

reference

稀疏 BE 块 max_error

4.4e-16

复现命令：

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

产物：out/verification/blockencoding.json。