关键要点
- 远距传动是最先被描述的量子信息处理过程之一。它使用纠缠在瞬间远距离传输信息,但它不能用于传送大型物体,如人或猫。
- 一旦人们意识到量子系统的计算复杂性实际上是一种计算能力,那么量子信息理论就真正起飞了。它可以被应用于其他问题上,例如在公钥密码学中用到的因子分解。
- 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 是第一个注意到量子系统具有高度计算复杂性的人,这为量子信息理论的后期发展奠定了基础。
因子分解
一旦人们注意到量子系统的计算复杂性实际上是计算能力,量子信息理论才真正起飞。我们可以将其应用于其他问题上。因子分解是指找出乘积等于一个给定数字的两个数。因子分解有时候会很有用,但最有趣的是,它太难了,而且是非常之难。因子分解是单向函数的一个例子,如果两个除数都是已知的,那么找到它们的乘积就很容易,但从乘积中找到除数可能需要很长的时间。最大的一个已被分解的数字是一个 232 位的数字,但实际上它并不算很大(作为对比,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)
评论