量子计算 - 阿贝尔稳定子问题与 Shor 算法

Posted on Jun 01, 2022 By WXM

在信息的度量中我提到了, 量子信息讨论的是量子态的基底不变的性质. 而在量子计算中, 输出 $0$ 与输出 $1$ 是截然不同的计算结果. 也就是说, 为了讨论量子计算, 我们必须先指定系统的一个基底, 并且标记每一个基向量. 这样被指定的基底便是我在量子过程的表示中定义的计算基底.

量子计算机

在量子计算中, 一个 $d$ 维系统 $\hilb$ 加上一个由字母表 $\Gamma$ 索引的一个计算基底被称为(量子)寄存器. 为了简单起见, 通常我们选择字母表为从 $0$ 到 $d-1$ 的阿拉伯数字 $\qty{0,1,2,3,\cdots, d-1}$. 对于物理系统, 我们也可以用自旋箭头符号 $\qty{\uparrow,\downarrow}$ 来做索引. 注意, 即使我们用阿拉伯数学来索引基向量, 理论上基向量之间不一定有序关系, 基向量之间也不能做代数运算. 不过对于某些问题来说, 给基向量赋予一个循环群 $\integer_d$ 结构对算法设计来说也是有益的. 在接下来的讨论中我们默认 $\Gamma = \qty{0,1,2,3,\cdots, d-1}$ 上存在这样的循环群结构.

在给定字母表后, 我们可以把寄存器的基向量记为 $\qty{\ket{0},\ket{1},\cdots, \ket{d-1}}$. 这些基向量对应的态被称为经典态, 也就是经典 (确定性) 计算机可以达到的状态. 量子寄存器区别于经典寄存器的一点就是, 它可以处于不同经典态的叠加态 $\cos(\theta)\ket{0} + e^{i\phi}\sin(\theta) \ket{1}$ 上.

一个被很多人忽视的问题是, 仅仅给定基向量并不足以唯一地定义叠加态. 因为在量子系统中, 相差一个全局相位的 $\ket{0}$ 与 $e^{i\eta}\ket{0}$ 本质上都是同一个密度算子 $\ketbra{0}{0}$ 的不同记号. 如果我重新定义基向量 $\ket{0^\prime}:= e^{i\eta}\ket{0}$, 那么 $\cos(\theta)\ket{0} + e^{i\phi}\sin(\theta) \ket{1}$ 同样可以被写做 $e^{-i\eta}\cos(\theta)\ket{0^\prime} + e^{i\phi}\sin(\theta) \ket{1}$. 如果我们仅仅把 $\ket{0}$ 与 $\ket{0^\prime}$ 当作经典态, 它们是无法被区分的, 这个相位 $e^{i\eta}$ 就成为了一个额外自由度. 因此, 在我们定义 $\ket{0}$ 的时候, 我们除了定义经典态, 同时还定义了什么是初始相位 $\eta = 0$ 以及相位的方向.

实际上从经典态出发, 这样定义寄存器的方式并不那么漂亮. 这个初始相位没有物理上的参考点, 似乎仅仅是数学上的一种随意选择. 一个更紧凑的定义方法是通过量子操作, 而非量子态来完成的.

漂移与时钟

我们在量子寄存器上可以定义两个不同的操作: 漂移 $X$ 与时钟 $Z$. 其中漂移算子 $X$ 对所有基向量做了一个 $\ket{k} \to \ket{k\oplus 1}$ 的交换操作. 这里 $\oplus$ 代表着循环群 $\integer_d$ 上的加法, 即相加再模 $d$. 而时钟 $Z$ 给每一个基向量加上了一个相位 $\ket{k} \to \omega^k \ket{k}$. 其中 $\omega = e^{2\pi i/d}$ 是单位 $1$ 的 $d$ 次根.

看似如上定义的量子操作同样是由基向量得到的, 但实际上它们是由代数结构所定义的. 经典态则应当被定义为时钟算子 $Z$ 的本征态.

正则对易关系

我们要求漂移与时钟算子满足 Weyl 正则对易关系:

  1. $XZ = \omega ZX$;
  2. $X^d = Z^d = 1$;

从物理的角度来说, 这个正则关系是位置算子 $\hat{x}$ 与动量算子 $\hat{p}$ 的对易关系的离散形式, 即 $X = e^{it \hat{x}}, Z = e^{it \hat{p}}$. 根据位置动量关系 $[X,P] = i$ 以及 BCH 公式

\[XZ = e^{it(\hat{x}+\hat{p})}e^{it/2} = e^{it}e^{it(\hat{x}+\hat{p})}e^{-it/2} = e^{it}ZX\]

既这是时间 $t= \log(\omega) = \frac{2\pi}{d}$ 时的正则对易关系.

另一方面这两个算子定义了离散傅里叶变换 $W$ 的两个基底 $Z = WXW^\dagger$. 在 $Z$ 的基底下, 傅里叶算子

\begin{equation} W = \frac{1}{\sqrt{d}} \left( \begin{matrix} \omega^{0\cdot 0} & \omega^{0\cdot 1} & \cdots & \omega^{0\cdot (d-1)} \\
\omega^{1\cdot0} & & \cdots & \omega^{1\cdot (d-1)} \\
\vdots & \vdots & & \vdots \\
\omega^{(d-1)\cdot0} & \omega^{(d-1)\cdot1} & \cdots & \omega^{(d-1)\cdot (d-1)} \end{matrix} \right) \end{equation}

对所有基向量 $\ket{x}$, $W\ket{x} = \ket{p_x} := \frac{1}{\sqrt{d}} \sum_{s\in \Gamma} \omega^{x\cdot s}\ket{s}$ 是 $X$ 算子的本征态.

在如上条件下, 我们可以说寄存器是由 $\spX = (\hilb,X,Z,\Gamma)$, 即空间 $\hilb$, 寄存器上的两个操作 $X,Z$, 以及用来索引 $Z$ 的本征态的字母表 $\Gamma$ 所定义的四元组构成的. 量子计算与经典计算的主要差别之一就是这个 $Z$ 操作的存在. 它使得我们可以同时在计算基底与傅里叶基底上操作量子态.

Stone-von Neumann 定理告诉我们, 所有满足正则对易关系的 (不可约) $X,Z$ 都是酉等价的. 也就是说两对 $(X,Z)$ 与 $(X^\prime,Z^\prime)$ 之间差了一个唯一的酉变换, 或者说基底变换. 这意味着每一对不可约 $(X,Z)$ 唯一地确定了一个寄存器的基底. 为了避免额外自由度的影响, 我们默认 $X,Z$ 不可约, 即寄存器的维数 $d$ 是质数. 对于 $d$ 是合数的情况, 我们只需要把它当成一个复合寄存器, 其中每个子寄存器的维度是 $d$ 的一个质因子.

量子门操作

量子计算机自然不可能只包含一个寄存器. 量子计算的过程是多个寄存器协作的过程. 为了简单起见, 在计算中我们一般选择相同的寄存器 $\spX$.

量子计算的过程包括三个部分:

  1. 每个寄存器 $\spX$ 内部的门操作, 即一个局域的酉变换;
  2. 寄存器之间的通信, 一般由控制门完成;
  3. 对寄存器的测量;

门操作其实指的是对布尔门操作, 即与, 或, 非门的推广. 对于一个 $d$ 维的寄存器, 数学上在它上面的局域门操作等价于 $d$ 维的酉变换. 而 $k$ 个寄存器上的门就是在 $d^k$ 维的空间中的酉变换. 通过多寄存器门操作, 信息得以在不同寄存器之间流通. 寄存器的测量与量子态的测量没有本质上的区别. 但是由于物理上的限制, 我们通常认为只能对每个寄存器进行局域的测量. 不过由于量子态与测量的对偶性, 我们可以通过逆基底变换去模拟任意测量的结果.

通常我们认为单一寄存器上的操作是容易的, 而多寄存器上的操作是困难的. 因此我们通常只考虑少数种类的多寄存器操作. 实际上单比特门加上一个控制门便可以完成所有的量子计算过程. 控制门通常是定义在 $Z$ 基底上的:

\[C\pi := \ketbra{c}{c}_a \otimes (\sum_t \ketbra{\pi(t)}{t}_b) + (\mathbb{I}_a - \ketbra{c}{c}_a)\otimes\mathbb{I}_b\]

即如果寄存器 $a$ 上的态处于 $\ket{c}$, 则对寄存器 $b$ 上进行一个交换操作 $\pi: b\to \pi(b)$, 否则什么都不做. 不难看出这个操作是一个酉操作.

当维度 $d$ 是质数的时候, $X,Z$ 可以被用来构造 Wootters 相点算子 (phase point operator)

\[A_{x,p} = \frac{1}{d} \sum_{j,m = 0}^{d-1} \omega^{xj-pm+jm/2} X^j Z^m = \frac{1}{d} \sum_{j,m = 0}^{d-1} \omega^{xj-pm} \omega^{j\hat{x}+m\hat{p}} \ .\]

这 $d^2$ 个相点算子构成了 $d$ 维厄米算子的一组正交基: $H = \frac{1}{d}\sum_{p,q} \Tr[HA_{p,q}] A_{p,q}$. 这个 $\mu_H(p,q) := \frac{1}{d}\Tr[H A_{p,q}]$ 被称为量子态的伪概率表示. 因为 $\sum_{p,q} \mu_\rho(p,q)$ 对所有的量子态都为 $1$, 看起来这类似于概率分布. 但是这个伪概率的值可以为负, 因而它不是真的概率. 量子态无法被表示为真概率这件事情本身也是量子优势的来源的一种1

这个相点算子的名字来源于位置与动量 $x,p$ 构成了一个粒子的相空间. 而在离散系统中, 它们可以被看作相空间上的一张网格 (注意, 这个网格的左右以及上下是联通的, 这个空间实际上是一个甜甜圈型, torus). 每一个 $A_{p,q}$ 都是这张网格上的一个点. 这张网格上有 $d(d+1)$ 条直线 $\lambda := ax+bp = c$. 如果对每一条线进行加和

\[A_\lambda := \sum_{\lambda} A_{x,p}\]

构成了一个投影算子2. 对给定斜率 $(a,b)$, 这 $d$ 条平行的线构成了一组寄存器的标准正交基, 或者说一组投影测量. 这个标准正交基同时也是 Heisenberg-Weyl 算子 $\sigma_{a,b} := \omega^{ab/2}X^aZ^b$ 的本征态. 对这 $d+1$ 个基底进行的测量被称为 Pauli 测量. 一般我们认为 Pauli 测量在量子计算中是简单的.

对于二维系统, 即量子比特系统, 这三个基底便是 Pauli 算子 $X,Y,Z$ 的本征态. 一般分别被记作 $\ket{+},\ket{-}$; $\ket{+i},\ket{-i}$; 以及 $\ket{0},\ket{1}$.

阿贝尔稳定子问题

在算法问题中, 有一类非常重要的问题叫功能性问题 (function problem). 在功能性问题中定义了一个函数 $F(x,y) \to \qty{\text{True}, \text{False}}$. 我们希望每当给出一个 $x$, 程序可以算出一个 $y$ 使得 $F(x,y) = \text{True}$. 简单的理解就是在解方程. 功能性问题占据了现实中的计算问题的一大部分. 函数的计算问题就是其中一种. 其对应的功能性函数: $F(x,y):=$ f(x) == y, 即找到一个使得 $f(x)=y$ 成立的 $y$.

功能性问题虽然很有用, 但是在理论计算机中, 它太过复杂了. 因此在理论研究中大家更关注于判定问题, 也就是图灵机可以解决的问题. 这也是大家比较熟悉的 P, NP 等复杂度问题的基础. 判定问题与功能性问题之间有很多直接但是比较微妙的联系, 并且可以相互转化. 我们通常说的 ‘P 问题是可以在多项式时间内被算出来的问题’ 其实是不对的. P 问题指的是可以在多项式时间内被判定的问题, 而多项式时间内可以被计算的问题是功能性 P 问题, 即 FP 问题. 不过由于 P 与 FP 在很多时候可以相互归约, 我们在很多时候会模糊掉他们之间的区别. 对于功能性问题, 我们同样可以定义 FNP 问题, 即那些 $F(x,y)$ 可以被高效计算的问题. 值得注意的是, 计算机科学中最重要的问题 P=NP? 与 FP=FNP? 是等价的. 因而在科普中一般都是用 FP=FNP 的定义去描述 P=NP. (实际上 NP 的定义更加复杂, 我这里用的也只是一种等价描述)

如果对于所有可以被高效计算的函数 $F(x,y)$, 我们都可以通过调用 $F(x,y)$ 多项式次找到满足条件的 $y$, 那么这等价于在多项式时间内解决了 NP 问题. 这个被调用的 $F(x,y)$ 的计算程序被称为预言机 (oracle). 如果我们可以找到一个量子算法能用预言机以比较高的概率得到一个满足条件的 $y$, 那么量子计算机就可以处理 NP 问题. 然而我们并不知道是否存在这样的算法. 不过 Kitaev 在 Shor 算法的基础上给出了一类特殊的 $F(x,y)$, 使得它在量子计算机上可以用多项式次预言机被计算3. 这一类问题包含了大数分解, 离散对数等我们至今不知道是否属于 P 的问题. 这么多年来我们一直找不到经典计算机在多项式时间内可以解决这些问题的算法.

Kitaev 给出的这一类问题的是阿贝尔稳定子问题. 它的定义为 $F(x,y):=$ f(x,y) == x and y != 0. 其中 $f(x,y)$ 构成了一个群作用:

\[f(x,0) = x; \quad f(x,yz) = f(f(x,y),z) \ .\]

更具体的说, 我们把输入 $x$ 编码到字母表 $\Gamma$ 上. 每一个 $y$ 代表着 $\Gamma$ 上的一个置换, 而我们所关注的就是 $\Gamma$ 的置换群的一个子群 $G$. 如果我们可以计算这个置换群的任意子群, 这个稳定子问题就可以囊括图同构问题. 然而 Kitaev 的算法只能解决阿贝尔群问题, 即 $yz = zy, \quad \forall y,z\in G$. 不过即使是只能解决阿贝尔群的稳定子问题, 这也足以动摇大多数非对称加密算法的数学根基了. 稳定子 $G_x$ 这个名字来源于源于, 如果 $y\in G_x$ 都满足 f(x,y) == x, 那么将 $G_x$ 中的元素作用到 $x$ 上任意多次, $x$ 也不会被改变.

阿贝尔稳定子问题与量子计算的关系源于一个群论的重要定理

有限阿贝尔群基本定理

由于 $\Gamma$ 是有限的, 这个 $G$ 必然是有限的. 而所有有限阿贝尔群都同构于 $\bigoplus_{i=1}^k \integer_{p_i}$. 其中 $p_i$ 是一些质数的幂.

根据该定理, 每一个有限阿贝尔群 $G$ 中的元素都可以用 $k$ 个整数表示: $(z_0,z_1,\dots,z_{k-1})$. 在这个同构下, 这个群 $G$ 显然可以被编码到 $k$ 个 $p_i$ 维的寄存器上. 每一个经典态 $\ket{y} := (\ket{z_0},\dots,\ket{z_{k-1}})$ 都对应了一个群元素. 同样的, 我们可以把每一个整数映射到一个相位 $\phi_i = e^{i 2\pi z_i / p_i}$ 上. 可以看到这个向量 $(\phi_1, \phi_2,\dots, \phi_k)$ 在元素乘法下与 $\bigoplus_{i=1}^k \integer_{p_i}$ 或者说 $G$ 是同构的.

在这个群表示下, 我们希望找到商群 $H_x = G/G_x$ 的生成元. 有意思的是这个商群 $H_x$ 与 $x$ 的轨道 $G(x) := \qty{g(x): g\in G}$ 有着一一对应的关系. 商群 $H_x$ 中的每一个元素 $aG_x := \qty{ag: gx=x, g\in G}$ 作用在 $x$ 上得到的都是 $G(x)$ 中的一个元素 $ax$.

由此引出了阿贝尔稳定子算法:

阿贝尔稳定子算法

首先, 我们准备三组寄存器: $X,Y,O$, 全部初始化为 $0$ 态, 其中 $X,O$ 的维度相同, $Y$ 是 $k$ 个 $p_i$ 维寄存器复合而成的. 其中 $X,Y$ 记录的是 $f(x,y)$ 的输入, 而 $O$ 记录的是函数的输出.

  1. 将输入 $X$ 录入到寄存器 $X$ 中:

    \[\ket{x}_X\ket{0}_Y\ket{0}_O \ ;\]

  2. 对 $Y$ 中的每一个寄存器进行傅里叶变换:

    \[\frac{1}{\sqrt{\abs{G}}} \ket{x}_X (\sum_y \ket{y}_Y) \ket{0}_O \ ;\]

  3. 使用预言机计算 $f(x,y)$, 把结果存入 $O$:

    \[\frac{1}{\sqrt{\abs{G}}} \ket{x}_X (\sum_y \ket{y}_Y \ket{f(x,y)}_O) \ ;\]

  4. 再次对 $Y$ 进行傅里叶变换:

    \[\frac{1}{\abs{G}} \ket{x}_X (\sum_{s,y} \omega^{s\cdot y}\ket{s}_Y \ket{f(x,y)}_O) \ ;\]

  5. 对 $Y,O$ 进行测量

要理解这个算法, 关键是把第 4 步的态重写为

\[\frac{1}{\abs{G}} \ket{x}_X \sum_{z}\sum_{s}\qty(\sum_{y: f(x,y)=z} \omega^{s\cdot y})\ket{s}_Y \ket{z}_O \ ;\]

这里 $z$ 是轨道 $G(x)$ 中的元素, 而这个括号中是对商群 $H_x$ 中的等价类 $\qty{g: gx=z, g\in G}$ 求和. 这里的内积 $\omega^{s\cdot y} := \prod_i \omega_i^{s_i\cdot y_i}$, $s_i,y_i \in \integer_{p_i}$.

考虑最小周期 $r_i$, 以及最小的 $y_i^\ast$ 使得 $f(x,y^\ast) = z$. 这样所有满足 $f(x,y)=z$ 的 $y$ 都可以被表示为 $y^\ast_i + b_i r_i$ 组成的向量. 因此

\[\sum_{y: f(x,y)=z}\omega^{s\cdot y} = \sum_{y: f(x,y)=z}\prod_i \omega_i^{s_i\cdot y_i^\ast + s_i\cdot(b_i r_i)} = \prod_i \omega_i^{s_i\cdot y_i^\ast}\sum_{b_i} \omega_i^{s_i\cdot(b_i r_i)}\]

在测量中, 态 $\ket{s}_Y\ket{z}_O$ 出现的概率即上式的模方 \(P(s,z) = \frac{1}{\abs{G}^2}\vert{\sum_{y: f(x,y)=z}\omega^{s\cdot y}}\vert^2 =\prod_i \vert{\sum_{b_i} \omega_i^{s_i\cdot(b_i r_i)}}\vert^2 =\prod_i \vert{\frac{\omega_i^{m_i r_i s_i}-1}{\omega_i^{r_i s_i}-1}}\vert^2 \ .\)

这最后一个等式来源于等比数列求和. $m_i$ 即不同的 $y_i$ 的数量. 如果某一个 $i$ 对应的 $r_i y_i = 0$, 则那一项等于 $m_i$. 我们可以继续用三角函数化简这个概率. 假设 $\frac{r_i s_i}{p_i}$ 离最近的整数差 $\delta_i \leq \frac{1}{2p_i}$

\[\begin{aligned} P(s,z) &= \frac{1}{\abs{G}^2}\prod_i \frac{\vert\sin^2(\frac{\pi m_i r_i s_i}{p_i})\vert^2}{\vert\sin^2(\frac{\pi r_i s_i}{p_i})\vert^2} \\\\ &= \frac{1}{\abs{G}^2}\prod_i \frac{\vert\sin^2(\pi m_i \delta_i)\vert^2}{\vert\sin^2(\pi \delta_i)\vert^2} \\\\ &\geq \frac{1}{\abs{G}^2}\prod_i \frac{\vert\sin^2(\pi m_i \delta_i)\vert^2}{(\pi\delta_i)^2} \\\\ &\geq \frac{1}{\abs{G}^2}\prod_i \frac{(2 m_i \delta_i)^2}{(\pi\delta_i)^2} \\\\ &= \frac{1}{\abs{G}^2}\prod_i \frac{4 m_i^2}{\pi^2} = \frac{4}{\pi^2} \frac{\prod_i m_i^2}{\abs{G}^2} \ . \end{aligned}\]

第一个缩放源于 $\abs{\sin(x)} \leq \abs{x}$, 而第二个缩放源于 $\delta_i \leq \frac{1}{2p_i}\leq \frac{1}{2m_i}$, 且对于 $x\in[0,\frac{pi}{2}]$ 有 $\sin(x) \geq \frac{2x}{\pi}$. 实际上由于 $s_i$ 是均匀分布的, 满足 $\frac{r_i s_i}{p_i}$ 与整数差 $\delta_i$ 的 $s_i$ 的数量乘 $m_i$ 与 $p_i$ 刚好是一样多的. 测量的结果是以不小于 $\frac{4}{\pi^2}$ 的概率得到一个 $s_i$, 使得 $\frac{r_i s_i}{p_i}$ 接近一个整数. 注意, 这个概率与 $z$ 是无关的, 我们实际上测的是函数的周期 $r_i$. 因为 $p_i$ 是已知的, $s_i$ 是被测量的, 而 $\frac{r_i s_i}{p_i}$ 接近一个整数, 所以我们可以估计出 $r_i$ 的大小.

我这里假设 $\frac{r_i s_i}{p_i}$ 接近一个整数. 但其实如果寄存器的维度跟群表示是一样的, 那它们必然刚好是一个整数. 我们测得正确结果的概率为 $1$. 现实中我们一般是在量子比特系统中工作的. 我们的寄存器的维度只能是 $2$ 的幂, 因此会有一定的错误率. 即使是这样, 我们上面给出的也是一个比较松的下界. 一般情况下真实的正确率应该远好于这个下界.

在测得 $s_i$ 后, 只要我们用经典计算机检验任何一个 $y_i$ 的周期是否是 $r_i$, 我们就可以知道测量的结果是否正确. 只要我们得到了所有非平凡 $r_i$, 只要我们把任意一个非平凡 $y_i$ 作用 $r_i$ 次, 得到的 $y = (y_0,y_1,\dots,y_{k-1})$ 就是一个非平凡的稳定子. 每一次正确的测量得到的 $r_i$ 是平凡的概率是 $\frac{1}{m_i}$, 因此重复 $k$ 次, 每次都得到平凡的概率 $\frac{1}{m_i^k}$ 是指数小的. 如果某个 $m_i=1$, 在这个维度上就不存在非平凡的结果. 当我们测量多次以后, 如果一直是平凡的结果, 我们基本就可以说这个维度应该没有非平凡解.

Ref:

  1. Veitch, Victor, et al. “Negative quasi-probability as a resource for quantum computation.” New Journal of Physics 14.11 (2012): 113011. ↩

  2. Ferrie, Christopher, and Joseph Emerson. “Framed Hilbert space: hanging the quasi-probability pictures of quantum theory.” New Journal of Physics 11.6 (2009): 063040. ↩

  3. Kitaev, A. Yu. “Quantum measurements and the Abelian stabilizer problem.” arXiv preprint quant-ph/9511026 (1995). ↩