基于离散时间量子行走的量子詹森-香农图核：原理与应用

### 基于离散时间量子行走的量子詹森 - 香农图核：原理与应用 #### 1. 图核方法概述 在模式识别的结构分析中，基于图的表示是强大的工具。然而，对图进行分类时，一个挑战是如何将离散的图结构转换为数值特征，图核方法应运而生。图核本质上是衡量一对图之间相似性的度量。 为了将通用机器学习领域的核方法扩展到图领域，Haussler 提出了 R - 卷积的通用方法来定义图核。对于一对图，R - 卷积核通过将每个图分解为更小的子图，并计算两个原始图之间同构子图对的数量来计算。不同的图分解方式通常会产生不同的图核。常见的图核包括： - **随机游走核**：由 Kashima 等人引入，基于枚举两个图之间的公共随机游走。 - **最短路径核**：由 Borgwardt 等人提出，通过计算图上匹配最短路径的数量。 - **无回溯核**：由 Aziz 等人引入，使用 Ihara zeta 函数识别的循环。 - **快速子树核**：由 Shervashidze 等人开发，通过比较 Weisfeiler - Lehman（WL）算法识别的子树对。 此外，还有一些基于经典詹森 - 香农散度计算两个图之间互信息的图核。经典詹森 - 香农散度是概率分布之间的非广泛互信息度量。基于此的詹森 - 香农图核通过图对及其复合图（如不相交并图或乘积图）的熵差来定义，避免了比较所有子结构对的计算负担。为了进一步发展，还引入了使用量子詹森 - 香农散度和连续时间量子行走的量子詹森 - 香农图核。 #### 2. 离散时间量子行走的量子力学背景 ##### 2.1 离散时间量子行走 离散时间量子行走是离散时间经典随机行走的量子对应。为了模拟图 $G(V, E)$ 上的离散时间量子行走的演化，首先将每条边 $e(u, v) \in E$ 替换为一对有向弧 $ed(u, v)$ 和 $ed(v, u)$，以确保量子过程的可逆性。新的弧集记为 $E_d$，离散时间量子行走的状态空间就是 $E_d$。 一般状态可表示为： \[ |\psi\rangle = \sum_{ed(u,v) \in E_d} \alpha_{uv} |uv\rangle \] 其中，量子振幅 $\alpha_{uv}$ 是复数，行走处于状态 $|uv\rangle$ 的概率为 $Pr(|uv\rangle) = \alpha_{uv}\alpha_{uv}^*$，$\alpha_{uv}^*$ 是 $\alpha_{uv}$ 的复共轭。 状态向量在步骤 $t$ 和 $t + 1$ 之间的演化由过渡矩阵 $U$ 决定，即 $|\psi_{t + 1}\rangle = U |\psi_t\rangle$。由于行走的演化是线性且概率守恒的，矩阵 $U$ 必须是酉矩阵，即 $U^{-1} = U^{\dagger}$，$U^{\dagger}$ 是 $U$ 的厄米转置。通常采用 Grover 扩散矩阵作为过渡矩阵，其元素为： \[ U_{(u,v),(w,x)} = \begin{cases} \frac{2}{d_x} - \delta_{ux}, & v = w \\ 0, & \text{otherwise} \end{cases} \] 其中，$\delta_{ux}$ 是 Kronecker 德尔塔。 mermaid 格式流程图如下： ```mermaid graph TD; A[开始] --> B[替换边为有向弧]; B --> C[定义状态空间Ed]; C --> D[定义一般状态|ψ⟩]; D --> E[确定过渡矩阵U]; E --> F[计算状态演化]; F --> G[结束]; ``` ##### 2.2 混合态的密度矩阵 在量子力学中，纯态可以用单个 ket 向量描述，而量子系统也可以处于混合态，即纯量子态 $|\psi_i\rangle$ 的统计系综，