量子信息笔记（五）：量子计算

函数计算

输入 $x=\left(x_{n-1}, x_{n-2}, \ldots, x_{0}\right)$ 储存在 $n$ 比特寄存器 $\ket{x}$ 中，输出 $f(x)$ 储存在 $m$ 比特寄存器 $\ket{y}$ 中，且 $\ket{y}$ 的初值为 $\ket{0}$。一个幺正算符 $U_{f}$ 可以执行以下计算：

$$U_{f}|x\rangle|y\rangle=|x\rangle|y \oplus f(x)\rangle$$

其中 $\oplus$ 表示按位模 $2$ 加法。量子计算的并行性可以明显地看出：

$$U_{f} \sum_{x=0}^{2^{n}-1} c_{x}|x\rangle|y\rangle=\sum_{x=0}^{2^{n}-1} c_{x}|x\rangle|y \oplus f(x)\rangle$$

Deutsch-Jozsa 问题

单比特情况

考虑一个“黑盒”或者“预言机” $U_{f}$，它实现了一个函数 $f:\{0,1\} \rightarrow\{0,1\}$。这个函数只可能是两种类型之一：常数函数（对所有输入都返回相同的输出）或者平衡函数（对一半的输入返回 $0$，对另一半的输入返回 $1$）。那么我们需要多少次查询 $U_{f}$ 才能确定 $f$ 的类型？经典算法在最坏情况下需要两次查询，而量子算法只需要一次查询。

n比特情况

Deutsch-Jozsa 问题是一个通用的 Deutsch 问题。函数 $f:\{0,1\}^{n} \rightarrow\{0,1\}$ 要么是常数函数，要么是平衡函数。经典算法在最坏情况下需要 $2^{n-1}+1$ 次查询，而量子算法只需要一次查询就能确定 $f\left(x\right)$ 的类型。

Grover 搜索算法

Grover 算法是一种量子算法，能够以高概率从 $N$ 个元素的无序数据库中找到一个特定的输入，且只需要 $O(\sqrt{N})$ 次查询。相比之下，经典算法在最坏情况下需要 $O(N)$ 次查询。

在量子语言下，Grover 算法提供了一种从均匀叠加态中找到目标态 $\ket{\phi}$ 的方法（$N \gg 1$）：

$$|s\rangle=\frac{1}{\sqrt{N}} \sum_{i=0}^{N-1}|x\rangle \Rightarrow \ket{\phi}$$

Grover 算法还有一个更准确的描述：函数逆运算。假设有一个函数能够在量子计算机上计算，Grover 算法允许我们在给定 $y$ 的情况下找到 $x$，使得 $f(x) = y$。

---

类似于 Deutsch-Jozsa 问题，我们先设定一个查询函数：

$$f(x)=\left\{\begin{array}{ll}1 & \text { if } x=\ket{\phi} \\ 0 & \text { if } x\neq \ket{\phi}\end{array}\right.$$

$\text{step\ 1}$：准备初始态 $\ket{\psi_1}=\ket{0}^{\otimes n}\ket{1}$，第一个寄存其中含有 $n=\log_2 N$ 个比特，第二个寄存器含有 $1$ 个比特。

$\text{step\ 2}$：对两个寄存器分别施加 Hadamard 变换，得到均匀叠加态：

$$\left|\psi_{2}\right\rangle=\frac{1}{\sqrt{2^n-1}} \sum_{i=0}^{2^n-1}|x\rangle \frac{1}{\sqrt{2}} \left(|0\rangle-|1\rangle\right)$$

$\text{step\ 3}$：执行以下 “Grover iteration” 迭代 $r\left(N\right)$ 次，其中函数 $r\left(N\right)$ 的渐进行为为 $O(\sqrt{N})$。Grover 迭代由两个幺正算符 $U_f$ 和 $U_s$ 组成：

$$\ket{\psi_{3}}=\left(U_{s} U_{f}\right)^{r\left(N\right)}\left|\psi_{2}\right\rangle$$

其中 $U_f$ 是查询函数对应的幺正算符 $U_{f}|x\rangle|y\rangle=|x\rangle|y \oplus f(x)\rangle$，因此

$$U_{f}|x\rangle \frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)=(-1)^{f(x)}|x\rangle \frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$$

若我门只关心第一个寄存器的状态，可以忽略第二个寄存器，查询结果可由 $\ket{x}$ 的相位判定

$$U_{f}|x\rangle=\begin{cases}-|x\rangle & \text { if } x=\ket{\phi} \\ |x\rangle & \text { if } x\neq \ket{\phi}\end{cases}$$

$U_f$ 可以等价地写为

$$U_{f}=1-2|\phi\rangle\langle\phi|$$

$U_s$ 同样作用在第一个寄存器上，定义为

$$U_{s}=-H^{\otimes n} (1-2|0\rangle\langle 0|) H^{\otimes n}=2|s\rangle\langle s|-1$$

其中 $|s\rangle=H^{\otimes n}|0\rangle^{\otimes n}=\frac{1}{\sqrt{2^n}} \sum_{i=0}^{2^n-1}|x\rangle$ 是均匀叠加态。态 $\ket{s}$ 可以被分解为两部分，一部分是目标态 $\ket{\phi}$，另一部分是所有非叠加而产生的态 $\ket{\phi_{\perp}}=\frac{1}{\sqrt{2^n-1}} \sum_{x \neq \phi}|x\rangle$，且 $\langle \phi | \phi_{\perp} \rangle = 0$。因此

$$|s\rangle=\cos \frac{\theta}{2} \ket{\phi}+\sin \frac{\theta}{2} \ket{\phi_{\perp}}$$

其中 $\cos \frac{\theta}{2}=\frac{1}{\sqrt{2^n}}$，$\sin \frac{\theta}{2}=\sqrt{\frac{2^n-1}{2^n}}$。在基 $\{\ket{\phi_\perp}, \ket{\phi}\}$ 下，算符 $U_f$ 和 $U_s$ 的矩阵表示分别为

$$U_{f}=1-2\ket{\phi}\bra{\phi}=\begin{pmatrix}1 & 0 \\ 0 & -1\end{pmatrix}$$

$$U_{s}=2|s\rangle\langle s|-1=\begin{pmatrix}\cos \theta & \sin \theta \\ \sin \theta & -\cos \theta\end{pmatrix}$$

因此 Grover 迭代 $G=U_s U_f$ 的矩阵表示为

$$G=U_{s} U_{f}=\begin{pmatrix}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta\end{pmatrix}$$

因此，Grover 迭代相当于在 $\{\ket{\phi_\perp}, \ket{\phi}\}$ 基下绕原点逆时针旋转 $\theta$ 角度。$\ket{\psi_3}$ 可以表示为

$$\begin{aligned} \left|\psi_{3}\right\rangle&=\begin{pmatrix}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta\end{pmatrix}^{r\left(N\right)}\ket{\psi_{2}}=\begin{pmatrix}\cos\left(r\theta\right) & -\sin\left(r\theta\right) \\ \sin\left(r\theta\right) & \cos\left(r\theta\right)\end{pmatrix} \ket{\psi_{2}} \\[5pt] &=\left[\cos\left(r\theta+\frac{\theta}{2}\right)\ket{\phi_{\perp}}+\sin\left(r\theta+\frac{\theta}{2}\right)\ket{\phi}\right]\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle) \end{aligned}$$

那么第一个寄存器的态为

$$\left|\psi_{3}^{(1)}\right\rangle=\cos\left(r\theta+\frac{\theta}{2}\right)\ket{\phi_{\perp}}+\sin\left(r\theta+\frac{\theta}{2}\right)\ket{\phi}$$

因为 $N=2^n \gg 1,\frac{\theta}{2} \approx \frac{1}{\sqrt{N}}$，所以当

$$r\theta\approx \frac{\pi}{2} \Rightarrow r\approx \frac{\pi}{4}\sqrt{N}$$

得到

$$\left|\psi_{3}^{(1)}\right\rangle \approx \ket{\phi}$$

$\text{step\ 4}$：测量第一个寄存器，我们将以高概率得到目标态 $\ket{\phi}$。

---

Grover 算法的几何可视化：

下图是由 $\ket{\phi_{\perp}}$ 和 $\ket{\phi}$ 张成的二维空间的几何表示。初始态 $\ket{s}$ 位于 $\ket{\phi_{\perp}}$ 和 $\ket{\phi}$ 之间，Grover 迭代 $G$ 相当于绕原点逆时针旋转 $\theta$ 角度。经过 $r$ 次迭代后，态被旋转到接近 $\ket{\phi}$ 的位置，从而实现了对目标态的高概率测量。

直观起见，图中夸大了 $\theta$ 的大小。在实际情况下，$\theta$ 非常小，约为 $\frac{2}{\sqrt{N}}$。

算符 $U_f$ 是一个与 $\ket{\phi}$ 垂直平面上的反射，作用在 $\ket{s}$ 上后，$\ket{\phi}$ 方向的投影分量被反转

$$U_{f}=1-2|\phi\rangle\langle\phi|=\ket{\phi_{\perp}}\bra{\phi_{\perp}}-|\phi\rangle\langle\phi|= \begin{pmatrix}1 & 0 \\ 0 & -1\end{pmatrix}$$

算符 $U_s$ 是一个通过 $\ket{s}$ 的反射，作用在任意态上后，$\ket{s_\perp}$ 方向的投影分量被反转

$$U_{s}=-1+2|s\rangle\langle s|=\ket{s}\bra{s}-\ket{s_{\perp}}\bra{s_{\perp}}= \begin{pmatrix}\cos \theta & \sin \theta \\ \sin \theta & -\cos \theta\end{pmatrix}$$

每一次 Grover 迭代 $G=U_s U_f$ 都相当于先绕 $\ket{\phi_\perp}$ 折射，再绕 $\ket{s}$ 折射，总体效果是旋转 $\theta=2\sin^{-1}\left(\frac{1}{\sqrt{N}}\right)\approx \frac{2}{\sqrt{N}}$。

量子傅里叶变换

离散傅里叶变换

一个 $N$ 维复变量的 $f=\left(f_{0}, f_{1}, \ldots, f_{N-1}\right)$ 的离散傅里叶变换定义为

$$\tilde{f}_k=\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}e^{2\pi i\frac{jk}{N}}f_j,$$

那么我们得到矢量 $\tilde{f}=\left(\tilde{f}_0, \tilde{f}_1, \ldots, \tilde{f}_{N-1}\right)$。由于计算每个 $\tilde{f}_k$ 都不需要得知其他的 $\tilde{f}_j$，所以可以进行并行计算。

量子傅里叶变换

定义两个 $n$ 比特量子寄存器 $|k\rangle=|k_{n-1},k_{n-2},...,k_{0}\rangle$ 和 $|j\rangle=|j_{n-1},j_{n-2},...,j_{0}\rangle$（$N=2^n$），$k$ 和 $j$ 分别为对应的十进制表示。定义一个作用在 $n$ 比特量子态上的算符 $\hat{F}$，其作用为

$$\hat{F}|j\rangle=\frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^n-1}e^{2\pi i\frac{jk}{2^n}}|k\rangle$$

上式虽然与离散傅里叶变换形似，但 $\hat{F}$ 只是一个基矢比变换，还未实现傅里叶变换的功能。

对于任意的量子态 $|\psi\rangle=\sum_{j}f_j|j\rangle$，其量子傅里叶变换由下式给出

$$\begin{aligned} |\tilde{\psi}\rangle & =\hat{F}|\psi\rangle=\sum_{j=0}^{2^n-1}f_j\hat{F}|j\rangle \\ & =\sum_{k=0}^{2^n-1}\left(\frac{1}{\sqrt{2^n}}\sum_{j=0}^{2^n-1}e^{2\pi i\frac{jk}{2^n}}f_j\right)|k\rangle \\ & =\sum_{k=0}^{2^n-1}\tilde{f}_k|k\rangle \end{aligned}$$

$\ket{\tilde{\psi}}$ 的系数矢量 $\tilde{f}=\left(\tilde{f}_0, \tilde{f}_1, \ldots, \tilde{f}_{N-1}\right)$ 正是 $\ket{\psi}$ 的系数矢量 $f=\left(f_0, f_1, \ldots, f_{N-1}\right)$ 的离散傅里叶变换结果。这样，我们只用了一次操作 $\hat{F}$ 就实现了对所有 $f_j$ 的傅里叶变换，但是光有这样的结果是不够的，因为我们无法直接访问 $\tilde{f}_k$。

量子线路实施

我们先构建算符 $\hat{F}$ 的量子线路

$$|\psi\rangle \xrightarrow{\hat{F}}|\tilde{\psi}\rangle \\[8pt] \hat{F}|j\rangle =\frac{1}{\sqrt{2^{n}}}\sum_{k=0}^{2^{n}-1}e^{2\pi i\frac{jk}{2^{n}}}|k\rangle$$

利用实数的二进制表示

$$k=\left(\overline{k_{n-1}k_{n-2}\cdots k_0}\right)_{\mathrm{binary}}=\left(k_{n-1}2^{n-1}+k_{n-2}2^{n-2}+\cdots+k_02^0\right)_{\mathrm{decimal}} \\[10pt] j=\left(\overline{0.j_{l-1}j_{l-2}\cdots j_0}\right)_{\mathrm{binary}}=\left(j_{l-1}2^{-1}+j_{l-2}2^{-2}+\cdots+j_02^{-l}\right)_{\mathrm{decimal}}$$

将 $\hat{F}|j\rangle$ 展开为

$$\begin{aligned} \hat{F}|j\rangle & =\frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^n-1}\exp\left(2\pi i\frac{jk}{2^n}\right)|k\rangle \\ & =\frac{1}{\sqrt{2^{n}}}\sum_{k_{n-1}=0}^{1}\sum_{k_{n-2}=0}^{1}\cdots\sum_{k_{0}=0}^{1}\exp\left(2\pi i\frac{j}{2^{n}}\sum_{l=1}^{n}k_{n-l}2^{n-l}\right)|k_{n-1},k_{n-2},\ldots,k_{0}\rangle \\ & =\frac{1}{\sqrt{2^{n}}}\sum_{k_{n-1}=0}^{1}\sum_{k_{n-2}=0}^{1}\cdots\sum_{k_{0}=0}^{1}\bigotimes_{l=1}^{n}\left[\exp\left(2\pi ij\frac{k_{n-l}}{2^{l}}\right)|k_{n-l}\rangle_{l}\right] & \\ & =\frac{1}{\sqrt{2^n}}\bigotimes_{l=1}^n\left[\sum_{k_{n-l}=0}^1\exp\left(2\pi ij\frac{k_{n-l}}{2^l}\right)|k_{n-l}\rangle_l\right] \\ & =\frac{1}{\sqrt{2^n}}\bigotimes_{l=1}^n\left[|0\rangle_l+\exp\left(2\pi ij\frac{1}{2^l}\right)|1\rangle_l\right] \end{aligned}$$

当求和项数有限时，两个求和可以调换位置，或者求和项数无限但求和项绝对收敛时，两个求和可以调换位置。

现在 $\hat{F}|j\rangle$ 对态 $|j\rangle$ 的作用被分解为对每个量子比特的作用的直积。但是 $j$ 仍然以十进制的形式整体作用在每个量子比特上，实际上 $j$ 也是一个二进制数。将 $j$ 的二进制表示代入上式，得

$$\begin{aligned} \hat{F}\ket{j}& =\frac{1}{\sqrt{2^n}}\bigotimes_{l=1}^n\left[|0\rangle_l+\exp\left(2\pi i(j_{n-1}2^{n-l-1}+j_{n-2}2^{n-l-2}+\cdots+j_02^{-l})\right)|1\rangle_l\right] \\ & =\frac{1}{\sqrt{2^{n}}}\bigotimes_{l=1}^{n}\left[|0\rangle_{l}+\exp\left(2\pi i(j_{l-1}2^{-1}+j_{l-2}2^{-2}+\cdots+j_{0}2^{-l})\right)|1\rangle_{l}\right] \\ & =\frac{1}{\sqrt{2^n}}\bigotimes_{l=1}^n\left[|0\rangle_l+\exp\left(2\pi i\overline{0.j_{l-1}j_{l-2}\cdots j_0}\right)|1\rangle_l\right] \\ & =\frac{1}{\sqrt{2^n}} \begin{bmatrix} |0\rangle_1+\exp\left(2\pi i\overline{0.j_0}\right)|1\rangle_1 \end{bmatrix} \\ &\quad\quad\ \otimes \begin{bmatrix} |0\rangle_2+\exp\left(2\pi i\overline{0.j_1j_0}\right)|1\rangle_2 \end{bmatrix} \\ & \quad\quad\ \ldots \\ & \quad\quad\ \otimes\left[|0\rangle_{n}+\exp\left(2\pi i\overline{0.j_{n-1}j_{n-2}\cdots j_{0}}\right)|1\rangle_{n}\right]. \end{aligned}$$

现在，我们可以根据上式搭建量子线路了，利用 $\text{Hadamard}$ 门和受控相位门 $U_k$

$$\begin{aligned} H|0\rangle &= \frac{1}{\sqrt{2}} \left[ |0\rangle + \exp\left(2\pi i \times \overline{0.0}\right) |1\rangle \right] \\ H|1\rangle &= \frac{1}{\sqrt{2}} \left[ |0\rangle + \exp\left(2\pi i \times \overline{0.1}\right) |1\rangle \right] \end{aligned} \qquad \qquad U_k = \begin{pmatrix} 1 & 0 \\ 0 & \exp\left( \frac{2\pi i}{2^k} \right) \end{pmatrix}$$

在上图中，第 $l$ 个量子比特经过一个 $\text{Hadamard}$ 门和 $l-1$ 个受控相位门 $U_2, U_3, \ldots, U_l$ 的作用后，得到了所需的相位因子 $\exp\left(2\pi i \times \overline{0.j_{l-1}j_{l-2}\cdots j_0}\right)$。整个量子傅里叶变换线路的深度为 $O(n^2)$，远小于经典快速傅里叶变换的 $O(2^n n)$；但缺点是初态制备问题和末态测量是概率性的。

量子相位估计

算法描述

量子相位估计算法应用于一类本征值为相位因子的幺正算符。设有一个幺正算符 $U$，其本征态为 $|u\rangle$，对应的本征值为 $e^{2\pi i \phi}$，其中 $0 \leq \phi < 1$，如果能够制备本征态 $|u\rangle$ 和实现受控 $U^{2^j}$ 操作，那么量子相位估计算法可以高效地估计 $\phi$ 的值。

第一行的 $n$ 个量子比特寄存器取决于对相位 $\phi$ 的精度需求，第二行的 $m$ 个量子比特寄存器用于存储本征态 $|u\rangle$。上图右边输出的结果为

$$\begin{aligned} |\underbrace{0,0,\ldots,0}_{n}\rangle|u\rangle \quad \to\quad&\frac{1}{\sqrt{2^{n}}}\left(|0\rangle+e^{2\pi i2^{n-1}\phi}|1\rangle\right)\left(|0\rangle+e^{2\pi i2^{n-2}\phi}|1\rangle\right)\cdots\left(|0\rangle+e^{2\pi i2^{0}\phi}|1\rangle\right)|u\rangle \\ & =\quad\frac{1}{\sqrt{2^{n}}}\sum_{k=0}^{2^{n}-1}e^{2\pi i\phi k}|k\rangle|u\rangle=\left(\hat{F}|2^{n}\phi\rangle\right)|u\rangle \end{aligned}$$

$|2^{n}\phi\rangle$ 是 $\phi$ 的二进制表示的前 $n$ 位，也就是将小数形式的 $\phi$ 小数点后的 $n$ 个二进制数提取出来。

$$\phi=\left(\overline{0.\phi_{n-1}\phi_{n-2}\cdots\phi_{0}}\right)_{\mathrm{binary}}=\left(\phi_{n-1}2^{-1}+\phi_{n-2}2^{-2}+\cdots+\phi_{0}2^{-n}\right)_{\mathrm{decimal}} \\[10pt] 2^{n}\phi=\left(\phi_{n-1}2^{n-1}+\phi_{n-2}2^{n-2}+\cdots+\phi_{0}2^{0}\right)_{\mathrm{decimal}}=\left(\overline{\phi_{n-1}\phi_{n-2}\cdots\phi_{0}}\right)_{\mathrm{binary}}$$

现在我们考虑如何将 $\ket{2^{n}\phi}$ 从量子傅里叶变换态 $\hat{F}|2^{n}\phi\rangle$ 中提取出来。我们只需要对第一行的 $n$ 个量子比特施加逆量子傅里叶变换 $\hat{F}^{-1}$

$$\hat{F}^{-1}|j\rangle=\frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^n-1}\exp\left(-2\pi i\frac{jk}{2^n}\right)|k\rangle$$

就可以得到

$$\boxed{|0,0,\ldots,0\rangle|u\rangle\to\left(\hat{F}|2^n\phi\rangle\right)|u\rangle\xrightarrow{\hat{F}^{-1}}|2^n\phi\rangle|u\rangle\equiv|\phi_{n-1},\phi_{n-2},\cdots,\phi_0\rangle|u\rangle}$$

傅里叶逆变换的量子线路与正变换类似，可以将所有受控相位门 $U_k$ 替换为其逆门 $U_k^{\dagger}$，但是这样需要变动的门很多，我们可以将输入端变换为输出端，就直接得到逆变换线路。

最后我们从测量结果 $\phi_{n-1},\phi_{n-2},\cdots,\phi_0$ 中读取到了 $\phi$ 的近似值 $\overline{0.\phi_{n-1}\phi_{n-2}\cdots\phi_{0}}$

误差分析

一般来说第一个寄存器的比特数 $n$ 不足以存储 $\phi$ 小数点后所有数据，那么测量结果会有误差，且这个误差并不像经典计算只需四舍五入那么简单，因为还要进行傅里叶逆变换：例如，$\overline{0.01101}$ 乘以$2^3$ 得到 $\overline{11.01}$，由于不是一个整数，无法直接用直积态 $|1101\rangle$ 来表示，这就会对傅里叶变换的结果产生影响。我们希望得到测量结果尽可能趋近于真实值 $\phi$，那么就需要进行观察误差较大的概率，并降低这个概率。

假设 $0\leq b\leq 2^n-1$，那么 $\frac{b}{2^n}$=$\overline{0.b_{n-1}b_{n-2}\cdots b_0}$ 是 $\phi$ 的一个 $n$ 比特近似值。定义误差 $\delta=\phi-\frac{b}{2^n}$，测量结果为

$$\begin{aligned} \hat{F}^{-1}\frac{1}{\sqrt{2^{n}}}\sum_{k=0}^{2^{n}-1}e^{2\pi i\phi k}|k\rangle & =\frac{1}{2^{n}}\sum_{l=0}^{2^{n}-1}\sum_{k=0}^{2^{n}-1}\exp\left(-2\pi i\frac{lk}{2^{n}}+2\pi i\phi k\right)|l\rangle \\ & =\frac{1}{2^{n}}\sum_{l=0}^{2^{n}-1}\sum_{k=0}^{2^{n}-1}\exp\left[2\pi ik\left(\phi-\frac{l}{2^{n}}\right)\right]|l\rangle \\ & =\frac{1}{2^n}\sum_{l=0}^{2^n-1}\sum_{k=0}^{2^n-1}\exp\left[2\pi ik\left(\phi-\frac{l+b}{2^n}\right)\right]|(l+b)({\mathrm{mod}}2^n)\rangle \\ & =\frac{1}{2^{n}}\sum_{l=0}^{2^{n}-1}\sum_{k=0}^{2^{n}-1}\exp\left[2\pi ik\left(\delta-\frac{l}{2^{n}}\right)\right]|(l+b)({\mathrm{mod}}2^{n})\rangle \\ &=\frac{1}{2^{n}}\sum_{l=0}^{2^{n}-1}\frac{1-\exp\left[2\pi i\left(2^{n}\delta-l\right)\right]}{1-\exp\left[2\pi i\left(\delta-\frac{l}{2^{n}}\right)\right]}|(l+b)({\mathrm{mod}}2^{n})\rangle \end{aligned}$$

通过计算，我们可以证明，得到的结果 $|m\rangle$ 满足 $|m-b|> \epsilon$ 的概率为

$$p\left(|m-b|>\epsilon\right)\leq\frac{1}{2(\epsilon-1)}$$

如果以 $2^{-t}$ 的精度近似 $\phi$，那么我们可以选择 $\epsilon=2^{n-t}-1$ 使得成功的概率达到 $1-\epsilon$，因此我们在第一个寄存器中至少需要 $n$ 个量子比特

$$n=t+\left\lceil\log(2+\frac{1}{2\varepsilon})\right\rceil$$

求阶问题

阶的定义

$\text{Shor}$ 算法可以通过量子计算机分解质因数，求阶是 $\text{Shor}$ 算法的核心步骤。

对于两个正整数 $x<N$，$x$ 与 $N$ 互质，$r$ 是满足下式的最小正整数：$x^{r} \equiv 1 (\bmod N)$。求阶问题是在给定的 $x$ 和 $N$ 下，找到 $r$ 的值。

• 阶 $r$ 也就是 $x^r=1+ kN$
• 对于一个正整数 $N$，若两个整数之差 $a-b$ 能被 $N$ 整除（也就是 $a-b=kN$），则称 $a$ 与 $b$ 在模 $N$ 下同余，记作 $a \equiv b (\bmod N)$

如果 $x^{r} \equiv 1 (\bmod N)$，我们可以定义一个函数 $f(a)=x^{a} \bmod N$，可以证明 $f(a)$ 是一个周期为 $r$ 的函数，即 $f(a+r)=f(a)$。因此，求阶问题可以转化为寻找函数 $f(a)$ 的周期 $r$，这和 $\text{QFT}$ 或 $\text{QPE}$ 密切相关。

算法准备

我们定义一个将在求阶问题中用到的幺正算符

$$U_x|y\rangle=|xy\ {\mathrm{mod}}\ N\rangle$$

其中 $y\in\{0,1\}^{\otimes L},L=\lceil\log N\rceil,N<2^L$, $0\leq y\leq N-1$，并且 $x$ 和 $N$ 互质。

用整数 $0\leq s \leq r-1$ 构造态 $\ket{u_s}$

$$|u_s\rangle=\frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}\exp\left(-2\pi i\frac{s}{r}k\right)|x^k{\mathrm{mod}}N\rangle$$

这个态共有阶数 $r$ 项，可以证明

$$U_x|u_s\rangle=\exp\left(2\pi i\frac{s}{r}\right)|u_s\rangle$$

我们可以使用量子相位估计来获得相位 $\frac{s}{r}$，从而求出阶 $r$。然而态 $\ket{u_s}$ 依赖于未知的阶 $r$ 且很难制备，幸运的是，我们发现

$$\frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}|u_s\rangle=|1\rangle\equiv|\underbrace{0,0,\ldots,0,}_{L-1}1\rangle$$

其中 $L=\lceil\log N\rceil$ 是存储 $N$ 所需的比特数。$\ket{1}$ 可以很容易地制备，但是这样使用量子相位估计会令得到的结果为所有 $\ket{u_s}$ 的相干叠加，我们来看如何处理这个问题。

算法步骤

$\text{step\ 1}$：准备两个寄存器，第一寄存器含有 $n=2L+1+\lceil\log(2+\frac{1}{2\varepsilon})\rceil$ 个量子比特且被初始化为 $|0\rangle\equiv|0\rangle^{\otimes n}$，第二寄存器含有 $L$ 个量子比特。初始态被制备在

$$|\psi_1\rangle=|0\rangle|1\rangle$$

$n=2L+1+\lceil\log(2+\frac{1}{2\varepsilon})\rceil$ 是为了满足连续分数定理的，这保证了能给出阶 $r$ 的有效估计

$\text{step\ 2}$：对第一个寄存器施加 $\text{Hadamard}$ 变换，得到所有态的等权重相干叠加

$$\begin{aligned} |\psi_2\rangle=H^{\otimes n}|\psi_1\rangle=\frac{1}{\sqrt{2^n}}\sum_{j=0}^{2^n-1}|j\rangle|1\rangle \end{aligned}$$

$\text{step\ 3}$：定义模幂算符 $U_{x,n}$，其作用为

$$U_{x,n}|j\rangle|y\rangle=|j\rangle U_x^j|y\rangle=|j\rangle|x^jy\ {\mathrm{mod}}\ N\rangle$$

$U^j_x$ 意味着进行 $j$ 次 $U_x$ 操作，是一个受控 $\text{U}$ 门。将 $U_{x,n}$ 作用在态 $|\psi_2\rangle$ 上，得到

$$\begin{aligned} \left|\psi_{3}\right\rangle & \begin{aligned} =U_{x,n}|\psi_2\rangle=\frac{1}{\sqrt{2^n}}\sum_{j=0}^{2^n-1}|j\rangle U_x^j|1\rangle \end{aligned} \\ & =\frac{1}{\sqrt{2^n}}\sum_{j=0}^{2^n-1}|j\rangle U_x^j\frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}|u_s\rangle \\ & \begin{aligned} & =\frac{1}{\sqrt{2^nr}}\sum_{j=0}^{2^n-1}\sum_{s=0}^{r-1}\exp\left(2\pi i\frac{s}{r}j\right)|j\rangle|u_s\rangle \end{aligned} \end{aligned}$$

$\text{step\ 4}$：若上式没有对 $s$ 的求和项，此时我们已经可以通过量子相位估计计算 $r$ 了。现在我们强行对第一个寄存器施加逆量子傅里叶变换 $\hat{F}^{-1}$，得到

$$\begin{aligned} \left|\psi_{4}\right\rangle & =\hat{F}^{-1}|\psi_3\rangle=\frac{1}{\sqrt{2^nr}}\sum_{j=0}^{2^n-1}\sum_{s=0}^{r-1}\exp\left(2\pi i\frac{s}{r}j\right)\left[\hat{F}^{-1}|j\rangle\right]|u_s\rangle \\ & \begin{aligned} & =\frac{1}{\sqrt{2^nr}}\sum_{j=0}^{2^n-1}\sum_{s=0}^{r-1}\exp\left(2\pi i\frac{s}{r}j\right)\frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^n-1}\exp\left(-2\pi i\frac{jk}{2^n}\right)|k\rangle|u_s\rangle \end{aligned} \\ & =\frac{1}{2^n\sqrt{r}}\sum_{j,k=0}^{2^n-1}\sum_{s=0}^{r-1}\exp\left[2\pi i\left(\frac{s}{r}-\frac{k}{2^n}\right)j\right]|k\rangle|u_s\rangle \end{aligned}$$

$\text{step\ 5}$：当两个寄存器的状态给定时，测量第一个寄存器得到 $k$ 的概率为

$$P(k)=\frac{1}{2^{2n}r}\left|\sum_{j=0}^{2^n-1}\exp\left[2\pi i\left(\frac{s}{r}-\frac{k}{2^n}\right)j\right]\right|^2$$

分情况讨论

1.若 $2^n$ 被 $r$ 整除

$$\begin{aligned} \sum_{j=0}^{2^n-1}\exp\left[2\pi i\left(\frac{s}{r}-\frac{k}{2^n}\right)j\right] & =\frac{1-\exp\left[2\pi i\left(s\frac{2^n}{r}-k\right)\right]}{1-\exp\left[2\pi i\left(s\frac{2^n}{r}-k\right)\frac{1}{2^n}\right]}=2^n\delta_{k,s2^n/r} \end{aligned}$$

那么

$$|\psi_4\rangle=\frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}|s\frac{2^n}{r}\rangle|u_s\rangle$$

在测量后，我们将会得到一个态 $|\frac{2^n}{r}s\rangle\equiv|b\rangle$，但是我们仍然不知道 $s$ 和 $r$ 的值。然而我们可以通过将 $b$ 和 $2^n$ 除以他们的公因子来得到 $r$ 的值，使得 $r$ 和 $s$ 互质。

2.若 $2^n$ 不被 $r$ 整除

我们总可以使用一个 $k$，定义 $\delta_k=\frac{s}{r}-\frac{k}{2^n}$，其中 $k^{\prime} \in [0,2^n-1]$，使得 $|\delta_{k^{\prime}}| \leq \frac{1}{2^{n+1}}$。

当 $s/r$ 在右半部分 $0\leq\frac{s}{r}-\frac{k^{\prime}}{2^n}\leq\frac{1}{2^{n+1}}$，我们有 $0\leq2\pi i\delta_{k^{\prime}}j\leq\pi i\frac{j}{2^n}\leq\pi i$

当 $s/r$ 在左半部分 $-\frac{1}{2^{n+1}}\leq\frac{s}{r}-\frac{k^{\prime}}{2^n}<0$，我们有 $-\pi i\leq-\pi i\frac{j}{2^n}\leq2\pi i\delta_{k^{\prime}}j\leq0$

无论 $\delta_{k^{\prime}}$ 为正还是负，相位因子之和都会在同一个半复平面内相干叠加，从而导致 $P(k^{\prime})\approx\frac{1}{r}$。

对于其他 $k\neq k^{\prime}$ 的情况，相位因子 $2\pi i\delta_{j}$ 有时位于复平面的上半平面，有时位于下半平面，从而导致相干相消，因此概率 $P(k)$ 可以忽略不计。

现在我们可以以相对高的概率 $\frac{1}{r}$ 得到 $\frac{s}{r}$ 的很好的近似。我们可以通过连分式展开找到 $\frac{s}{r}$ 的最简分数形式，从而以某个精度得到阶 $r$。（连分式定理的有效性可以被证明）

1. 对于不同的 $s$，$k^{\prime}$ 通常不同
2. 若 $s$ 和 $r$ 有公因子，那么通过连分式展开得到的 $r$ 可能不是最小阶，需要多次运行算法以获得正确的阶 $r$。

求阶算法的缺点说结果仍是不确定的，因为测量结果依赖于 $s$ 的选择，而 $s$ 是随机的。

Shor 分解质因数算法

算法步骤如下：

step 1：随机选择一个小于 $N$ 的整数 $x$。

step 2：计算 $\gcd(x,N)$，如果 $\gcd(x,N)\neq 1$，那么我们已经找到了 $N$ 的一个非平凡因子 $\gcd(x,N)$，算法结束。

step 3：如果 $\gcd(x,N)=1$，使用求阶算法找到 $x$ 的阶 $r$。

step 4：如果 $r$ 是奇数，那么重新回到 $\text{step\ 1}$。

step 5：如果 $r$ 是偶数，若 $x^{r/2}\equiv -1(\bmod N)$，那么重新回到 $\text{step\ 1}$。

step 6：计算 $\gcd(x^{r/2}-1,N)$ 和 $\gcd(x^{r/2}+1,N)$，它们将会是 $N$ 的非平凡因子，算法结束。

证明：如果 $r$ 是 $x$ 模 $N$ 的阶数，那么 $x^r\equiv 1(\bmod N)$，因此

$$x^r-1=\left(x^{r/2}-1\right)\left(x^{r/2}+1\right)=nN,n\in\mathbb{Z}$$

$\left(x^{r/2}-1\right) \left(x^{r/2}+1\right)$ 能被 $N$ 整除，但 $\left(x^{r/2}-1\right)$ 和 $\left(x^{r/2}+1\right)$ 都不能被 $N$ 整除（否则 $r$ 不是最小正整数或违背 step 5），这意味着 $N$ 的质因数被拆分在了 $\left(x^{r/2}-1\right)$ 和 $\left(x^{r/2}+1\right)$ 中，使用 $\gcd$ 就能提取出来。$\gcd(x^{r/2}-1,N)$ 和 $\gcd(x^{r/2}+1,N)$ 将会以极高的概率给出 $N$ 的质因数。