局部哈密顿问题的复杂性 01

原文为：arXiv:quant-ph/0406180

这篇文章挺难读的，但是也很有意思。大概会分成四次把解读更新完，其实原文在大部分地方已经讲的很清楚了，但是一些计算过程可能需要澄清，毕竟文中的证明有些给的实在简洁。

这篇文章主要讨论的问题是 $\text{2-}\large\text{L}\small{\text{OCAL }}\large{\text{H}}\small{\text{AMILTONIAN}}$ 问题的复杂度。作为第一部分这里主要把论文的前四节的比较复杂的证明过了一遍，主要是投影引理和对 Kitaev 构造的重述，虽然还没进入正题但也并不算简单，还是很有仔细研究的价值的。

基本定义

首先，我们快速回顾一下经典计算理论中复杂度类 $\mathsf{NP}$ 的量子版本，即 $\mathsf {QMA}$ 的概念：

给定 $\varepsilon = \varepsilon(|x|) = 2^{-\Omega(|x|)}$，其中 $|x|$ 为字符串 $x$ 的长度。称一个承诺问题 $L = (L_{yes}, L_{no})$ 在类 $\mathsf{QMA}$ 中，若存在一个量子的、多项式时间的验证者 $V$ 和一个多项式 $p$，使得：

• $\forall x \in L_{yes}, \exists |\xi\rangle \in \mathcal{B}^{\otimes p(|x|)}, \mathbf{P}(V(|x\rangle, |\xi\rangle) = 1) \geqslant 1 - \varepsilon$
• $\forall x \in L_{no}, \exists |\xi\rangle \in \mathcal{B}^{\otimes p(|x|)}, \mathbf{P}(V(|x\rangle, |\xi\rangle) = 1) \leqslant \varepsilon$

其中 $\mathcal B$ 指描述一个量子比特的 Hilbert 空间。

注意到，只需要取 $\varepsilon \leqslant 1/3$，事实上也就够了，它们产生的复杂度类都是等价的。

在经典计算复杂度理论中，Cook-Levin 定理表明， $\text{SAT}$ 问题是 $\mathsf{NP}$-完备的。在 $\mathsf{QMA}$ 中，我们取局部哈密顿问题 $\large\text{L}\small{\text{OCAL }}\large{\text{H}}\small{\text{AMILTONIAN}}$ 来作为其等价物。这个问题定义如下：

我们称一个算子 $H: \mathcal B^{\otimes n} \rightarrow \mathcal B^{\otimes n}$ 是 $k$-局部哈密顿（$k$-local Hamiltonian），若 $H = \sum_{j=1}^rH_j$，其中每个 $H_i$ 都是在最多 $k$ 个量子比特上的哈密顿算子。

在 $n$ 个量子比特上，给定一个 $k$-局部哈密顿 $H = \sum_{j=1}^r H_j$，其中 $r=\text{poly}(n)$。每个 $H_j$ 的范数 $||H_j|| \leqslant \text{poly}(n)$，其中的每个元素也可以被 $\text{poly}(n)$ 个比特表示出来。有两个输入 $a, b$ 满足 $a < b$，我们需要判断， $H$ 的最小特征值至多为 $a$ 还是大于 $b$。

在下文中，我们记 $H$ 的最小特征值为 $\lambda(H)$；若 $\Pi$ 为 $\mathcal{B}^{\otimes n}\rightarrow \mathcal{S}$ 的投影，则称 $\Pi H\Pi$ 为 $H$ 在子空间 $\mathcal S$ 上的限制，记作 $H\vert_\mathcal S$。

投影引理（Projection Lemma）

这个引理的核心意义就在于通过局部哈密顿近似一个全局哈密顿。考虑 Hilbert 空间 $\mathcal H$，$H_1$ 是其上的一个哈密顿，对于一个子空间 $\mathcal S \subseteq \mathcal H$ ，取一个哈密顿 $H_2$，使得 $\mathcal S$ 是其特征值 $0$ 的特征子空间，且 $\lambda(H_2|_\mathcal {S^{\perp}}) \gg ||H_1||$ 。考虑 $H = H_1 + H_2$，投影引理表明，$\lambda(H)$ 非常接近于 $\lambda(H_1\vert_\mathcal S)$。

我们称哈密顿 $H$ 的惩罚值（penalty value）为 $\min_{x \in \mathcal H, ||x|| = 1}\langle x | H | x \rangle$。

直觉地，我们发现，$H_2$ 对于那些在 $\mathcal S^{\perp}$ 上有分量的向量给出了非常大的惩罚值，因此，$\lambda(H)$ 对应的特征向量一定接近于 $\mathcal S$，也就是接近于 $H_1|_\mathcal S$ 的特征向量。

接下来给出一个形式化的描述：

令 $H = H_1 + H_2$ 为 Hilbert 空间 $\mathcal H = \mathcal S + \mathcal S^\perp$ 上的两个哈密顿之和，哈密顿 $H_2$ 的零特征空间为 $S$，而其在 $S^\perp$ 上的特征向量对应的特征值至少为 $J > 2||H_1||$，于是：

$$\lambda(H_1\vert_\mathcal S) - \frac{||H_1||^2}{J - 2||H_1||} \leqslant \lambda(H) \leqslant \lambda(H_1\vert_\mathcal{S})$$

注意到，如果 $J \geqslant 8||H_1||^2 + 2||H_1|| = \text{poly}(||H_1||)$，则我们有 $\lambda(H_1\vert_\mathcal S) - 1/8 \leqslant \lambda(H) \leqslant\lambda(H_1\vert_\mathcal S)$。

这个引理的证明非常简单。首先表明 $\lambda(H) \leqslant \lambda(H_1\vert_\mathcal S)$ ：令 $|\eta\rangle \in \mathcal S$ 为 $H_1|_\mathcal S$ 对应 $\lambda(H_1|_\mathcal S)$ 的特征向量，则

$$\langle \eta|H|\eta \rangle = \langle \eta|H_1|\eta \rangle + \langle \eta|H_2|\eta\rangle = \lambda (H_1\vert_\mathcal S)$$

因此 $\lambda(H_1|_\mathcal S)$ 也是 $H$ 的特征值，$\lambda(H) \leqslant \lambda(H_1|_\mathcal S)$。

接下来证明 $\lambda(H)$ 的下界：将单位向量 $|v\rangle \in \mathcal H$ 分解成 $|v\rangle = \alpha_1|v_1\rangle + \alpha_2 |v_2\rangle$，其中 $|v_1\rangle$ 和 $|v_2\rangle$ 分别为 $\mathcal S$ 和 $\mathcal S^\perp$ 中的两个单位向量，$\alpha_1, \alpha_2$ 为非负实数且平方和为 $1$ 。令 $K = ||H||$，则：

\begin{aligned}
\langle v|H|v \rangle &\geqslant \langle v|H_1|v\rangle + J\alpha_2^2\hfill\newline
&= \alpha_1^2\langle v_1|H|v_1\rangle + 2\alpha_1\alpha_2 \text{Re} \langle v_1 |H_1|v_2\rangle + \alpha_2^2\langle v_2|H_1|v_2\rangle + J\alpha_2^2\hfill\newline
&= (1 - \alpha_2^2)\langle v_1|H|v_1\rangle + 2\alpha_1\alpha_2 \text{Re} \langle v_1 |H_1|v_2\rangle + \alpha_2^2\langle v_2|H_1|v_2\rangle + J\alpha_2^2\hfill\newline
&\geqslant \langle v_1|H|v_1\rangle - K\alpha_2^2 - 2K\alpha_2 - K \alpha_2^2 + J \alpha_2\hfill\newline
&= \langle v_1|H|v_1\rangle + (J - 2K)\alpha_2^2 - 2K\alpha_2 \hfill\newline
&\geqslant \lambda(H_1|_\mathcal S) + (J - 2K)\alpha_2^2 - 2K\alpha_2\hfill\newline
&\geqslant \lambda(H_1|_\mathcal S) - \frac{K^2}{J - 2K}
\end{aligned}

Kitaev 构造

这里会经常用到一个非常好用的性质，对于张量积和矩阵乘法，有：

$$(A\otimes B)(C\otimes D) = AB\otimes CD$$

直觉上看，这很好理解，当然也是有条件的。这里懒得复述其条件和证明了，反正在这都能用。

在这一节中，作者尝试应用上述投影引理重述 Kitaev 关于 $O(\log n)\text{-}\large\text{L}\small{\text{OCAL }}\large{\text{H}}\small{\text{AMILTONIAN}}$ 是 $\mathsf{QMA}$ 完全的证明。也就是说，需要表明，所有 $\mathsf{QMA}$ 中的问题都可以被多项式地规约到 $O(\log n)\text{-}\large\text{L}\small{\text{OCAL }}\large{\text{H}}\small{\text{AMILTONIAN}}$。

我们考虑验证者 $V_x = V(|x\rangle, \cdot) = U_T\cdots U_1$，其中 $T = \text{poly}(|x|)$ 作用在 $N = \text{poly}(|x|)$ 个量子比特上。最开始前面的 $m = p(|x|)$ 个量子比特包含被给出的证明，后面的 $N - m$ 个辅助量子比特被初始化为 $0$ ，而电路的最终结果被放在第一个量子比特上。

我们构造一个作用在 $n = N + \log(T+1)$ 个量子比特上哈密顿 $H$ ，其中前面 $N$ 个量子比特表征计算，最后的 $\log(T + 1)$ 个量子比特表征时钟 $0, \cdots, T$ 的可能值，使得：

$$H = H_{out} + J_{in}H_{in} + J_{prop}H_{prop}$$

其中 $J_{in}$ 和 $J_{prop}$ 为 $N$ 为变量的大多项式，在后面将详细讲述其构造，而其他参量构造为：
\begin{aligned}
H_{in} \hfill&= \sum\limits^N_{i=m+1} |1\rangle\langle1|_i\otimes|0\rangle\langle0|\hfill\\
H_{out} \hfill &= (T+1)|0\rangle\langle0|_1 \otimes |T\rangle\langle T|\hfill\\
H_{prop} \hfill &= \sum\limits_{t=1}^T H_{prop, t}\hfill\\
H_{prop, t} \hfill &= \frac 1 2 \big(I \otimes |t\rangle\langle t| + I \otimes |t-1\rangle\langle t-1| - U_t \otimes |t\rangle\langle t-1| - U_t^\dagger|t-1\rangle\langle t| \big)
\end{aligned}
其中 $|\alpha\rangle\langle\alpha|_i$ 表示在第 $i$ 个量子比特为 $|\alpha\rangle$ 的子空间上的投影。上面的张量积中，第一部分都是在 $N$ 个量子比特的空间上的作用，第二部分则是为了处理时钟量子比特，$U_t$ 和 $U_t^\dagger$ 作用的量子比特与在原来的电路中完全相同。直观地讲，现在构造的这一系列哈密顿量中：

• $H_{in}$ 检查我们的输入值是正确的，也就是说，后面的 $N - m$ 个量子比特确实被初始化为 $0$；
• $H_{out}$ 检查表征结果的输出位；
• $H_{prop}$ 检查我们的结果确实是按照原来电路的状态转移方式得到的。

由于我们只有 $\log(T + 1) = O(\log n)$ 个时钟量子比特，所以这些哈密顿算子都是 $O(\log n)$-局部的。接下来我们表明任何一个 $\mathsf{QMA}$ 中的问题都能规约为对上述 $H$ 的 $O(\log n)\text{-}\large\text{L}\small{\text{OCAL }}\large{\text{H}}\small{\text{AMILTONIAN}}$ 问题：

如果电路 $V_x$ 对某个输入 $|\xi, 0\rangle$ 的接受概率大于 $1-\varepsilon$，那么哈密顿 $H$ 有一个小于 $\varepsilon$ 的特征值；如果它对所有输入 $|\xi, 0\rangle$ 的接受概率小于 $\varepsilon$，那么哈密顿 $H$ 的所有特征值均大于 $3/4 - \varepsilon$。

这个引理的前半部分非常好证明，只需要取

$$|\eta\rangle = \frac{1}{\sqrt{T+1}} \sum\limits^T_{t=0}U_t\cdots U_1 |\xi, 0\rangle \otimes |t\rangle$$

接下来就可以表明：

$$\langle \eta|H_{prop}|\eta \rangle = 0$$

记 $\eta_j = U_j\cdots U_1|\xi, 0\rangle \otimes |j\rangle$，注意到：

$$\langle \eta|H_{prop}|\eta\rangle = \sum\limits_{t=1}^t \langle\eta|H_{prop, t}|\eta\rangle$$

再次逐项展开，得：

$$\langle \eta|(\frac 1 2 I \otimes |t\rangle\langle t|)|\eta\rangle = \frac {1} {2(T+1)} \langle \sum\limits_{t=0}^T \eta_t |(I\otimes |t\rangle\langle t|)|\sum\limits_{t=0}^T \eta_t\rangle$$

这里如果将 $\eta_t$ 再展开，就会出现交叉项，首先考虑能不能消除它：
\begin{aligned}
\langle \eta_i | (I \otimes |t\rangle \langle t|) | \eta_j\rangle &= (U_j \cdots U_1 |\xi, 0\rangle \otimes |j\rangle)^\dagger(I\otimes|t\rangle\langle t |)(U_i \cdots U_1 |\xi, 0\rangle \otimes |i\rangle)\hfill\\
&= (U_j \cdots U_1 |\xi, 0\rangle)^\dagger I (U_i \cdots U_1 |\xi, 0\rangle) \otimes (\langle i|t\rangle\langle t|j\rangle)\hfill\\
&= (U_j \cdots U_1 |\xi, 0\rangle)^\dagger I (U_i \cdots U_1 |\xi, 0\rangle) \otimes 0\hfill\\
&= 0\hfill
\end{aligned}
那么非交叉项呢？事实上按照上面的式子，我们已经表明，所有这些和式中只会剩下一项：
\begin{aligned}
\langle \eta|(I \otimes |t\rangle\langle t|)|\eta\rangle &= (U_t \cdots U_1 |\xi, 0\rangle)^\dagger I (U_t \cdots U_1 |\xi, 0\rangle) \otimes (\langle t|t\rangle\langle t|t\rangle) \hfill\\
&= I \otimes 1\hfill\\
&= I\hfill
\end{aligned}
第二项如法炮制：
\begin{aligned}
\langle \eta|(I \otimes |t-1\rangle\langle t-1|)|\eta\rangle &= (U_{t-1} \cdots U_1 |\xi, 0\rangle)^\dagger I (U_{t-1} \cdots U_1 |\xi, 0\rangle) \otimes (\langle t-1|t-1\rangle\langle t-1|t-1\rangle)\hfill\\
&= I \otimes 1\hfill\\
&= I\hfill
\end{aligned}
后面两项同理展开，不过需要注意左边的不再是 $I$ 了：
\begin{aligned}
\langle \eta|(U_t \otimes |t\rangle\langle t -1 |)|\eta\rangle &= \langle \eta_{t}|(U_t \otimes |t\rangle\langle t-1|)|\eta_{t-1}\rangle\hfill\\
&= (U_{t} \cdots U_1 |\xi, 0\rangle)^\dagger U_t (U_{t-1} \cdots U_1 |\xi, 0\rangle) \otimes (\langle t|t\rangle\langle t-1|t-1\rangle)\hfill\\
&= I \otimes1\hfill\\
&= I\hfill\\
\langle \eta|(U_t \otimes |t -1\rangle\langle t |)|\eta\rangle &= \langle \eta_{t-1}|(U_t^\dagger \otimes |t-1\rangle\langle t|)|\eta_{t}\rangle\hfill\\
&= (U_{t-1} \cdots U_1 |\xi, 0\rangle)^\dagger U_t^\dagger (U_{t} \cdots U_1 |\xi, 0\rangle) \otimes (\langle t-1|t-1\rangle\langle t|t\rangle)\hfill\\
&= I \otimes1\hfill\\
&= I\hfill\\
\end{aligned}
于是我们成功地表明了 $\langle \eta|H_{prop}|\eta \rangle = 0$。

接下来的式子就简单了：
\begin{aligned}
\langle \eta|H_{in}|\eta \rangle = 0, \langle \eta|H_{out}|\eta \rangle < \varepsilon
\end{aligned}
合起来就有：

$$\lambda(H) \leqslant\langle \eta|H|\eta \rangle = \langle \eta|H_{out}|\eta \rangle < \varepsilon$$

嗯，确实非常好证明，容易到原作者都没有仔细写。接下来的第二部分会更加复杂一些：假设 $V_x$ 对于所有输入 $|\xi, 0\rangle$ 的接受概率都小于 $|\varepsilon\rangle$ ，令 $\mathcal S_{prop}$ 为 $H_{prop}$ 的基态空间，很显然，它是 $2^N$ 维的，它的一组基是：

$$|\eta_i\rangle = \frac {1}{\sqrt{T + 1}} \sum\limits^{T}_{t=0} U_t\cdots U_1|i\rangle \otimes |t\rangle$$

其中 $|i\rangle$ 表示 $N$ 个进入计算的量子比特，它们的特征值为 $0$，$\mathcal S_{prop}$ 事实上就表征了正确的状态转移方式。接下来我们要对这个子空间应用可爱的投影引理，为了做到这一点，首先需要标明 $J_{prop}H_{prop}$ 对处于 $\mathcal{S}_{prop}^\perp$ 中的状态给出了一个 $\text{poly}(N)$ 的惩罚值，也就是说，$H_{prop}$ 中最小的非零特征值反比于某个关于 $N$ 的多项式。于是，我们给出以下命题：

$\exists c > 0$，使得 $H_{prop}$ 的最小非零特征值至少为 $c/T^2$。

这个命题的证明也不太复杂，首先构造一个基的变换：

$$W = \sum\limits_{t=0}^T U_t\cdots U_1 \otimes |t\rangle\langle t|$$

将其应用到 $H_{prop}$ 上：

$$W^\dagger H_{prop}W = \sum\limits_{t=1}^T I \otimes \frac 1 2(|t\rangle\langle t| + |t-1\rangle\langle t-1| - |t\rangle\langle t-1| - |t-1\rangle\langle t|)$$

这里的计算方式和上面的证明很像，就不再重复了。当然，这个变换并不会改变 $H_{prop}$ 的特征谱，但它成功地将我们的哈密顿块对角化了：

$$W^\dagger H_{prop}W = I \otimes \begin{bmatrix} \frac 1 2 & -\frac 1 2 & 0 &&&\cdots& 0\\ -\frac 1 2 & 1 & -\frac 1 2 & 0 & \ddots && \vdots\\ 0 & -\frac 1 2 & 1 & -\frac 1 2 & 0 & \ddots &\vdots \\ &\ddots&\ddots&\ddots&\ddots&\ddots&\vdots\\ \vdots&&0 &-\frac 1 2 & 1 & -\frac 1 2 & 0 \\ &&&0 &-\frac 1 2 & 1 & -\frac 1 2 \\ 0 &&\cdots&& 0 &-\frac 1 2 &\frac 1 2 \end{bmatrix}$$

漂亮，这样我们就可以开始估计 $(T+1) \times (T+1)$ 小矩阵的特征值了。作者在这里说，使用“标准方法”即可，本来打算用 Givens 变换求解，但是算着实在烦人，于是在这里给出一个（看上去）稍微简单点的思路：

考虑到第一行和最后一行破坏了这个矩阵的美感，我们先把它们无视掉，来看一看中间这个矩阵：

$$\begin{bmatrix} 1 & -\frac 1 2 & 0 &&&\cdots& 0\\ -\frac 1 2 & 1 & -\frac 1 2 & 0 & \ddots && \vdots\\ 0 & -\frac 1 2 & 1 & -\frac 1 2 & 0 & \ddots &\vdots \\ &\ddots&\ddots&\ddots&\ddots&\ddots&\vdots\\ \vdots&&0 &-\frac 1 2 & 1 & -\frac 1 2 & 0 \\ &&&0 &-\frac 1 2 & 1 & -\frac 1 2 \\ 0 &&\cdots&& 0 &-\frac 1 2 & 1 \end{bmatrix}$$

这个矩阵是个 Toeplitz 矩阵，其特征值还是比较容易获得的：考虑其特征多项式为 $\varphi_n(\lambda)$ ，若其为一个 $n \times n$ 矩阵，则可以很容易地得到：

$$\varphi_n(\lambda) = (1-\lambda)\varphi_{n-1}(\lambda) - \frac 1 4 \varphi_{n-2}(\lambda)$$

然后观察一下这个式子，考虑到：

$$\varphi_0(\lambda) = 1, \varphi_1(\lambda) = 1-\lambda$$

发现它长得和第二类切比雪夫多项式的递推式长得有点神似：

$$\varphi_0(x) = 1, \varphi_1(x) = 2x, \varphi_n(x) = 2x\varphi_{n-1}(\lambda) - \varphi_{n-2}(\lambda)$$

那么我们可以考虑折腾一下这个矩阵，让它能够变成切比雪夫多项式的样子，只要把 $-\frac 1 2$ 这个系数提出来就可以了。这样的话得到的多项式就是：

$$\varphi_0 (\lambda) = 1, \varphi_1(\lambda) = 2-\lambda, \varphi_n(\lambda) = (2-\lambda)\varphi_{n-1}(\lambda) - \varphi_{n-2}(\lambda)$$

这下子我们就大功告成，只欠换元，令 $2x = 2-\lambda$，于是 $\phi_n(x) = \varphi_n(\lambda) = U_n(x)$。

接下来的事情就好办了，众所周知，第二类切比雪夫多项式的表达式是：

$$U_n = \frac{\sin((n+1)\cos^{-1}x)}{\sin(\cos^{-1}x)}, |x| \leqslant 1$$

它的根就是：

$$\cos\frac{k\pi}{n+1}, k = 1, 2, \cdots, n$$

所以我们求出现在这个矩阵的特征值为：

$$1-\cos\frac{k\pi}{n+1}, k = 1, 2, \cdots, n$$

接下来我们考虑按照和最后一行展开原来的矩阵，新的特征多项式为：

$$\psi(\lambda) = (\frac 1 2-\lambda)\xi(\lambda) - \frac 1 4 \xi\prime(\lambda)$$

其中：
\begin{aligned}
\xi(\lambda) &= (\frac 1 2 - \lambda)\varphi_{T-1}(\lambda) - \frac 1 4 \varphi_{T-2}(\lambda)\hfill\\
\xi\prime(\lambda) &= (\frac 1 2 - \lambda)\varphi_{T-2}(\lambda) - \frac 1 4 \varphi_{T-3}(\lambda)\hfill\\
\end{aligned}
嗯，看上去很丑。整理一下，就有：

$$\psi(\lambda) = (\frac 1 2 - \lambda)^2\varphi_{T-1}(\lambda) - \frac 1 2(\frac 1 2 - \lambda)\varphi_{T-2}(\lambda)+ \frac 1 {16} \varphi_{T-3}(\lambda)$$

看上去似乎就没什么办法了，但是别忘了我们有 $\varphi_n(\lambda)$ 的递推公式，现在这是我们最后的希望了：
\begin{aligned}
\psi(\lambda) &= (\frac 1 2 - \lambda)^2\varphi_{T-1}(\lambda) - \frac 1 2(\frac 1 2 - \lambda)\varphi_{T-2}(\lambda) - \frac 1 4 \varphi_{T-1}(\lambda) + \frac{1-\lambda}4 \varphi_{T-2}(\lambda)\hfill\\
&= (\lambda^2-\lambda) \varphi_{T-1}(\lambda) + \frac{\lambda}{4}\varphi_{T-2}(\lambda)\hfill\\
&= -\lambda((1-\lambda)\varphi_{T-1}(\lambda) - \frac 1 4\varphi_{T-2}(\lambda))\hfill\\
&= -\lambda\varphi_{T}(\lambda)\hfill
\end{aligned}
诶嘿，这下我们就发现了，原来加边矩阵的特征值和没加边的情形是一样的。所以，特征值中的较小值就是：

$$1 - \cos\frac{\pi}{T+1} \geqslant \frac c {T^2}$$

这个不等式挺显然的，就不做证明了。

好，准备工作做完了，接下来我们就要应用我们的投影引理了。上面表明了，$J\geqslant cJ_{prop}/T^2$。我们取：

$$H_1 = H_{out} + J_{in}H_{in}， H_2 = J_{prop}H_{prop}$$

只需要令 $J_{prop} = JT^2/c=\text{poly}(n)$，那么 $\lambda(H) \geqslant \lambda(H_1|_\mathcal {S_{prop}}) - \frac 1 8$。接下来我们考察 $\lambda(H_1|_\mathcal {S_{prop}})$。

考虑 $\mathcal{S}_{in} \subset \mathcal{S}_{prop}$ 为 $H_{in}|_{\mathcal S_{prop}}$ 的基态空间，很显然，它也是一个 $2^m$ 维子空间，其基为

$$|\eta_i\rangle = \frac{1}{\sqrt{T+1}}\sum\limits^T_{t=0}U_t\cdots U_1|j, 0\rangle \otimes |t\rangle$$

其中 $|j\rangle$ 为前面 $m$ 个计算用的量子比特的基。接下来在 $\mathcal S_{prop}$ 中应用投影引理，其中：

$$H_1 = H_{out}|_{\mathcal S_{prop}}, H_2 = J_{in}H_{in}|_{\mathcal S_{prop}}$$

很显然地，$||H_1|| \leqslant ||H_{out}|| = T+1 = \text{poly}(N)$。而任意处于 $\mathcal S_{in}^\perp$ 中的 $H_2$ 的特征向量的特征值都至少是 $J_{in} / (T+1)$，因此，可以找到 $J_{in} = \text{poly}(N)$ 使得 $\lambda(H_1+H_2) \geqslant \lambda(H_{out}|_{\mathcal S_{in}}) - \frac 1 8$。

根据我们在上面给出的接受概率小于 $\varepsilon$ 的假定，我们可以表明，$\lambda(H_{out}|_{\mathcal S_{in}}) > 1-\varepsilon$。综上所述，$\lambda(H) \geqslant 1-\varepsilon - \frac 2 8 = \frac 3 4 - \varepsilon$。