【Under Construction】应用线性代数学习笔记 (2) 离散时间量子游走
Abstract.
随机游走经典结论
矩阵 $P$ 称为一个随机矩阵若
$$
P_{ij} \geq 0 ~\forall i, j; \quad \sum_{j}P_{ij} = 1 ~\forall i.
$$
这样的矩阵 $P$ 描述了一个图 $G = (V, E)$ 上的随机游走的转移概率。称一个随机游走是
- 不可约的 若图是强连通的。
- 非周期性的 若图中所有环长的最大公约数为 $1$。
- 遍历的 若满足上述两条。
我们将下述经典结果作为 input：
定理 1.1（Perron-Frobenius）. 任意一个遍历的随机游走有唯一的稳态 $\pi$ 使得 $\pi_i > 0$，$\sum_{i}\pi_I = 1$ 且 $\sum_i \pi_iP_{ij} = \pi_j$。
换言之，$\pi$ 是 $P$ 的特征值为 $1$ 的特征向量。
称一个遍历的随机游走是可逆的，若 $\pi_iP_{ij} = \pi_j P_{ji}$。定义遍历的随机游走的 discriminant matrix 为 $D_{ij} = \sqrt{P_{ij}P_{ji}}$，依定义它是实对称的。
命题 1.2. 若随机游走 $P$ 可逆且遍历，那么其稳态 $|\pi\rangle = \sum_i\sqrt{\pi_i}|i\rangle$ 是 $D$ 的特征值为 $1$ 的特征向量，且
$$
D = \mathrm{diag}(\sqrt \pi) P \mathrm{diag}(\sqrt \pi)^{-1}
$$
因此 $D$ 和 $P$ 有相同的特征值。
证明. 简单计算。