为什么计算机科学家们应该了解量子计算?（二）：用量子比特计算-阿里云开发者社区

用量子比特计算

量子比特(qubit)是计算观点对量子力学的基础贡献之一. 一般而言, 对于可区分维量子系统的量子态, 我们可以用 $\mathbb{C}^d$ 上的一个单位矢量来描述它. 最简单而有趣的情形即是 d=2 , 这样的系统就叫量子比特(qubit). 考虑对态矢量 $x=\begin{pmatrix}x_0\\x_1\\\end{pmatrix}$ 的测量, 为了保证得到结果的概率是 |x_0|^2 , 并且得到结果的概率是 |x_1|^2 , 那么必须是单位矢量. 如此说来, 任何一个线性动力系统都是可能的备选方案, 只要能够保证态矢量的模长不变. 换句话说, 这样的演化把态矢量从映射到, 这里的是酉矩阵(unitary), 即它能够保证态矢量的模长不变. 在数学上, 这等价于 $U^{\dagger}U = I$ , 即对于每个矩阵元有 $(U^{\dagger})_{ij} = \bar{U}_{ji}$ . 这个解释的美妙之处, 在于它是与实现系统无关的, 这样的系统可能是光子的极化, 也可能是原子中某个电子的能级, 还可能是原子核的自旋, 亦或是超导线圈中的电流方向. 因此, 量子比特是一种设备无关的量子信息描述方式. 它就像是经典信息中的比特一样, 我们能够从中推理出信息, 却不必知道它究竟是编码在何处, 不管是在RAM(Random-Access Memory, 随机访问存储器)上, 在硬盘上, 还是在算盘上.

于物理实验而言, 单量子比特的情形已经足够有趣了. 但从计算观点来看, 量子比特情形下发生的事情更吸引我们. 此时, 一个量子态就是 $\mathbb{C}^{2^n}$ 中的一个单位矢量. 那么, 对于矢量空间单位正交基中的每个元素, 我们都用一个比特字符串标记. 大多数量子比特的量子态是纠缠的, 这意味着它们的振幅在某种意义上, 对比特串的各处都是关联的. 酉矩阵给出了这样的系统的动力学描述, 它们由一系列两比特量子门构成. 为了表示作用在具体的量子比特上的量子门, 比如第个或者第个量子比特, 我们考虑一个矩阵元 $U_{ij}$ $U_{i j}$ 非零当且仅当比特字符串中和等于或者的酉矩阵. 进一步地, $U_{ij}$ 的值应该只取决于四个比特, 即 i_3, j_3, i_7 和 j_7 .

这样的线性代数形式看起来似乎很抽象, 但它还可以被用于描述经典的确定性计算和随机计算. 对于经典的确定性计算, 虽然有些浪费, 但确实用比特字符串来表示. 譬如说对于长度为 2^n 的矢量, 其中只有一个分量为, 其余均为的情形. 那么考虑一个 0/1 矩阵, 且其中每列只有一个, 这样的动力学描述即表示了从到的映射. 事实上, 随机计算(译者注: 指的就是 Markov 过程)也是类似的. 只不过此时的状态矢量的各个分量均为非负实数, 且它们的和为. 对于任何仅有非负矩阵元, 且每一列矩阵元和为的矩阵, $x \mapsto Mx$ 都是有效的状态转移. 在一般意义上, 这样的图象忽视了一个事实: 一些比特的变换比另一些更容易. 那么为了表示单个操作, 即两比特操作, 我们也需要用一个矩阵. 它满足对于所有未作用比特 i,j , 有 $M_{i,j}=0$ , 即 $M_{i,j}$ 的值仅仅取决于其对应的比特和是否被作用. 这启示我们, 如果我们不对一个比特作用, 那么它不应该发生变化.

因此, 说到随机计算和量子计算最关键的不同, 它“仅仅”是把实数换成了复数(甚至允许负实数), 以及用于度量态矢量模长的范数从 $\ell_1$ 换成了 $\ell_2$ . 也就是说, 于量子态而言, 其态矢量各分量的概率幅平方和等于; 而概率矢量的分量的和为, 且并没有平方. 然而, 在计算中, 可以用不同的相位作为不同分支这一事实, 意味着当我们重新组合它们的概率幅的时候, 概率幅可能得到增强(即相长干涉)或者削弱(即相消干涉). 如果“0”用矢量 $\begin{pmatrix}1\\0\\ \end{pmatrix}$ 表示, 而“1”用矢量 $\begin{pmatrix}0\\1\\ \end{pmatrix}$ 表示, 那么非(NOT)操作能够表示(不论量子或经典情形)为 $\begin{pmatrix}0&1\\1&0\\ \end{pmatrix}$ . 论及它的几何意义, 这是一个角度为 $\pi/2$ 的旋转. 然而, 只有量子计算机才能作用“非门的平方根”, 这样的量子门即 $\pi/4$ 旋转:

$\sqrt{\text{NOT}} = \begin{pmatrix} 1/\sqrt{2} & -1/\sqrt{2}\\ 1/\sqrt{2} & 1/\sqrt{2}\\ \end{pmatrix}$ .

如果我们从量子态“0”开始, 然后作用一个 $\sqrt{\text{NOT}}$ 门, 那么我们会得到态 $\begin{pmatrix}1/\sqrt{2} \\ 1/\sqrt{2} \\ \end{pmatrix}$ . 要是我们测量这个态, 那么得到结果或者的概率都是 1/2 . 然而, 如果我们对初态“0”作用两次 $\sqrt{\text{NOT}}$ 门, 那么我们得到的结果是“1”. 这展示了量子叠加和经典随机性之间的核心差异: 将一个量子态进行叠加, 那么它不会有任何不可逆的信息丢失. 当我们有个量子比特的时候, 叠加和干涉使得我们能得到更大的计算优势. 一个著名的例子就是 Grover 算法: 给定一个比特二进制函数, 我们要找到一个满足 f(x)=1 的输入 $x \in \{0, 1\}^n$ , 这里仅仅需要计算大约 $2^{n/2}$ 次, 即平方级加速. 正是概率是概率幅的平方这一事实, 使得 Grover 算法得以可行. 因此, 在 2^n 个基矢量上的均匀叠加的量子态, 对应着每个基矢量的概率幅都是 $1/\sqrt{2^ n}$ . 更进一步地, 我们能够演示计算造成的影响, 并且这样的影响是可比较的: 每个目标量子态(即 f(x)=1 )的概率幅大致以 $1/\sqrt{{2^n}}$ 的速度增长, 而这样的破坏仅仅出现在总概率幅非常大的时候. 因此, 总影响(渐进时间复杂度)的阶是 $2^{n/2}$ ; 或者更一般地, 对于个解有 $\sqrt{2^n/M}$ .

而用于分解整数的 Shor 算法的加速, 于经典计算而言更为戏剧性. Shor 算法有更为本质的经典部分, 即把素因子分解(Factoring)问题转化为更抽象的寻阶问题(Period-finding). 这个问题输入是一个在集合 $\{0,1,\cdots,2^n-1\}$ 上函数, 满足性质 f(x)=f(y) 当且仅当 x-y 能够整除某些隐含周期. 它的目标是寻找合适的. 既然相对于来说可以指数大, 如果我们把视作一个黑盒, 那么经典计算机用于寻找它的时间自然是指数的.

然而, 量子计算机却能够概率幅近似表示为一系列 $\sqrt{r/2^n}$ 的量子态的叠加,即考虑每个 $z, z+r, z+2r, \cdots$ , 这里的是某个随机选择的 $z \in \{ 0, 1, \cdots, r-1 \}$ . 迄今为止, 这很像一个概率算法, 选择随机的用于计算 f(x) . 此外, 根据对 f(x) 的, 选择考虑的分布. 但算法的下一步是量子的, 并且应用了一类称为量子 Fourier 变换(Quantum Fourier Transform, QFT)的酉矩阵. 这个矩阵中的矩阵元为 $(y,z)=e^{2 \pi i yz/2^n}/\sqrt{2^n}$ . 为了有效的执行算法, 我们需要经典快速 Fourier 变换(Fast Fourier Transform, FFT)的量子版本. 但是它们的相异之处同样是戏剧性的: 因为它是对量子态的概率幅进行变换, 而不是像经典的 FFT 一样作用在一串数上. 在这种情形下应用 QFT, 得到的叠加态中的概率幅约为 $\frac{r}{2^n}(1+e^{\pi i \frac{y r}{2^n}}+e^{\pi i \frac{2yr}{2^n}}+e^{\pi i \frac{3yr}{2^n}}+\cdots)$ . 如果能够近似地被 2^n 整除, 那么它的和会非常大; 反之, 如果并不能近似地整除 2^n , 它会涉及到很多不同相位的复数, 不难验证, 此时它们倾向于互相抵消. 因此, 测量会返回一个接近 2^n/r 的倍数的答案. 最终, 通过经典连分数展开算法, 我们重新得到了.

一旦我们开发出了新的公钥密码系统来抵抗量子计算机的攻击, 量子模拟就在实践上逐渐变得更加重要. 而 Shor 算法所展示的量子计算的力量, 甚至远不能用令人惊讶来形容, 因为这一问题的解决和量子力学并没有明显的联系. 在 Shor 算法之后, 人们越来越难以相信量子力学能够被经典计算机有效模拟. 在此之前, 很多科学家们寄希望于基于量子力学的模型, 希望它能够控制那些反直觉特征, 比如指数大的态矢量空间, 并且要保持它们与我们的观测相容. 但是现在, 我们知道这些模型并不能简化量子力学自身(或者说, 至少并不容易模拟), 除非素因子分解问题(Factoring)和寻阶问题(Period-finding)在经典计算机上有更快的算法. 这样的情形就像是 NP 完全性(NP-Completeness)的发展, 即昭示了不同领域在求解 NP-Complete 问题的努力, 在实际上是等价的.

Shor 算法和 Grover 算法是最著名的量子算法, 但并不是唯一的两个. 比如最近提出的一个量子算法, 即用于求解大的线性方程组的 HHL 算法[1]: 给定一个矩阵和一个矢量, 找到满足 Ax=b 的. 然而, 不像这一问题的经典算法, 量子版本的和都是量子态(因而我们可以只用个量子比特表示 2^n 维的矢量). 更进一步地, 必须是稀疏的, 并且对于给定的隐含表示满足给定任意行指标, 能够有效的找到所有的非零 $A_{ij}$ . 这一限制使得它能够在理论上在多项式时间里解决指数大小的方程组. 然而, 需要说明的是: 算法的运行时间还取决矩阵的条件数的大小, 条件数是一个关系到经典计算机上求解线性方程组的数值稳定性的参数. 找一个能够使用这一算法的自然的情形, 是一个引人注目的未解决问题(Open Problem).

另一个最近的算法上的进展是 Metropolis 采样算法(Metropolis sampling)的量子对应[2]. 对于经典情形, Metropolis 法是是一种在指数大小的状态空间上, 从难于分析的分布中采样的方法. 事实上, 这是一个通过使用随机性来得到指数级加速的例子, 而刻画对计算模型的改变会使得它变得多么强大也并不令人着迷. 它应用范围很是出乎意料, 包括统计推断和关于非负矩阵的排列(the permanent of a nonnegative matrix)的近似算法[3], 但是它最初的发展, 是对系统的热力学分布采样所引起的. 如果一个状态有能量 E(x) , 那么在温度下的热力学分布与 $e^{-E(x)/T}$ 成比例, 所以更低的温度会使得系统更难以转化到低能态情形. 类似地, 量子 Metropolis 算法也从热力学分布中产生量子态. 就像它的经典版本一样, 量子 Metropolis 算法花费更多时间去产生低温态, 正如其往往解决更困难的优化问题一样. 但是除了少数情形, 证明其运行时间的严格的界(bound), 在一般意义上是困难的. 尽管没有形式化的证明, 我们仍然能够运行经典 Metropolis 算法, 并且经验地观察到它在很多情形下执行的很快. 而对于量子 Metropolis 算法的经验观察, 当然需要等到第一台真正的大规模量子计算机出现. 但是我们已经知道了足够的工具, 如果我们能够指出如何组合它们, 以此使用量子 Metropolis 算法作为子过程设计新的量子算法, 就像非负矩阵的排列算法使用经典 Metropolis 算法一样.

人们仍然在不断地提出着使用量子计算机的新想法, 而一个令人兴奋地进展是, 我们找到了越来越多的只需要或稍多些量子比特的应用. 量子比特的数量足够小, 意味着它能够很容易被经典计算机有效模拟, 特别是当我们并不能展示量子比特间足够大的相互作用之前. 这样的量子计算设备能够被用于提高量子测量的精度(比如原子钟, 或者测量引力波), 在网络中作为“量子中继器(quantu repeater)”分发用于密码学协议的纠缠, 或者甚至用于构建能够组成任意尺寸孔径的望远镜阵列. 正如经典计算机使用, 远远超过了作为计算模型的 Turing 机看起来的那样, 量子计算设备的使用也会变得比我们现在的想象更加广泛.

原文发布时间为：2017.02.01
本文作者：Climber.pI
本文来源：知乎，如需转载请联系原作者。

为什么计算机科学家们应该了解量子计算?（二）：用量子比特计算

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

为什么计算机科学家们应该了解量子计算?（二）：用量子比特计算

热门文章

最新文章

相关电子书