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

$|j\rangle\mapsto \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$

$|\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$

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

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

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

\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}

$U|\tilde{\lambda}\rangle=S|\tilde{\lambda}\rangle\\ US|\tilde{\lambda}\rangle=2\lambda S|\tilde{\lambda}\rangle-|\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$

$\square$.

# # 一点经典的随机游走

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

$1$ 是 stochastic matrix $P$ 的一个特征值，并且对于任意一个特征值$\lambda$，都有$|\lambda|\leq 1$

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

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

$|\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|$

$\square$.

$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}$

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

$\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}$

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

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

Lemma: Assuming $P$ is symmetric, if the second largest eigenvalue of $P$ (in absolute value) is at most $1-\delta$, (i.e. eigenvalue $1$ has single multiplicity), and $|M|\geq \varepsilon N$, then

$\|P_M\|\leq 1-\varepsilon\delta$

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

\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}

\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}

\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}

$\square$.

# # 对 Szegedy 游走的理解

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$

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

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

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

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

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

$(\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$

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