我的意识因沉重和慵懒而黏糊糊地沉沦着，与此同时，新陈代谢也在无声地进行着。

# 一个简单的想法和 Szegedy quantum walk

给定一个图$G=(V,E)$，我们希望在上面随机游走。这个游走的过程最朴素的想法就是，有这样一个变换：

对于任意一个点$j\in V$，变换为：

$$|j\rangle\mapsto \frac{1}{\sqrt{\deg(j)}}\sum_{k:(j,k)\in E}|k\rangle$$

也就是把$|j\rangle$ 变化为$j$ 能到达的邻居$k$ 的均匀叠加态。

但是不难验证上述变换都不是酉的。

验证：设$U|j\rangle=|\partial_j\rangle:=\frac{1}{\sqrt{\deg(j)}}\sum_{k:(j,k)\in E}|k\rangle$，那么：

$$\langle j|U^\dagger U|k\rangle=\langle\partial_j|\partial_k\rangle\neq 0=\langle j|k\rangle$$

即这个变换不保持内积，就不是酉变换。

怎么解决呢？对于一个转移矩阵$P\in\mathbb{R}^{N\times N}$，其中$N=|V|$。有$\forall i,j\in[N],P_{i,j}\geq 0$ 和$\forall j\in [N],\sum_{i=1}^N P_{i,j}=1$。（和经典的 Markov 转移矩阵类似，列和为 1）而$P_{i,j}$ 意思是从结点$j$ 转移到结点$i$ 的概率。那么我们可以记：

$$|\psi_j\rangle:=|j\rangle\otimes \sum_{k\in [N]}\sqrt{P_{k,j}}|k\rangle=\sum_{j,k\in [N]}\sqrt{P_{k,j}}|j,k\rangle$$

即从$j$ 转移到的结点的一个叠加态。我们也可以引入：

$$\Pi:=\sum_{j=1}^N|\psi_j\rangle\langle\psi_j|$$

很显然有$\Pi^2=\Pi$，所以它是一个 projective operator。再引入交换算子：

$$S:=\sum_{j,k\in [N]}|j,k\rangle\langle k,j|$$

那么一步的 quantum random walk 可以定义为酉变换：

$$U:=S(2\Pi-I)$$

会发现这非常类似于 Grover 的式子。我们先验证它是一个酉变换：

$$\begin{aligned} UU^\dagger&=S(2\Pi -I)(2\Pi - I)^\dagger S^\dagger\\ &=S(2\Pi -I)(2\Pi - I) S\\ &=S(4\Pi^2-4\Pi+I)S\\ &=S(4\Pi-4\Pi+I)S\\ &=S^2\\ &=I \end{aligned}$$

为什么这么定义量子游走？一个直观的感觉是：

$$\begin{aligned} U^2&=S(2\Pi-I)S(2\Pi-I)\\ &=(2S\Pi^2S-I)(2\Pi-I)\\ &=(2(S\Pi)(S\Pi)^\dagger-I)(2\Pi-I) \end{aligned}$$

其中$(2\Pi-I)$ 可以看作是：关于空间$\text{supp}(\Pi)=\text{span}\{|\psi_j\rangle:j\in [N]\}$ 的一个 reflection。

因为对于一个向量$|\alpha\rangle$，你可以将其分解为属于$\text{supp}(\Pi)$ 和属于$\text{supp}(\Pi)^\bot$ 的两部分。

而作用$(2\Pi-I)$，就是前一部分不变，后一部分取反。直觉上这就是一个 reflection。

再关于$\text{span}\{S|\psi_j\rangle:j\in [N]\}$ 做一次 reflection。

这个被称为 Szegedy quantum walk。在第三部分我们再详细介绍它的使用和实现。

证明：我们定义$T=\sum_{j=1}^N|\psi_j\rangle\langle j|$，不难验证$T^\dagger T=I$, $TT^\dagger=\Pi$。并且$T^\dagger ST=D$。

我们定义$|\tilde{\lambda}\rangle:=T|\lambda\rangle$，那么对于任意一个$D$ 的特征值$\lambda$ 都有：

$$U|\tilde{\lambda}\rangle=S|\tilde{\lambda}\rangle\\ US|\tilde{\lambda}\rangle=2\lambda S|\tilde{\lambda}\rangle-|\tilde{\lambda}\rangle$$

这其实说明了，$\text{span}\{|\tilde{\lambda}\rangle,S|\tilde{\lambda}\rangle\}$ 这个二维子空间在$U$ 下是不变的。那我们用待定系数法，在这个不变子空间内找$U$ 的特征值。

假设特征向量为$|\mu\rangle:=|\tilde{\lambda}\rangle-\mu S|\tilde{\lambda}\rangle$，那么

$$U|\mu\rangle=S|\tilde{\lambda}\rangle-\mu(2\lambda S|\tilde{\lambda}\rangle-|\tilde{\lambda}\rangle)=\mu|\tilde{\lambda}\rangle+(1-2\lambda\mu)S|\tilde{\lambda}\rangle$$

所以我们希望，$U|\mu\rangle=\mu|\mu\rangle$，即$1-2\lambda\mu=-\mu^2$，解得$\mu=\lambda\pm i\sqrt{1-\lambda^2}$。

$\square$.

# 一点经典的随机游走

如果一个矩阵$P\in\mathbb{R}^{N\times N}$ 满足：

• $\forall i,j\in [N].\;P_{i,j}\geq 0$.
• $\forall j\in [N].\;\sum_{i=1}^NP_{i,j}=1$.

那么就称$P$ 是一个 stochastic matrix。

证明：首先根据线性代数知识，我们知道$P$ 和$P^T$ 有相同的特征值。而注意到：

$$P^T\begin{pmatrix}1\\1\\...\\1\end{pmatrix}=\begin{pmatrix}1\\1\\...\\1\end{pmatrix}$$

所以$1$ 是$P$ 的一个特征值。此外，对于任意特征值$\lambda$，都有：

$$P^T\mathbf{x}=\lambda\mathbf{x}\Rightarrow \forall j\in [N].\;\lambda x_j=\sum_{i=1}^NP_{i,j}x_i$$

那我们找出绝对值最大的$x_j$，就有：

$$|\lambda|\cdot|x_j|=\left |\sum_{i=1}^N P_{i,j}x_i\right |$$

根据三角不等式，

$$|\lambda|\cdot|x_j|=\left |\sum_{i=1}^N P_{i,j}x_i\right |\leq\sum_{i=1}^N|P_{i,j}x_i|\leq|x_j|\sum_{i=1}^N|P_{i,j}|=|x_j|$$

所以$|\lambda|\leq 1$。

$\square$.

下面我们考虑击中时间的分析。譬如给定一个$M\subset V$，我们认为$M$ 中的顶点被 mark 了。同样给定一个顶点$v\in V$，我们也有办法 check 是否$v\in M$。那么我们主要分析，随机游走什么时候能走到被 mark 的结点。

不失一般性，我们可以假设被 mark 的结点编号都是最大的若干个点。

给定 stochastic matrix $P$，可以诱导出一个新的 stochastic matrix：

$$P'_{j,k}=\begin{cases} P_{j,k}& k\notin M\\ 1 & k\in M,j=k\\ 0 & k\in M,j\neq k \end{cases}\qquad P':=\begin{pmatrix} P_M & \mathbf{0}\\ Q & I \end{pmatrix}$$

直观地理解就是，走到被 mark 的点后，将不再走出去。那么走$t$ 步的话，就为：

$$P'^t=\begin{pmatrix} P_M^t &\mathbf{0}\\ Q(I+P_M+...+P_M^{t-1})&I \end{pmatrix}$$

不失一般性，我们假设最开始我们有一个$V-M$ 上的均匀概率分布。

这里为什么不失一般性？因为首先，我们可以有一个$V$ 上的均匀概率分布，然后假如我们对这个概率分布进行 sample，sample 后进行 check，若 check 到属于$M$ 就重新 sample，那就得到了一个$V-M$ 上的均匀概率分布。

也就是我们分析时不考虑初始一随机 sample 直接 sample 到答案了这种情况。

注意，我们只关心 t 步后，没走到$M$ 的概率，那么：

$$\begin{pmatrix} P_M^t &\mathbf{0}\\ Q(I+P_M+...+P_M^{t-1})&I \end{pmatrix}\cdot\frac{1}{N-|M|}\begin{pmatrix}1\\1\\...\\1\\0\\...\\0\end{pmatrix}=\frac{1}{N-|M|} \begin{pmatrix} \sum_{k=1}^{N-|M|}[P_M^t]_{1,k}\\ \sum_{k=1}^{N-|M|}[P_M^t]_{2,k}\\ ...\\ \sum_{k=1}^{N-|M|}[P_M^t]_{N-|M|,k}\\ ... \end{pmatrix}$$

也就是，走$t$ 步后，没走到$M$ 的概率为：

$$\mathbb{P}(t)=\frac{1}{N-|M|}\sum_{j,k\notin M}[P_M^t]_{j,k}$$

我们记$|v\rangle=\frac{1}{\sqrt{N-|M|}}\begin{pmatrix}1,1,...,1\end{pmatrix}^T$，那么$\mathbb{P}(t)=\langle v|P_M^t|v\rangle$。

我们知道对于$|\langle v|v\rangle=1$ 的话，有$|\langle v|A|v\rangle|\leq \| A\|$ 对于任意矩阵$A$，其中，$\|A\|=\max_{\lambda\text{ is an eigenvalue of }A}|\lambda|$ 是$A$ 的谱范数。

如果$\|P_M\|=1-\Delta$，那么

$$\mathbb{P}(t)=|\langle v|P_M^t|v\rangle|\leq\|P_M^t\|\leq \|P_M\|^t=(1-\Delta)^t$$

所以我们期望走$t=O(1/\Delta)=O(1/(1-\| P_M\|))$ 步，就会以常数的概率走到$M$。

证明：设$|u\rangle\in\mathbb{R}^{N-|M|}$ 是$P_M$ 的最大特征根对应的特征向量。然后$|w\rangle\in\mathbb{R}^N$ 是在$|u\rangle$ 下面补齐一堆$0$ 的向量。

因为我们假设了$P$ 是对称的，那么它的行和、列和都是 1。那么$|V\rangle:=\frac{1}{\sqrt{N}}\sum_{j\in V}|j\rangle$ 是$P$ 的一个特征值为 1 的特征向量。

由于$|u\rangle$ 就是最大特征根对应的特征向量，所以

$$\|P_M\|=\max_{\lambda}|\lambda|=\langle u|P_M|u\rangle=\langle w|P|w\rangle$$

因为$P$ 是对称的，不妨设其谱分解为$P=\sum\lambda|\lambda\rangle\langle\lambda|$，那么

$$\begin{aligned} \|P_M\|&=\langle w|P|w\rangle\\ &=\sum\lambda\langle w|\lambda\rangle\langle\lambda|w\rangle\\ &=|\langle V|w\rangle|^2+\sum_{\lambda\neq 1}\lambda |\langle\lambda|w\rangle|^2\\ &\leq|\langle V|w\rangle|^2+\sum_{\lambda\neq 1}(1-\delta)|\langle\lambda|w\rangle|^2\\ \end{aligned}$$

注意到这个$\sum_\lambda|\langle\lambda|w\rangle|^2=1$，对于任意一个归一化的向量$|w\rangle$ 都满足。所以

$$\begin{aligned} \|P_M\|&\leq|\langle V|w\rangle|^2+\sum_{\lambda\neq 1}(1-\delta)|\langle\lambda|w\rangle|^2\\ &=\sum_{\lambda}|\langle\lambda|w\rangle|^2-\delta\sum_{\lambda\neq 1}|\langle\lambda|w\rangle|^2\\ &=1-\delta(1-|\langle V|w\rangle|^2) \end{aligned}$$

我们定义$\Pi_{V/M}=\sum_{j\notin M}|j\rangle\langle j|$，那么$\Pi_{V/M}|w\rangle=|w\rangle$。因为$|w\rangle$ 只有前$|M|$ 个 entry 是 1。那么根据柯西不等式：

$$\begin{aligned} |\langle V|w\rangle|^2&=|\langle V|\Pi_{V/M}|w\rangle|^2\\ &\leq\|\Pi_{V/M}|V\rangle\|^2\cdot\||w\rangle\|^2\\ &=\|\Pi_{V/M}|V\rangle\|^2\\ &=\frac{N-M}{N}\\ &\leq 1-\varepsilon \end{aligned}$$

所以$\|P_M\|\leq 1-\varepsilon\delta$。

$\square$.

# 对 Szegedy 游走的理解

或许会很奇怪，$U=S(2\Pi-I)$ 这是从哪来的，有何含义？

我们想一个更符合直观的，更好的理解。譬如我们现在有一个状态$|u,v\rangle$，它表示：我们现在在结点$v$，但是是从$u$ 走来的。

那么量子随机游走可以看作两个阶段：

1. Coin flip。保持第二寄存器$|v\rangle$ 不变，把第一寄存器变成一个$v$ 能到达结点的一个概率分布，即$\sum_{(v,v')\in E}p_{v'}|v'\rangle\otimes |v\rangle$。
2. Deterministic phase。交换两个寄存器，得到$\sum_{(v,v')\in E}p_{v'}|v,v'\rangle$。

结束后我们从一个状态$|u,v\rangle$（其中$(u,v)\in E$）到达了一个状态上的概率叠加态$\sum_{(v,v')\in E}p_{v'}|v,v'\rangle$。

如果对第二寄存器进行测量，我们就可以得到一个新的合法状态$|v,v'\rangle$。

但是我们不这样。我们从任意一个状态开始，不断地进行以上两步，也就是在随机游走，随后就会获得一个结点上的概率分布$\sum_{(u,v)\in E}p_{u,v}|u,v\rangle$，只测量第二寄存器，我们可以理解为，走若干步后：

$$\text{Prob}[\text{走到}v_0]=\sum_{(u,v_0)\in E}|p_{u,v_0}|^2$$

这就是一个随机的概率分布。

而重点在于第一个 Coin flip。我们该怎么 flip 呢？有许多策略。其中一个策略是 Hadamard type，它做的事情很简单，就是：

$$|u,v\rangle\mapsto \frac{1}{\sqrt{\deg(v)}}\sum_{(v,v')\in E}|v'\rangle\otimes |v\rangle$$

就是均匀地走到$v$ 的邻居上。不难发现，如果整个图是完全图，而且没有结构的，那么我们采用这样的均匀随机走法：

$$|u,v\rangle\mapsto\frac{1}{\sqrt{|V|}}\sum_{u\in V}|u,v\rangle$$

无论你走几步再测量第二寄存器，都和直接在原图上均匀随机没区别。但当在一条链上这样随机游走，可能会有一些其他性质。

但是 Grover 提出一种 Coin flip 的测量。他的朴素想法是，既然我们都知道从哪个结点来的，我们要分开讨论，走回上一个结点的概率和其他点的概率。即：

$$(C_v\otimes I)|u,v\rangle=\alpha|u,v\rangle+\beta\sum_{v'\in N_v\backslash\{u\}}|v',v\rangle$$

其中$N_v$ 表示$v$ 的邻居集合。我们就分开讨论了返回$u$ 的概率$\alpha^2$ 和其他情况的概率。那么为了让$C_v\otimes I$ 是酉变换，就需要：

$$\begin{cases} \alpha^2+(|N_v|-1)\beta^2=1\\ 2\alpha\cdot\beta+(|N_v|-2)\beta^2=0 \end{cases}$$

这是将$C_v$ 写成矩阵形式后，要求矩阵列形成了一个归一化的正交基。

所以我们解得

$$(\alpha,\beta)=\pm(1,0)\text{ or }\pm\left (\frac{2}{|N_v|}-1,\frac{2}{|N_v|}\right )$$

显然我们更关心后面这种情况。假设图是无向的，此时我们发现：

$$(C_v\otimes I)|u,v\rangle=2\cdot\frac{1}{|N_v|}\sum_{v'\in N_v}|v',v\rangle-|u,v\rangle$$

实际上就是

$$C_v\otimes I=2\sum_v|\psi_v\rangle\langle\psi_v|-I$$

其中$|\psi_v\rangle=\frac{1}{\sqrt{|N_v|}}\sum_{v'\in N_v}|v',v\rangle$。

这就是 Grover 的 coin flip 来源。

更一般地，我们假设图是全联通也无向的，我们用一个矩阵$P\in\mathbb{R}^{N\times N}$ 来表示从结点间的转移关系，譬如$P_{k,j}$ 表示从结点$j$ 到结点$k$ 转移的概率，如果设为 0 就说明他们不连通。

那么 Grover coin flip 就可以一般化地变为：

$$2\sum_v|\psi_v\rangle\langle\psi_v|-I$$

其中$|\psi_v\rangle=\sum_{u\in V}\sqrt{P_{u,v}}|u,v\rangle$。

注意，这和第一章中有点小区别就是，把第一个寄存器看作当前结点，还是第二个寄存器看作当前结点。

可以隐隐约约感觉到，这个量子随机游走的之所以可以平方加速，很可能就是$U=S(2\Pi-I)$ 的特征值是$e^{i\arccos\lambda}$ 这个有个三角函数，然后三角函数泰勒展开是一个根号平方之类的。

一个可能的实现（IsQ 风格）为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

defgate U = [...]; // 2Pi-I


defgate S = [...]; // 交换变换

unit random_walk(){
    qbit q[n];
    q = |0>; 
    // start from |0, 0>
    qbit anc;
    int a = M(anc);
    while (!a) {
        U(q[3], q[2], q[1], q[0]);
        M(q[1]);
        M(q[0]);
        S(q[3], q[2], q[1], q[0]);
        U_marked(q[3], q[2], anc);
        a = M(anc);
    }
}