业界 | 首次理论证明:Science论文提出超越经典计算的量子算法

机器之心报道

参与:晓坤、王淑婷、张倩

近日,来自 TMU、滑铁卢大学和 IBM 的研究者在 Science 上发表论文,首次证明了量子算法可以在特定代数问题上拥有相对于经典算法的理论优势,而在此之前,这还只是个猜想。

Science 评论道:

人们预期量子计算机在求解特定计算问题的时候其性能比经典计算机更高。这种预期基于计算复杂度理论中一个有充分根据的猜想,但严谨地把量子算法和经典算法进行对比是很难实现的。Bravyi 等人在理论上证明了,并行量子电路求解特定线性代数问题时需要的计算步骤和问题规模无关,而类似的经典电路需要的计算步数随着问题规模的增长而指数级增加。这就是所谓的量子优势,源于量子电路中存在的量子关联,这在经典电路中是无法被重现的。

论文:Quantum advantage with shallow circuits

论文地址:http://science.sciencemag.org/content/362/6412/308

arXiv 地址:https://arxiv.org/pdf/1704.00690.pdf

多年来,量子计算机不仅仅是一个想法,人们还在为此付诸行动。如今,企业、政府和情报机构都在投资发展量子技术。现在,TUM 复杂量子系统理论研究院教授 Robert König,与滑铁卢大学量子计算研究所的 David Gosset 以及来自 IBM 的 Sergey Bravyi 合作,已经为这个充满希望的领域奠定了基石。

传统计算机遵循经典物理定律。它们依赖二进制数 0 和 1。这些数字被储存并用于数学运算。在传统的储存单元中,每个比特(信息的最小单位)都由一个电位来表示,该电位决定该比特设置为 1 还是 0。

但在量子计算机中,一个比特(量子比特)可以同时为 0 和 1。因为量子物理定律允许电子一次占据多个状态。因此,量子比特(qubit)以多个重叠状态存在。这种所谓的叠加允许量子计算机一次对多个值执行操作,而单个传统计算机必须顺序执行这些操作。量子计算的前景在于能够更快速地解决某些问题。

从猜想到证明

König 和他的同事决定性地证明了量子计算机的优势。为此,他们开发了一种可以求解一类特别困难的代数问题的量子电路。新的电路有很简单的结构:它仅在每个量子比特上执行固定数量的运算。这样的电路被称作拥有固定的深度。在他们的研究中,研究者证明了这个问题不能用固定深度的经典电路求解。他们还进一步回答了量子算法超越所有经典电路的原因:量子算法利用了量子物理的非局域性。

在本研究之前,量子计算机的优势既没有得到证明,也没办法用实验方法进行展示,尽管有证据指向这个可能。一个实例是 Shor 的量子算法,该算法有效解决了大数素因子分解问题。然而,这仅仅是一个复杂的理论猜想,没有量子计算机,这个问题就无法有效解决。也可以理解为高效的方法是存在的,只是经典计算机还没找到。

Robert König 认为,新的结果主要是对复杂理论的贡献。他表示,「我们的结果表明,量子信息处理的确有很多优点——不必依赖于未证明的复杂理论猜想。」除此之外,该研究为量子计算机研究树立了新的里程碑。由于结构简单,这一新的量子电路可以作为量子算法近期实验实现的备选对象。

参考内容:https://phys.org/news/2018-10-proof-quantum-advantage.html

原文发布于微信公众号 - 机器之心(almosthuman2014)

原文发表时间:2018-10-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CDA数据分析师

如何成为大神级数据科学家 | Kaggle Grandmaster是怎样炼成的

Vladimir I. Iglovikov 是一名 Kaggle 顶级大师(Grandmaster),曾获得过 Carvana 图像遮蔽挑战的冠军,以及 Dst...

24320
来自专栏PPV课数据科学社区

案例分享|美团如何用NLP完成5大应用场景

针对NLP技术,大神们刚刚展开过比较激烈的讨论——Yann Lecun论战Yova Goldberg,导火索是是一篇“对抗式生成自然语言的论文”。 NLP大神Y...

55590
来自专栏人工智能快报

深度学习可听到机器故障信号

人们绝不想开车开到在路上出故障了才想起要日常保养,但预防性维护检查或定期维护检查经常发现不了可能会出现的问题。一家初创公司提出了更好的办法:利用人工智能去听车辆...

41860
来自专栏IT派

麻省博士的机器学习经验干货分享

我的一个朋友最近正要开始人工智能的研究,他问及我在 AI 领域近两年的研究中有哪些经验教训。本文就将介绍这两年来我所学到的经验。其内容涵盖日常生活到 AI 领域...

7410
来自专栏新智元

机器学习先驱 Michael I. Jordan 清华演讲:更好的分布式机器学习(PPT)

【新智元导读】今天,机器学习诸多理论的主要奠基人、美国三院院士 Michael I. Jordan受聘为清华大学访问教授,同时发表主题报告。Jordan认为,大...

51660
来自专栏人工智能头条

【AI每日播报】周志华最新论文、Redis之父9条忠告、百度又搞了个大新闻

26530
来自专栏人工智能LeadAI

如何准备机器学习工程师面试

人们用很多东西来比喻准备面试的过程。有人说这像准备一场战争,也有人说像邀请某人出去约会,还有人说像在高尔夫大师赛上打进最后一个洞。准备面试是一个令人兴奋,又或者...

37160
来自专栏机器之心

Kaggle Grandmaster是怎样炼成的

最近,Vladimir 分享了自己成为 Kaggle 高手的经验。目前,Kaggle 注册用户数量已超 100 万,其中只有 124 人拥有 Grandmast...

11830
来自专栏大数据文摘

Nature新研究 | 科学家的职业巅峰可以被预测吗

18140
来自专栏机器学习算法与Python学习

一份MIT博士的学习心得,送你入坑机器学习?(可下载PDF)

14660

扫码关注云+社区

领取腾讯云代金券