量子那些事儿 关注
手机版

为什么计算机科学家们应该了解量子计算?(二):用量子比特计算

  1. 云栖社区>
  2. 量子那些事儿>
  3. 博客>
  4. 正文

为什么计算机科学家们应该了解量子计算?(二):用量子比特计算

雪花又一年 2018-05-17 15:36:41 浏览361 评论0

摘要: 用量子比特计算 量子比特(qubit)是计算观点对量子力学的基础贡献之一. 一般而言, 对于可区分维量子系统的量子态, 我们可以用上的一个单位矢量来描述它. 最简单而有趣的情形即是, 这样的系统就叫量子比特(qubit).

用量子比特计算

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


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

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


因此, 说到随机计算和量子计算最关键的不同, 它“仅仅”是把实数换成了复数(甚至允许负实数), 以及用于度量态矢量模长的范数从\ell_1换成了\ell_2. 也就是说, 于量子态而言, 其态矢量各分量的概率幅平方和等于1; 而概率矢量的分量的和为1, 且并没有平方. 然而, 在计算中, 可以用不同的相位作为不同分支这一事实, 意味着当我们重新组合它们的概率幅的时候, 概率幅可能得到增强(即相长干涉)或者削弱(即相消干涉). 如果“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}. 要是我们测量这个态, 那么得到结果0或者1的概率都是1/2. 然而, 如果我们对初态“0”作用两次\sqrt{\text{NOT}}门, 那么我们得到的结果是“1”. 这展示了量子叠加和经典随机性之间的核心差异: 将一个量子态进行叠加, 那么它不会有任何不可逆的信息丢失. 当我们有n个量子比特的时候, 叠加和干涉使得我们能得到更大的计算优势. 一个著名的例子就是 Grover 算法: 给定一个n比特二进制函数f, 我们要找到一个满足f(x)=1的输入x \in \{0, 1\}^n, 这里仅仅需要计算f大约2^{n/2}次, 即平方级加速. 正是概率是概率幅的平方这一事实, 使得 Grover 算法得以可行. 因此, 在2^n个基矢量上的均匀叠加的量子态, 对应着每个基矢量的概率幅都是1/\sqrt{2^ n}. 更进一步地, 我们能够演示计算f造成的影响, 并且这样的影响是可比较的: 每个目标量子态x(即f(x)=1)的概率幅大致以1/\sqrt{{2^n}}的速度增长, 而这样的破坏仅仅出现在总概率幅非常大的时候. 因此, 总影响(渐进时间复杂度)的阶是2^{n/2}; 或者更一般地, 对于M个解有\sqrt{2^n/M}.

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

然而, 量子计算机却能够概率幅近似表示为一系列\sqrt{r/2^n}的量子态的叠加,即考虑每个z, z+r, z+2r, \cdots, 这里的z是某个随机选择的z \in \{ 0, 1, \cdots, r-1 \}. 迄今为止, 这很像一个概率算法, 选择随机的x用于计算f(x). 此外, 根据对f(x)的, 选择考虑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, 得到的叠加态中y的概率幅约为\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). 如果yr能够近似地被2^n整除, 那么它的和会非常大; 反之, 如果yr并不能近似地整除2^n, 它会涉及到很多不同相位的复数, 不难验证, 此时它们倾向于互相抵消. 因此, 测量y会返回一个接近2^n/r的倍数的答案. 最终, 通过经典连分数展开算法, 我们重新得到了r.


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

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

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

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


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

【云栖快讯】你想见的Java技术专家都在这了,向大佬提问,有问题必答  详情请点击

网友评论

雪花又一年
文章1321篇 | 关注43
关注
阿里云流计算(Aliyun StreamCompute)是运行在阿里云平台上的流式大数据分析... 查看详情
提供一种性能卓越、稳定、安全、便捷的计算服务,帮助您快速构建处理能力出色的应用,解放计算给服... 查看详情
一种适用于大规模并行批处理作业的分布式云服务。可支持海量作业并发规模,系统自动完成资源管理,... 查看详情
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
阿里云总监课正式启航

阿里云总监课正式启航