14、量子漫步中的极限分布、混合时间与空间搜索算法

量子漫步中的极限分布、混合时间与空间搜索算法

1. 极限分布与混合时间

1.1 极限分布相关公式推导

在研究量子漫步时，我们会遇到一些关键的公式推导。首先，通过特定的条件（对应项消失），利用相关公式（7.11）和（7.46），可以得到如下公式：
[D(\bar{p}(t), \pi) = \frac{1}{2t} \sum_{v = 1}^{N} \left| \sum_{a,a’ = 0}^{d - 1} \sum_{k,k’ = 0}^{N - 1} \atop \lambda_{a,k} \neq \lambda_{a’,k’} } c_{a,k} c_{a’,k’}^* \frac{e^{2\pi i (\lambda_{a,k} - \lambda_{a’,k’})t} - 1}{e^{2\pi i (\lambda_{a,k} - \lambda_{a’,k’})} - 1} \sum_{b = 0}^{d - 1} \langle \lambda_{a’,k’} | b, v \rangle \langle b, v | \lambda_{a,k} \rangle \right|]
这里的(\frac{1}{t})因子导致了逆幂律的出现。在求和项中，唯一与时间(t)相关的项是(e^{2\pi i (\lambda_{a,k} - \lambda_{a’,k’})t} - 1)，其模是一个有界的周期函数。这种项的线性组合会产生围绕直线的振荡模式。

1.2 练习相关内容

• 练习7.8：在奇数循环中，从任意顶点开始的初始分布与极限分布之间的距离为(D(p(0), \pi)