3. 图问题的量子编码

要用量子游走求解图问题，第一步不是设计游走算子，而是把图本身“翻译”成量子计算机能读写的对象。图由顶点集 V 和边集 E 构成，量子编码的任务就是为顶点和边分配量子寄存器，并把邻接矩阵、拉普拉斯矩阵、关联矩阵这些经典矩阵映射为可被量子线路调用的算符。本节围绕“顶点与边的寄存器映射”和“黑箱访问模型”两条主线展开，说明三种矩阵各自的量子态表示方式及其适用场景。

一、顶点寄存器与边寄存器：两种基本映射

最直接的编码是顶点寄存器：若图有 N 个顶点，取 n = ⌈log₂N⌉ 个量子比特，用计算基 |v⟩ 表示第 v 个顶点。例如 N=8 时用 3 个比特，|000⟩ 到 |111⟩ 一一对应顶点 0 到 7。顶点寄存器是量子游走中“位置空间”的载体，硬币算子作用其上，行走算子则依据图的连接关系在顶点间转移振幅。

边也需要表示。对于边集规模为 M 的图，可另取 m = ⌈log₂M⌉ 个比特构成边寄存器，用 |e⟩ 标记第 e 条边。边寄存器常用于边着色、匹配、割集等问题，也用于把关联矩阵的作用写成“顶点—边”联合态上的受控操作。当 N 或 M 不是 2 的幂时，超出范围的基态属于无效编码，需要在实现中通过条件判断或辅助比特排除，避免振幅泄漏到不存在的顶点或边上。

二、邻接矩阵的量子态表示

邻接矩阵 A 的元素 A_uv=1 表示 u、v 之间有边，否则为 0。它最自然的量子表示是受控翻转算符：以顶点寄存器 |u⟩ 为控制、|v⟩ 为目标，当且仅当 A_uv=1 时施加翻转或相位。若把 A 视为作用在顶点空间上的算符，则 A|u⟩ = Σ_v A_uv|v⟩，这正是行走算子中“按邻接关系扩散”的数学形式。

在块编码（block encoding）框架下，邻接矩阵可被嵌入一个更大的酉算符 U，使得 U 的左上角子块正比于 A/α，α 为归一化因子（通常取最大度或最大行和）。这样，量子线路就能以受控方式“调用”A，而不必显式写出整个矩阵。邻接矩阵编码适合无向图上的扩散、连通性判断和谱性质估计。

三、拉普拉斯矩阵与关联矩阵的量子表示

拉普拉斯矩阵 L = D − A，其中 D 为度对角矩阵。它比邻接矩阵多了一层“度”的信息，因此量子编码时通常需要同时访问度数与邻接关系。一种做法是把 L 写成 L = B Bᵀ，其中 B 是关联矩阵；另一种做法是分别构造 D 和 A 的块编码，再通过线性组合得到 L 的块编码。拉普拉斯矩阵的零空间维数等于图的连通分量数，这一性质使它在连通性检测和割问题中非常关键。

关联矩阵 B 的规模为 N×M，元素 B_ve 表示顶点 v 与边 e 的关联关系。对无向图，通常约定每条边在两端点处取 +1，或按定向取 +1/−1。关联矩阵的量子表示天然是“顶点—边”联合空间上的算符：以边寄存器 |e⟩ 为控制，对两个端点顶点寄存器施加相位或翻转。由于 B 直接刻画“哪条边连着哪两个顶点”，它在边割、匹配和网络流类问题中比邻接矩阵更直观。

四、黑箱访问模型：从矩阵到可调用算符

有了寄存器映射，还需要一个“查询接口”让算法访问矩阵元素。这就是黑箱访问模型，也叫 Oracle 或块编码。其核心思想是：不把矩阵写进线路，而是构造一个酉算符 U_M，使得对任意基态 |u⟩|v⟩|0⟩，U_M 依据 M_uv 的值翻转辅助比特或施加相位。对于邻接矩阵，U_A|u⟩|v⟩|0⟩ = |u⟩|v⟩|0⊕A_uv⟩；对于关联矩阵，则以边寄存器为控制，对两个端点施加相位。

黑箱模型的复杂度通常以“查询次数”衡量。量子游走算法往往只需 O(√N) 或 O(√M) 次黑箱调用，就能完成经典算法需要 O(N) 次查询的任务。实现时要注意三点：一是归一化因子 α 必须覆盖矩阵最大行和，否则块编码不是酉的；二是辅助比特在每次调用后要回到 |0⟩，否则会污染后续计算；三是无效基态（超出 N 或 M 的编码）必须通过条件门排除，避免振幅泄漏。

五、编码选择与实现要点

三种矩阵并非互斥，而是对应不同问题结构。邻接矩阵适合扩散和连通性；拉普拉斯矩阵适合割、谱聚类和连通分量计数；关联矩阵适合边匹配、网络流和边着色。实际实现时，可先按 N、M 确定寄存器宽度，再根据目标矩阵选择块编码方式，最后用辅助比特和条件门保证编码合法。下表给出一个 N=4、M=4 的示例参数，便于对照理解。

总结来说，图问题的量子编码分三步：先用顶点寄存器和边寄存器把图元素映射为量子基态；再把邻接、拉普拉斯、关联矩阵分别写成受控翻转、线性组合或联合相位算符；最后通过黑箱访问模型把这些算符封装成可调用的酉门。掌握这三步，后续的量子游走算子设计就有了稳固的输入基础。