图邻接 oracle（Adjacency Oracle）

English · 简体中文

类别 C1 · 模块 oracq.algorithms.input_model.graph_walks · 阶段 V3

概述

图行走框架的输入模型：以邻居表 oracle 访问图，查询语义为

\[ |v\rangle|j\rangle|c\rangle \mapsto |v\rangle|j\rangle|c \oplus N(v,j)\rangle, \]

即给定顶点 \(v\) 与出边下标 \(j\)，把第 \(j\) 个邻居编号异或进 neighbor 寄存器。设 \(g\) 为出边下标位宽、\(D = 2^g\)，每个顶点的出边表统一补齐到恰好 \(D\) 列（通常用自环补齐），使邻居叠加态 \(\frac{1}{\sqrt D}\sum_j |N(v,j)\rangle|j\rangle\) 无需知道具体度数即可归一化。该输入模型（FO，XOR 查询范式 database_xor）同时服务 Szegedy 量子行走与 MNRS 量子行走搜索。

接口与输入模型

核心类型 AdjacencyOracle（冻结 dataclass，OracleView 子类）封装一个 (vertex, index, neighbor) 签名的操作并复用 database_xor 范式，构造时校验签名及 vertex/neighbor 等宽。三个构造入口：

abstract_adjacency(vertex_bits, degree_bits, *, name=None)   # 开放声明
gate_adjacency(neighbors, *, name=None)                      # 门级受控 X 网络
qram_adjacency(vertex_bits, degree_bits, *, name=None)       # QRAM 表

API 入口：abstract_adjacency、gate_adjacency、qram_adjacency

  • abstract_adjacency：体为空的开放声明，vertex_bits 至多 32、degree_bits 取 0..32，可经 bind 绑定 gate/QRAM 实现。

  • gate_adjacency：小规模邻居表的门级实现；表必须是非空矩形且每项为合法顶点编号，位宽由表规模自动推出。

  • qram_adjacency：QRAM 实现，表项按地址 vertex | (index << vertex_bits) 寻址。

  • as_adjacency(value) 把裸 Operation 适配为 AdjacencyOracle。

AdjacencyOracle 的属性：

属性

含义

vertex_bits / degree_bits

顶点与出边下标位宽 \(v\) / \(g\)

vertices / degree

\(2^v\) 与 \(2^g\)

xor_database()

适配为 XorDatabase：address = vertex‖index（宽 \(v+g\)）、data = neighbor

实现要点

gate_adjacency 枚举全部 \((v, j)\) 分支做受控 X 网络，仅对非零的目标位发射门，因此任意表上的查询语义与真值逐点一致。qram_adjacency 是单条 QRAM Load 查表。补齐是调用方的责任：框架只要求每行恰好 \(D\) 列，行内重复（自环）不改变 XOR 语义，但决定 Szegedy 行走的有效转移。xor_database() 把图输入接入 XorDatabase 生态，可复用 QRAM 绑定与数据加载工具。

适用边界：gate_adjacency 的门数随表规模增长，面向小图与测试；更大的图用 qram_adjacency 或保持 abstract 声明延后绑定。

验证方案

类别 C1（精确离散语义，判定准则见 ../../development/validation-plan.md §2）：查询语义须与邻居表逐点相等。证据：

  • 结构：tests/core/test_graph_walks.py:AdjacencyOracleTests；test_bad_tables_fail_at_generation 覆盖非矩形表、顶点越界、marked 集合不可达导致首达时间发散等生成期违例。

  • 数值：AdjacencyOracleTests.test_gate_adjacency_implements_neighbor_table——对 Q3 超立方体邻居表（8 顶点 × 4 列，自环补齐到 \(D=4\)）穷举全部 32 个 \((v, j)\) 查询，读出幅度精确为 1（places = 10）；test_xor_database_adapter 校验适配后的地址/数据宽度与查询值。

  • 绑定：AdjacencyOracleTests.test_qram_adjacency_matches_gate_implementation（gate 与 QRAM 两实现逐点对拍）与 QuantumWalkSearchTests.test_abstract_handles_bind_to_gate_implementations（abstract 声明绑定 gate 实现后端到端语义不变，见 MNRS 量子行走搜索）共同构成邻接 oracle 的 gate/qram 双绑定证据。

已知缺口与计划阶段

与验证矩阵一致：Johnson 图（element distinctness 依赖）上尚无见证，需补新见证后接入，阶段 V3。

相关链接

数值验证

实验设计（端到端行走数值，邻接查询本身已由单测覆盖）：以超立方体 Q3 邻居表（8 顶点、度 4）的 gate_adjacency 为例，对 vertex/index 寄存器加 H 做一次叠加调用，穷举全部 32 个 \((v,j)\) 查询分支，四条后端路径（reference、rir-pysparq、adapter-pysparq、originir-ext）逐振幅核对 \(\lvert v\rangle\lvert j\rangle\lvert N(v,j)\rangle\) 结构。另以 QRAM 绑定（qram_adjacency + 内存表）跑通 MNRS 搜索端到端（K4，steps=2，OriginIR-ext 不含 QRAM 资源，该实例仅 reference 与 rir-pysparq 两路径）。

案例

规模

路径

指标

数值

adjacency-superposition-hypercube

8 顶点 × 4 列 = 32 查询

4 路径

振幅最大误差 / 表外分支权重

5.6e-17 / 0.0

mnrs-search-qram-k4

N=4, D=4, steps=2

reference, rir-pysparq

marked 概率 / 末态最大误差

0.578125 / 6.3e-16

复现命令：

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

产物：out/verification/search_walks.json（案例 adjacency-superposition-hypercube、mnrs-search-qram-k4）。