【Under Construction】应用线性代数学习笔记 (2) 离散时间量子游走

Posted on 2024-12-07 Edited on 2024-12-15 In Notes , Quantum Computing

Abstract.

随机游走经典结论

矩阵 $P$ 称为一个随机矩阵若

$\begin{matrix} (1) & P_{i j} \geq 0 \forall i, j; \sum_{j} P_{i j} = 1 \forall i . \end{matrix}$

这样的矩阵 $P$ 描述了一个图 $G = (V, E)$ 上的随机游走的转移概率。称一个随机游走是

我们将下述经典结果作为 input：

定理 1.1（Perron-Frobenius）. 任意一个遍历的随机游走有唯一的稳态 $π$ 使得 $π_{i} > 0$ ， $\sum_{i} π_{I} = 1$ 且 $\sum_{i} π_{i} P_{i j} = π_{j}$ 。

换言之， $π$ 是 $P$ 的特征值为 $1$ 的特征向量。

称一个遍历的随机游走是可逆的，若 $π_{i} P_{i j} = π_{j} P_{j i}$ 。定义遍历的随机游走的 discriminant matrix 为 $D_{i j} = \sqrt{P_{i j} P_{j i}}$ ，依定义它是实对称的。

命题 1.2. 若随机游走 $P$ 可逆且遍历，那么其稳态 $| π ⟩ = \sum_{i} \sqrt{π_{i}} | i ⟩$ 是 $D$ 的特征值为 $1$ 的特征向量，且

$\begin{matrix} (2) & D = diag (\sqrt{π}) P diag (\sqrt{π})^{- 1} \end{matrix}$

因此 $D$ 和 $P$ 有相同的特征值。

证明. 简单计算。