江苏龙网

  1. 首页 > 资讯 > 资讯 > >

量子计算机|到底什么是量子计算( 二 )


本文图片

【量子计算机|到底什么是量子计算】图1 量子线路和量子门 。 量子线路由量子比特的初始化、一组量子门以及最终的信息读取组成 。 其中的量子门可以由矩阵表示
与经典计算机中的通用逻辑门类似 ， 在量子计算机中任意的幺正变换均可以通过一组有限的幺正变换(量子门)的组合以任意的精确度近似 。 这样一组量子门被称为通用量子门 。 例如 ， Hadamard门(H)、π/4 相位门(S)、π/8 相位门(T)以及受控非门(CNOT)构成一组通用量子门[5] 。 这里面H、S 和T为单量子比特门 ， CNOT为两量子比特门(图1) 。 利用这些量子门 ， 不仅可以实现任意的量子算法 ， 还可以实现任意的经典算法 。 从这个意义上说 ， 显然量子计算机的计算能力是大于等于经典计算机的 。
1986 年 ， 多伊奇和乔沙(R. Jozsa)提出了一个计算问题来表明量子计算机的确在解决某些问题上具有优势[6] 。 他们提出的问题是判断一个函数f ：x→0 ， 1对于不同的输入x 是否给出相同的输出0 或1 。 函数f 需要满足一定的条件 ， 这里不再赘述 。 对于输入为一个比特的情况 ， 也就是x有两个取值0 和1 ， 用经典计算机解决这个问题需要计算f 至少两次 。 而用量子计算机只需要计算f一次 ，这个量子算法被称为多伊奇— 乔沙(Deutsch—Jozsa)算法 。
当输入比特增多的时候 ， 确定性经典算法需要计算f 的次数随着比特数量指数增长 ， 而量子算法仍然只需要计算f 一次 。
 多伊奇-乔沙问题·
在多伊奇—乔沙问题中 ， 函数f 需要满足如下条件：要么所有的输出均相同；要么在所有的输入x中 ， 一半的输出为0 ， 一半的输出为1 。 对于n 个输入比特的情况 ， 总共有2n种可能的输入x ， 有可能在查看2n/2+1 种输入以后才发现有不同的输出 。 因此 ， 在经典计算中确定性的解决多伊奇—乔沙问题需要进行2n/2+1 次计算 。
1994 年 ， 肖尔(P. Shor)提出了能够解决因数分解问题的量子算法 ， 被称为肖尔(Shor)算法[7] 。 利用已知最好的经典算法 ， 因数分解所需的时间随着整数长度次指数增长 。 由于指数函数增长非常快 ， 当整数达到一定长度时 ， 经典计算机无法有效地进行因数分解 。 广为使用的RSA密码系统正是基于这一点 。 然而 ， 量子算法所需的时间随着整数长度代数增长 ， 要远远慢于指数函数 。 因此 ， 量子计算机可以更快地对大整数进行因数分解 。 利用量子计算机 ， 我们可以破解经典计算机无法破解的密码 ， 给密码系统的安全性带来了挑战 。 当然 ， 对于有些密码算法 ， 还没有发现像肖尔算法这样可以进行破解的量子算法 。 因此 ， 抵御量子计算对密码安全的威胁有两种方式 ， 一种是基于量子物理的量子密钥分发 ， 另一种是后量子密码 ， 也就是量子计算还无法破解的经典密码算法[8] 。
1996 年 ， 劳埃德(S. Lloyd)提出了可以模拟局域相互作用量子系统演化的通用量子计算机算法[9] 。 根据这个算法 ， 模拟量子系统演化的误差可以趋近于零 ， 而算法所需的资源随着子系统个数、误差等参数的变化是一个代数函数 。 因此 ， 通用量子计算机可以有效模拟量子系统演化 。 基于对演化的模拟 ， 量子计算机还可以用来求解某些量子系统的基态能量等问题 。 量子系统的演化和基态能量是两个非常重要的计算问题 ， 在物理、化学和材料等学科的研究中均有应用 。
目前计算机已经广泛应用于日常生活的方方面面 。 但在计算机技术普及以前 ， 它的两个主要应用是密码破译以及科学计算和模拟 。 非常巧合的 ， 量子计算机两个重要的算法——肖尔算法和量子模拟算法分别对应了这两种应用 。 这两个算法有清晰的应用背景以及对经典算法的优势 ， 因此极具代表性 。 如果能够在量子计算机上演示这两个算法 ， 并且用来解决经典计算机无法解决的实例 ， 或许可以认为最终实现了通用量子计算机 。
除了本文介绍的 ， 目前还有很多其他的量子算法[10] 。 应该注意到 ， 不是对于所有的计算问题量子算法都有指数加速 。 在算法方面量子计算机和经典计算机的对比有大量计算复杂性理论的研究[5] 。
到目前为止 ， 所有的结论都是基于拥有通用量子计算机这一假设 。 那么 ， 我们有可能制造一台通用量子计算机吗？事实上 ， 由于普遍存在的退相干现象 ， 严格的幺正变换量子门是不可能百分百实现的 。 关键是这种退相干对计算结果有多大影响 ， 是否在许可误差范围内 。
03
退相干
量子计算所需的量子门是幺正变换 。 在量子力学理论中 ， 幺正变换描述了一个封闭系统的演化 。 然而 ， 在自然界中我们还没有发现真正的封闭系统：一个物理系统总是或多或少地与外界环境存在相互作用 。 由于相互作用的影响 ， 系统演化不仅由系统本身决定还取决于环境的状态 。 其结果是系统演化一般不再是幺正变换 。
我们用完全正定映射来描述量子系统最一般性的演化 。 有些非幺正演化会使量子系统逐渐失去相干性 ， 也就是量子叠加态无法持续 ， 这个过程就被称为退相干 。
退相干会导致量子算法失去优势 。 1998 年 ， 本文作者之一及其合作者讨论了退相干对肖尔算法的影响 ， 发现退相干会降低成功求解因数的概率[11] 。 当概率过低时 ， 量子算法的效率不再高于经典算法 。 事实上 ， 在物理系统中执行的量子门相对理想量子门的任何偏离都有可能导致量子计算的结果错误 ， 进而量子算法失效 。


推荐阅读


上一篇：中央气象台：今年第9号台风“美莎克”昨日生成

下一篇：上海有3例确诊病例今日出院，共计829例治愈出院