江苏龙网

  1. 首页 > 人文 > >

cnBeta微软研究人员攻克了两个已有20年历史的量子计算问题

与传统计算机相比 ， 量子计算机可以利用量子纠缠和叠加原理来显著提升计算速度 。 近日 ， 由RobinKothari带领的微软研究团队 ， 就在两个已经持续20多年的常见问题的研究上取得了重大的突破 。 具体说来是 ， 研究团队重新讨论了一些重要问题类别中最大可行的量子加速问题 ， 且其算法能够在比例量子计算机上实现指数级的加速 。
cnBeta微软研究人员攻克了两个已有20年历史的量子计算问题
文章图片
非结构化问题的量子加速研究（来自：Microsoft）
早在2019年的时候 ， RobinKothari与研究合著者HaoHuang就已经实现了一定的突破 。
该设想解决了困扰人们已久的灵敏度猜想问题 ， 且证明了针对非结构化问题的最佳量子加速是四次（TversusT^4） 。
幸运的是 ， 新研究表明 ， 同样的证明方法 ， 亦可用于回答有关图形量子加速的古老猜想 。 该问题具体涉及分析大量非结构化数据集 ， 并在其中查找潜在的连接与模式 。
1999年的时候 ， Buhrman等人提出——任何量子算法都必须查询Ω（√n）次 ， 才能确定单调图的性质 。
推测答案的复杂度与时间呈线性相关 ， 与最优解相对的最坏情况边界为Ω（n） ， 可借助Grover算法来实现 。
近日 ， Kothari团队以最优方式证明了这一猜想 。 鉴于与该猜想有关的经典对应物尚未得到证明 ， 微软研究人员的这项成果也是独一无二的 。
【cnBeta微软研究人员攻克了两个已有20年历史的量子计算问题】最惊讶的是 ， 我们竟然能够完全解出这个量子模拟猜想 ， 而经典版本仍然未能解决 。


    推荐阅读


    上一篇：Tech情报局腾讯和华为互相开炮了，QQ删图片被EMUI系统拦截？为了这事

    下一篇：钨丝woosmart要赚多少钱才算是财富自由？