江苏龙网

  1. 首页 > 人文 > >

老王科技 另一个角度看量子计算：与弹球碰撞的惊人关联

选自acm.org
作者：DonMonroe
机器之心编译
编辑：Panda
从看似无关的主题中发现某种共同特质是件挺有意思的事 ， 而且说不定会带来理解事物的新方式 。 本文探讨了著名量子算法Grover搜索算法与完全弹性碰撞这一问题之间的关联 。
老王科技 另一个角度看量子计算：与弹球碰撞的惊人关联
文章图片
在科学和数学领域 ， 许多看似无关的主题之间存在某些共同的特质 。 这样的相似性有时能同时为这两个领域带来重大的进展 ， 不过很多时候这样的相似性只是单纯地很有趣 。
去年12月 ， 谷歌一位物理学家AdamBrown发现：一种基本量子计算算法与一种用于计算无理数π的奇妙方法之间存在一种异常精确的关系 。 「目前来说这个发现只是单纯很有意思 ， 但我们希望找到思考事物的新方式 ， 人们未来也许能使用这种方式寻找之前无法看到的联系 。 」Brown说 ， 「对于一个现象 ， 多种思考角度是非常有用的 。 」
在网上发布的一篇预印本论文中（目前尚未完成同行评议） ， Brown表明两个看似无关的问题之间存在某种数学上的相关性 。 其中一个问题是为量子计算机提出的著名的Grover搜索算法 ， 理论上它比任何经典搜索算法都更快 。 另一个问题则是一个出人意料的过程：通过统计理想弹性球的碰撞次数来得到任意精度的π值 。
量子算法
量子计算要用到量子比特 ， 每个量子比特可以同时表示两个状态 ， 而它们通常用离子或超导回路构建 。 从原理上看 ， 一定数量的量子比特能表示和操作比经典比特多指数级数量的组合 。 之前 ， 人们觉得利用这种概率性质来进行计算似乎是一场白日梦 ， 但是研究者还是成功设计出了可从量子比特提取有用信息的算法 。
第一个量子算法是彼得·秀尔（PeterShor）1994年提出的秀尔算法 ， 当时他正在新泽西州的贝尔实验室工作 。 秀尔算法能高效地将整数分解为质因数 ， 也由此给现今的许多加密方案带来了潜在的威胁 。 该算法的诀窍是将整数分解重构为一个新问题：确定一个序列的重复周期 。 这本质上是一种傅立叶变换 ， 通过在量子比特的全集上使用全局运算就能找到这个序列 。
【老王科技 另一个角度看量子计算：与弹球碰撞的惊人关联】第二个基本算法则是LovGrover于1996年在贝尔实验室独立提出的Grover算法 ， 它有着大不一样的工作方式 。 「秀尔算法和Grover算法是两种最典型的量子算法 。 」德克萨斯州大学奥斯汀分校的ScottAaronson说 ， 「即便在今天 ， 我们所知的绝大部分量子算法都要么受秀尔算法启发 ， 要么受Grover算法启发 ， 要么同时受两者启发 。 」
Grover算法通常被描述为一个数据库搜索过程 ， 即检查一个包含N项的列表 ， 找到其中满足所需性质的一项 。 如果该列表已按某种标签进行了排序（比如按字母顺序排列） ， 那么通过不断连续减半地切分列表 ， 就可以找到任意标签；这个过程所需的查询次数为log?N 。 但是 ， 对于无序列表 ， 检查完每一项平均需要N/2步（有可能需要多达N步） 。
和其它量子算法一样 ， Grover算法也会同时操作整个量子比特集 ， 同时保留它们之间的关系（过早地查询任意量子比特会使其状态确定下来 ， 从而将其转换成一个普通比特 ， 这会消除量子计算所带来的优势） 。 但是 ， Grover的研究表明：通常仅需次全局操作就能找到所需的项 。
这样的提升没有秀尔算法所带来的提升多 ， 因为秀尔算法带来的是指数级的提升 。 但Brown强调说：Grover算法可应用于更一般的、非结构化的问题 。
Grover算法的计算首先是对所有N个量子比特进行均等混合 。 然后 ， 该算法会反复让所有量子比特进行两种轮流交替的操作 。 第一个操作是嵌入该目标：它会反转一个特定但未知的比特的状态 。 该任务的目标是确定哪个比特被修改了 ， 但方法不是观测所有比特 。 第二个操作不需要有关该目标的任何信息 。 Grover发现每次重复该序列时 ， 该目标在混合结构中的权重都会增大（尽管这无法被观测到） 。 重复了适当的次数之后 ， 此时执行一次观测 ， 则有非常高的可能性能得到正确结果 。


推荐阅读


上一篇：湘湘带你看社会 同江市公安局联合相关单位对全市中小学幼儿园开展安全检查

下一篇：幸福一箩筐 长丰公交再添80台新能源公交车！看完图片我只能说高大上！