5、量子随机游走与搜索算法解析

量子随机游走与搜索算法解析

1. 经典马尔可夫链

经典随机游走的量子化并非只有离散时间量子游走这一种方式。这里将介绍一种不借助硬币来确定移动方向的新量子游走模型，其灵感来源于连续时间马尔可夫链。

当时间为连续变量时，游走者可在任意时刻从顶点 $x_j$ 移动到相邻顶点 $x_i$。可以把概率想象成从 $x_j$ 渗透到 $x_i$ 的液体。初始时，游走者大概率处于 $x_j$，随着时间推移，在相邻顶点被找到的概率增加，而停留在 $x_j$ 的概率降低。

设转移率为 $\beta$，假设对所有顶点（均匀性和各向同性）和所有时间而言，$\beta$ 是常数。那么相邻顶点间的转移概率为每单位时间 $\beta$。若取无穷小时间间隔 $\tau$，游走者从顶点 $x_j$ 移动到 $x_i$ 的概率为 $\beta\tau$。设 $d_j$ 为顶点 $x_j$ 的度，$x_j$ 有 $d_j$ 个相邻顶点，所以经过时间 $\tau$ 后，游走者处于某个相邻顶点的概率为 $d_j\beta\tau$，停留在 $x_j$ 的概率为 $1 - d_j\beta\tau$。

在连续情况下，转移矩阵在时间 $t$ 的元素 $M_{ij}(t)$ 定义为处于顶点 $x_j$ 的粒子在时间间隔 $t$ 内移动到顶点 $x_i$ 的概率：
[
M_{ij}(\tau) =
\begin{cases}
1 - d_j\beta\tau + O(\tau^2), & \text{if } i = j \
\beta\tau + O(\tau^2), & \text{if } i \neq j
\end{cases