AICon全球人工智能与机器学习技术大会周四开幕,点击查看完整日程>> 了解详情
写点什么

猫、量子位和远距传动:令人匪夷所思的量子计算世界(第二部分)

  • 2018 年 7 月 17 日
  • 本文字数:5250 字

    阅读完需:约 17 分钟

关键要点

  • 远距传动是最先被描述的量子信息处理过程之一。它使用纠缠在瞬间远距离传输信息,但它不能用于传送大型物体,如人或猫。
  • 一旦人们意识到量子系统的计算复杂性实际上是一种计算能力,那么量子信息理论就真正起飞了。它可以被应用于其他问题上,例如在公钥密码学中用到的因子分解。
  • Shor 的对数算法并没有破坏密码学,“量子安全”加密协议已经在开发当中。
  • Shor 的算法是第一个量子“杀手级应用”。两年后,出现了第二个,也就是 Grover 的搜索算法。Grover 算法可以在 O(n) 时间内搜索未排序的数据库。
  • 在过去几年中,随着量子计算和机器学习逐渐升温,人们很自然会想是否可以把它们结合起来。到目前为止,答案似乎是肯定的。

为了理解为什么量子计算机会如此有趣,有必要简要地挖掘一下复杂性理论。虽然它看起来与我们大多数人日常工作相去甚远,但复杂性理论不只是出现在大学课堂或求职面试的白板上。量子计算之所以这么快,并不是因为量子计算机的处理速度(其实它的速度很慢)或计算机的内存速度(对速度影响微乎其微),而是因为它的算法。量子计算机的新算法具有与经典等价算法完全不同的复杂性特征。

研究复杂性的人将问题按照复杂性进行分类。一个给定的问题可能属于多个类,并且有很多复杂的类,因此,有时候也将其称为复杂性动物园。所幸的是,我们只需要了解少数几个。顾名思义,NP-hard 问题就是指难以解决的问题。随着解决方案中元素(数字、点或城市)数量的增加,它们会变得更加难以解决。NP-complete 问题是一类NP-hard 问题,其解决方案可以推广到解决任何其他NP-hard 问题。NP-complete 问题的有效算法正是复杂性理论的终极解决方案(但量子计算不提供这个解决方案)。

复杂性类不仅通过大O 符号来定义,一般来说,NP-hard 问题用事物的数量进行多项式缩放——也就是说,它们在2 的O(log(n)) 次方时间内是可解的。这意味着,计算3 个点需要8 秒(这是合理的),计算10 个点需要17 分钟(已经不是很合理了),计算20 个点需要12 天(有点荒谬),计算40 个点需要35,000 年(逆天了)。或者换句话说,硬件在计算完成26 个点计算之前就已经过时了,对于31 个点的计算,任何编写程序的人很可能在得到答案之前就已经死了。

重要的量子算法

运距传动

虽然运距传动不是一种计算,但如果少了它,对量子信息的讨论就是不完整的。运距传动是最先被描述的量子信息处理过程之一。它使用纠缠在瞬间远距离传输信息,但它不能用于传输大型物体,如人或猫。它仅适用于单个粒子,甚至不传输实际粒子,只传输有关其状态的信息。它可以传输粒子的全量子位丰富(full qubit-rich) 状态,这让关心量子态的人感到非常兴奋。量子信息不能通过经典的信道传输,因为量子态的任何经典测量都会破坏它(“失稳”)。

量子信息无法被复制(“无克隆”定理),因此传送粒子信息会破坏原始粒子的状态,这可能是“远距传动”这个名称的灵感来源。物质无法在一个地方解体而在另一个地方再生,但信息可以。

爱因斯坦的狭义相对论认为,信息的传播速度不如光速快。远距传动实际上并没有违反这一理论,它只是看起来违反罢了。为了纠缠,光子对必须在同一个地方开始,然后远离彼此。这意味着“潜伏”信息的传播速度比光速慢,因此仍然遵循爱因斯坦的理论。这有点像信鸽之间的通信,虽然鸽子可以比骑马的人更快地运送便条,但是马必须先将鸽子运送到目的地,这样鸽子才能带着便条飞回家。为了传送有用的信息(而不仅仅是概率测量的结果),远距传动协议还需要经典的通信手段——也就是说,除了一匹马先把信鸽送到目的地,还需要第二匹马跟着信鸽回去,这匹马带有如何阅读信鸽腿上便条的指示。这意味着量子远距传动不太可能在不久的将来用于高频交易。然而,它仍然是在不失稳的情况下传输完整量子态最有效的方式。

量子系统的模拟

量子系统(如量子计算机)可用于模拟另一个量子系统,这并不令人感到惊讶。令人感到惊讶的是,经典计算机在模拟量子系统方面表现得非常糟糕。模拟小型量子系统倒还好,但要模拟大型量子系统实际上是不可能的。量子态信息的丰富性意味着,随着元素数量的增长,模拟所需要做出的工作量呈指数级增长。Richard Feynman 是第一个注意到量子系统具有高度计算复杂性的人,这为量子信息理论的后期发展奠定了基础。

因子分解

一旦人们注意到量子系统的计算复杂性实际上是计算能力,量子信息理论才真正起飞。我们可以将其应用于其他问题上。因子分解是指找出乘积等于一个给定数字的两个数。因子分解有时候会很有用,但最有趣的是,它太难了,而且是非常之难。因子分解是单向函数的一个例子,如果两个除数都是已知的,那么找到它们的乘积就很容易,但从乘积中找到除数可能需要很长的时间。最大的一个已被分解的数字是一个 2​​32 位的数字,但实际上它并不算很大(作为对比,pi 已被计算到了至少五万亿个数字)。但分解一个 232 位的数字已经算得上是一个重大项目了,它使用了数百台机器,研究人员花了两年时间才找到除数。

这种不对称的难度使得因子分解被用在了公钥加密(例如 RSA)中。两个素数的乘积用于生成公钥,发送者使用该公钥来加密消息。然后,接收方基于其中一个原始因数使用私钥来解密消息。如果一个人知道原始的除数,那么解谜就很容易,否则的话,那将会是一个很棘手的问题。

虽然它没有经过数学证明,但人们普遍认为,一般性因子分解的难度规模比多项式大,但比指数小。这被称为亚指数,用 2 的 O(n) 次方表示。实际上,如果数字足够大,基本上是无法通过经典方法来分解的。

1994 年,数学家 Peter Shor 证明可以使用量子计算机在多项式时间内解决因子分解问题。他听过关于量子计算理论前景的讨论,但当时没有人发现任何有用的算法。他开始考虑如何使用量子计算机解决一般的计算问题,但没有告诉任何人他在做什么。他花了一年的时间(兼职)提出了用于寻找对数的量子算法。四天后,他将对数算法用在了因子分解上。

因为因子分解是大多数公钥加密的核心部分,所以Shor 的研究成果引起了人们的注意。不过,Shor 的算法并没有破坏密码学,“量子安全”加密协议已经在开发当中。此外,我们将在本系列文章的第3 部分中看到,我们需要一台具有数千个量子位的量子计算机才能成功运行Shor 算法。

Shor 的算法通过使用量子叠加来尝试各种可能性。

然而,Shor 算法的细节比仅仅“尝试所有可能的因素并找出正确的那个”更加复杂。虽然这可以在量子计算机上完成,但任何测量都会产生随机——并且很可能是不正确的——因素。

Shor 算法的聪明之处在于,在尝试了很多可能性之后,它会将所有答案干扰在一起,因此测量更有可能产生正确的答案而不是错误的答案。对于经典计算机来说,“干扰答案”并不合理,但量子计算机利用量子态的波动特性却可以做到这一点。干扰获得正确结果的可能性是许多量子算法的共同特征。

Shor 解决方案的第一部分是进行经典计算,将因子分解问题变成查找函数周期(即它的频率)的问题。一旦完成了这一步,问题就与波和频率有关,那么就有可能使用量子波和干扰的解决方案。

在经典数学中,傅里叶变换用于将函数(如波信号)转换为组成频率。为了找到未知函数的傅立叶变换,有必要在许多点上进行测量,以便计算出它重复的频率。例如,标准正弦波的傅里叶变换是一对尖峰(只有一个频率,围绕 y 轴镜像)。框函数的傅里叶变换是逐渐下降的凹凸。

量子傅立叶变换也具有选择构成时间序列的频率的目标,但它能够使用叠加在多个点上及时有效地测量函数,然后对波进行干扰,这样正确的答案就会放大,错误的答案就会消退。完成这一步后,任何测量都很有可能让系统收敛到正确的答案。

将波混合在一起,以便让错误的答案自行消退,这与经典计算机的工作方式非常不同,但这也是我们大多数人在宏观世界中曾经经历过的事情。例如,降噪耳机通过向现有噪声添加额外噪声达到降噪的效果。它们发出额外的声波,试图再现外部噪声,只不过使用了相移。只要新的声波与原先的噪声波相差 180 度,并且是完美的副本,它们将整齐地相互抵消,从而为耳机佩戴者带来安静的世界。

搜索

Shor 的算法是第一个量子“杀手级应用”。两年后,出现了第二个,也就是 Grover 的搜索算法。Grover 算法可以在 O(根号 n) 的时间复杂度搜索未排序的数据库。例如,如果只知道一个人的电话号码,可用它在电话簿中查找姓名。Grover 算法没有像 Shor 的因子分解算法那样提供同样惊人的速度,它是二次加速,而不是指数级加速(也就是说,它按照元素数量的平方根进行缩放)。Grover 算法的速度虽然比较保守,但其适用性却十分广泛。

尽管 Grover 只针对数据库搜索来描述他的算法,但事实上它应该更加通用。被搜索的东西是能够满足某些功能的东西——也就是问题的答案(从技术上讲,目标是“函数的逆”)。例如,问题可能是“我应该用什么密钥来解密这个消息?”换句话说,Grover 的搜索算法可以用来加速密码的暴力破解,即使不是基于因子分解加密的。它还可用于估计一组数字的平均值(平均值或中值)。

像其他很多量子算法一样,Grover 算法是带有概率性的。每次执行都有可能给出正确的答案,并且也有少许的可能性获得错误的答案。这看起来似乎不太令人满意,但实际上它比表面上看起来的更有用处。因为答案是函数的解决方案,所以如果算法给出错误的答案就会非常明显。对于一个包含 n 个元素的系统,使用 O(根号 n) 的时间复杂度寻找解决方案,如果得到错误的答案,将是非常令人沮丧的。不过,即使重复这种长时间的慢速计算多次,总的时间复杂度不变,仍然比使用确定性经典算法快得多(计算错误的概率不随 n 增加,这就是为什么可以容忍误差)。

碰撞

我们可以对 Grover 算法进行一般化,用它来解决“碰撞问题”。也就是说,我们不找可以满足函数的东西,而是尝试找出产生相同答案的多个元素。这对于理解空间中的物理碰撞以及更常见的问题(例如找到两个生日是同一天的人)非常有帮助。与 Grover 的原始算法一样,它可以通过查找具有相同散列值的两个数字来进行加密攻击(它的经典版被称为“生日攻击”)。

旅行推销员问题

量子算法通常会尝试所有可能的解决方案,然后通过幅度放大选择其中正确的一个,因此,量子计算机似乎应该在解决优化问题方面表现出色。到目前为止,还没有通用的量子优化算法,但是对于某些优化问题的子类别,确实存在有吸引力的量子解决方案。最著名的优化问题之一被称为旅行推销员问题,即为在多个地点之间旅行的推销员找到最短路线。随着位置数量的增加,寻找最佳路线的难度也随之增加。旅行推销员问题是 NP-hard 问题,并且其难度随着位置数量的增加呈指数级增长。这个问题的精确解决方案可能需要用很多年(甚至数百万年)才能计算出来,即使只有几十个城市。

旅行推销员问题是一个持续研究的领域。直到最近,最著名的量子算法时间复杂度是 O(根号 n 的阶乘)(二次加速),而最著名的经典算法时间复杂度是 O(2 的 n 次方)。2017 年 3 月,发布了一个最新量子算法,该算法在大多数情况下接近二次加速,并且仍有改进的空间。

机器学习

在过去几年中,随着量子计算和机器学习逐渐升温,人们很自然会想是否可以把它们结合起来。到目前为止,答案似乎是肯定的。在数学层面,量子态计算和机器学习模型都严重依赖矩阵。从概念上讲,机器学习是关于在数据中寻找模式,量子计算的干扰和放大波模型非常适合用于寻找模式。

量子计算机可以使用对数资源进行某种类型的矩阵求逆(矩阵求逆等效于求解线性方程组)。矩阵求逆有助于解决一些机器学习问题。更一般地说,Grover 算法可用于搜索“正确”的答案(即满足给定函数的答案)。其他机器学习问题,例如聚类,可以使用其他独特的量子算法。

理论上已经证明,量子计算机能更好地解决所谓的“黑盒问题”(通过探测发现未知的随机比特序列),研究人员已经演示了如何解决5 个比特的黑盒问题。除了能够(原则上,用足够强大的计算机)能够发现如此长的序列(使用经典计算机可能永远也算不出来),量子计算机对读数中的噪音也更加宽容。

没有通用的量子加速

所有这些算法都是针对特定的问题,其中一些(例如搜索或旅行推销员问题)存在很多潜在的应用场景,但算法本身非常具体。现在还不存在一种已知的“通用量子加速”。换句话说,就复杂性类别而言,已知BQP 与NP 重叠,但目前还不知道重叠的程度。有可能是NP 包含了BQP,但尚未得到证实。 Peter Shor 指出,要让量子算法提供有趣的加速,需要对正确答案的计算路径进行建设性的干涉,并对错误答案的路径进行相互抵消,现在还没有一个通用的过程。考虑到问题的难度如此之大,可能永远不会有。

不过,缺乏通用量子算法不应该对已知算法的有趣程度或适用性产生影响。本系列文章的下一篇将讨论这些问题,并探究量子计算的未来。

关于作者

Holly Cummins 是一位全栈开发人员和云计算技术主管。她经常发表演讲,是一位 Java Champion,以及 Enterprise OSGi in Action 一书的作者。Holly 拥有牛津大学量子计算博士学位(PhD)。

查看英文原文 Cats, Qubits, and Teleportation: The Spooky World of Quantum Computation (Part 2)

2018 年 7 月 17 日 10:201116
用户头像

发布了 731 篇内容, 共 383.7 次阅读, 收获喜欢 1903 次。

关注

评论

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

SCA Sentinel 分布式系统的流量防卫兵,春招我借这份PDF的复习思路

Java 程序员 后端

Spring JdbcTemplate简介,java高级开发面试总结

Java 程序员 后端

SpringBoot 实现大文件视频转码(转码基于FFMPEG实现)

Java 程序员 后端

Redis:看完就比常人多会三种类型实战,可以拿去炫耀了

Java 程序员 后端

Spring--声明式事务控制,mysql索引教程

Java 程序员 后端

Spring+SpringMVC+MyBatis整合,想拿高工资

Java 程序员 后端

set集合,挑战华为社招

Java 程序员 后端

SonarQube,SonarLint检测代码修复问题汇总归纳,2021京东最新Java面试真题解析

Java 程序员 后端

Spring Boot 项目如何做性能监控?,javase教程书

Java 程序员 后端

Spring Boot 谷粒学院、谷粒商城项目问题汇总,springboot源码视频

Java 程序员 后端

Spring Security账号密码认证源码解析,java项目开发全程实录第四版视频

Java 程序员 后端

Servlet的Cookie和Session机制,面试谈谈对springboot的理解

Java 程序员 后端

Set集合无法去重相同内容的父类对象和子类对象的问题解决

Java 程序员 后端

Socket和ServerSocket的简单介绍及例子,mongodb教程导入外部数据

Java 程序员 后端

SpringBoot 实现大文件视频转码(转码基于FFMPEG实现)(1)

Java 程序员 后端

RestFul API 统一格式返回 + 全局异常处理,linux系统编程视频教程

Java 程序员 后端

seata-golang 一周年回顾,java面试准备内容

Java 程序员 后端

Spring 基于 xml 配置的快速入门(超详细),数据库事务深入分析

Java 程序员 后端

Spring Boot核心技术之Restful映射以及源码的分析,springboot启动原理通俗

Java 程序员 后端

Spring Boot面试题(2020最新版),2021我的Java大厂面试之旅

Java 程序员 后端

Spring Cloud Gateway实战之二:更多路由配置方式,阿里面试java准备

Java 程序员 后端

spring-boot-route 使用aop记录操作日志,springboot入门项目实战

Java 程序员 后端

Redis该怎么学?其实很简单,这份学习路线,mybatis架构梳理

Java 程序员 后端

RocketMQ 5,学习linux系统管理

Java 程序员 后端

Serverless Devs 的官网是如何通过 Serverless Devs 部署的

Java 程序员 后端

Redis精通系列——LRU算法详述(Least Recently Used - 最近最少使用)

Java 程序员 后端

Redis面试题汇总,mysql调优面试题

Java 程序员 后端

Redis高可用篇:Cluster集群能支持的数据量有多大?,再不了解你就out啦

Java 程序员 后端

Sleuth服务跟踪大厂高频面试题:整合-Zipkin,java面向对象程序开发及实战答案

Java 程序员 后端

SonarQube检测出的bug、漏洞以及异味的修复整理,mysql基础知识

Java 程序员 后端

Spring+MySQL+数据结构,mybatis懒加载的原理及实现

Java 程序员 后端

数据cool谈(第2期)寻找下一代企业级数据库

数据cool谈(第2期)寻找下一代企业级数据库

猫、量子位和远距传动:令人匪夷所思的量子计算世界(第二部分)-InfoQ