写点什么

已经证明:量子计算机能比传统计算机更快解决特定问题

2018 年 11 月 07 日

已经证明:量子计算机能比传统计算机更快解决特定问题

来自 IBM T.J.Watson 研究中心,加拿大滑铁卢大学(University of Waterloo)和德国慕尼黑工业大学(Technical University of Munich)的研究员们已经在理论上证实了量子计算机能够比传统计算机更快地解决特定问题。他们设计的算法已经达到当前量子计算机处理器的计算能力极限,实验证明可能即将推出。

严格来说,Sergey Bravyi、David Gosset 和 Robert König 等三位研究员证明了:

在恒定的时间周期内运行的并行量子算法一定比经典算法更加强大;在解决与二元二次型相关的特定线性代数问题上它们很可能更优。

他们提供的证据基于一种算法,以解决可以在量子常数深度中实现的二次“隐式线性函数”问题。隐式线性函数是一个不完全已知的线性函数,但它“隐藏”在你可以计算的另一个函数中。例如,一个线性函数可以隐藏在一个可以查询的 oracle 中。挑战是基于应用已知函数的结果来充分表征隐式线性函数。如果这听起来有点类似于将公钥反转以找到其私钥的问题,那么这并不意外,因为这正是它所要解决的问题

在Oracle 的例子中,这个问题通过经典的 Bernstein-Vazirani 算法解决,该算法最小化对 oracle 的查询次数。根据三位研究员的观点,Bernstein-Vazirani 算法被应用于 oracle 的事实限制了它的实际适用性,所以他们建议在二维网格图中“隐藏”一个线性函数。在证明这种做法确实可行之后,他们建立了一个量子常量深度算法来找出隐藏的函数。

研究员们提供的另一半证据表明,与量子电路相反,任何传统电路都需要随输入数量的增加而提高其深度。例如,量子算法可以用一个最大深度为10 的量子电路解决该问题,而无论你有多少输入,但反过来看传统呢,对于16 个输入的问题,需要一个深度为10 的传统电路;对于32 个输入的问题,需要一个深度14 的电路;对于64 个输入的问题,需要一个深度20 的电路等等。

证明的第二部分在哲学上是非常有趣的,因为它详述了量子非局域性的概念,而量子非局域性又与量子纠缠有关,量子纠缠与叠加是量子处理器最独特的特性之一。所以,量子优势似乎来自量子物理学最本质的特性。

在理论层面上,这一成就的价值也不可低估。IBM IBM Q 副总裁 Bob Sutor 写道

这个证明是量子算法和经典算法之间无条件分离的首次证明,尽管是在恒定深度计算的特殊情况下。

以前,量子计算机比经典计算机更强大的想法是基于因式分解问题。 Shor 指出,量子计算机可以在多项式时间内对整数进行因子分解,也就是说比任何已知的经典计算机算法更高效。尽管这是一个有趣的结果,但它并不排除确实可以找到更高效的经典因式分解算法的可能性。因此,除非人们猜想根本不存在高效的因式分解问题解决方案,这等价于证明” P ≠ NP “,否则人们不能真正地说量子优势被证明。

如上所述,Bravyi、Gosset 和 König 的算法依赖于恒定数量的操作(量子电路的深度),这似乎正好适合当前量子计算机处理器的局限。这些基本与量子位的错误率和相干时间有关,它们限制了操作序列的最大持续时间及其总数。因此,使用短深度电路是当前量子电路任何可行应用的关键。Sutor 说,由于所提出的算法的这种特性,IBM 的研究人员已经开始使用 IBM 量子计算机来证明量子优势。

如果你有兴趣了解证明的全部细节,请不要错过 David Gosset 在普里美特理论物理研究所(Perimeter Institute for Theoretical Physics)的演讲以及演示幻灯片

查看英文原文 https://www.infoq.com/news/2018/10/quantum-advantage-proved-ibm

感谢冬雨对本文的审校。

2018 年 11 月 07 日 09:111156

评论 2 条评论

发布
暂无评论
发现更多内容

阿里大牛八年打造,编程宝典,从初学到编程进阶—深入学习—实战

Java~~~

Java 阿里巴巴 程序员 架构 编程语言

《ZooKeeper分布式过程协同技术详解》.pdf

田维常

电子书

React 灵魂 23 问

局外人

Java 前端 React

用 Python 实现定时自动化收取蚂蚁森林能量

Python小二

Python

实现2nm工艺突破,台积电为何能给“摩尔定律”续命?

脑极体

Appium常用操作之「Toast提示信息获取」

清菡

五、一致性哈希算法

Geek_28b526

Nacos实战及其源码分析

程序员Fox

Spring Cloud nacos spring cloud alibaba

网络冲浪信任危机频发,区块链能否破局?

CECBC区块链专委会

区块链 征信透明

结合实战和源码来聊聊Java中的SPI机制?

冰河

Java spi 服务发现

git使用与原理剖析及其私服搭建

程序员Fox

git

看“区块链”如何为外贸企业融资

CECBC区块链专委会

区块链 银行

阿里内部“新鲜出炉”手慢无!首发面试终极指南V3.0,符合一线大厂面试知识点+面试题

Java架构追梦

Java 阿里巴巴 架构 分布式 面试手册

架构师训练营第 1 期第 9 周作业

好吃不贵

极客大学架构师训练营

消灭微服务的坏味道 之 循环依赖

码猿外

微服务 循环依赖 坏味道

Spring Cloud Config 实现分布式配置中心

AI乔治

Java 架构 微服务 Spring Cloud

LeetCode 热题 - 递归

哈希说

LeetCode

区块链的新信任模式将重塑传统金融业

CECBC区块链专委会

区块链 资产流动性

《使用C ++的数据结构和程序设计》限时免费下载

计算机与AI

c++

第五周 - 作业

leo

极客大学架构师训练营

架构师训练营第 1 期 - 第九周作业

Todd-Lee

极客大学架构师训练营

MyBatis 面试题(附答案解析)

比伯

Java 大数据 编程 架构 面试

Redis 分布式锁原理看这篇就够了, 循循渐进

源码兴趣圈

redis 架构 分布式 分布式锁

给,你们想要的内存溢出MAT排查工具

田维常

内存溢出

第五周-笔记

leo

极客大学架构师训练营

架构师训练营第 1 期 - 第九周总结

Todd-Lee

极客大学架构师训练营

接口的幂等性的多重考虑,你会了吗?

moon聊技术

Java 接口

石、火、水:从OriginOS透视移动系统进化论

脑极体

Maven-技术专题-Setting文件结构解析

李浩宇/Alex

大专学历Java开发7年,从年初被裁到四面美团点评成功上岸,闭关七个月,入职那一天我哭了!

Java架构追梦

Java 阿里巴巴 面试 美团 java架构

架构师系列之6: python实现一致性hash

桃花原记

演讲经验交流会|ArchSummit 上海站

演讲经验交流会|ArchSummit 上海站

已经证明:量子计算机能比传统计算机更快解决特定问题-InfoQ