科学无国界

我们是知识的搬运工

福利时间

今天我们将送出由清华大学出版社提供的优质科普书籍《时间之问》。

《时间之问》是一部少有的打通学科边界，融合科技与人文内涵的通识之作。作品以大学师生的问答对谈开始，选取“时间”作为跨学科讨论的媒介，联结起数学、天文、信息技术、音乐、生物、物理等不同学科，一来一往的对话中隐含了作者精心设置的问题，辅以精心制作的插图和经过严谨考证的学术资料。阅读这本书，你将亲密接触到祖冲之、朱载堉、庞加莱、普莱斯、庄子、惠更斯、博尔赫斯等古今中外的科学家和思想家，了解到重大的科学观念和发明是如何产生、流变并推动历史的。你一度无法理解的习俗和现象，如二十四节气是阴历还是阳历、闰月是怎么来的、冬至时刻的测量问题、神奇的连分数与黄金分割等，都将在这部作品中找到源头和答案。

输入文字

只要你认真阅读下面的这篇文章，思考文末提出的问题，严格按照 互动：你的答案 的格式在评论区留言，就有机会获得奖品！

作者：Marianne Freiberger

翻译：Nothing

审校：loulou

如果你在新闻中看到有人成功制造出了量子计算机的话，你最好立刻冻结自己的信用卡。因为，当你在网上购物时，目前所有保护你的信用卡信息的方法将会在几秒钟内被量子计算机攻破。不光是你在银行内的信息，所有的加密信息在量子计算机面前都将被轻松破解。

网络安全依赖于一些很难解决的数学问题

关于量子计算机有很多耸人听闻的说法，但是量子计算机破解加密信息的超强能力是真的。现有的加密方法是基于那些用普通计算机无法快速解决的数学问题设计的，但是量子计算机可以轻易攻破这种加密方法。那么量子计算机还有哪些明显强于普通计算机的技能？

破译密码

虽然为了回答这个问题我们进行了很多理论方面的准备，但是这个问题仍旧很棘手。RSA算法，一种广泛被用于保护信息安全的算法，它利用计算机都很难快速完成的因数分解来进行加密。如果给你一个数字10，你立刻就可以告诉我它可以被分解为2和5两个素数的乘积，但是如果我给你的数字是62615533，你应该无法通过心算告诉我它是哪些素数的乘积。

这不能怪罪于你的心算能力。一旦数字足够大，计算机也无能为力。“如果给出一个4000位的数字，即使是让现存的计算机运行和宇宙年龄一样长的时间也无法将它分解成一系列素数的乘积，”剑桥大学的量子计算先驱Richard Jozsa说。

其实还有其他很多问题和分解数字具有一样的特征：我们有很多可以解决它们的算法，但是随着要解决的问题的难度的增加，所需算法的步数也越多。另一个著名的问题是旅行商问题，这个问题是说如何让旅行商访问每个城市时所走的路程最短：要访问的城市越多，问题越复杂。

复杂性理论按照解决问题的步数的增长速度来对各种问题进行分类。如果步数的增长是指数型的，比如旅行商问题，问题会变得非常棘手，因为指数型增长的增长速度会越来越快。当算法步数的增长随着输入数字的增加表现成多项式形式时，我们才认为这样的问题是可解决的：如果输入的大小是n，解题所需的步数正比于n2,n3或者nk。虽然解题步数增长在我们看来还是很快（假设k=10），但是复杂理论专家认为这种增长还算缓慢。“步数增长表现为多项式的数学模型是可计算的，”Jozsa解释道，“如果步数增长不表现为多项式的形式，我们认为这类问题在实际操作中是无法解决的。”

因数分解被认为是不可解决的问题：没有人写出可以由我们现在的计算机运行的多项式时间（步数呈多项式型增长）算法。这正是量子计算可以大展神威之处。1994年数学家Peter Shor提出一种解决数字分解问题的量子算法，它不光是多项式时间算法，并且k不大于3。这个算法利用数论的知识，将因数分解问题转化成一种在特定的数学函数中识别周期模式的问题——模式识别正是量子计算机所擅长的。

如今使用的其他加密算法也存在类似的问题，例如椭圆曲线加密算法（elliptic curve cryptography）：量子计算机可以轻易破解它们。

这看起来量子计算机有很大优势，但在这个领域内任何事情都是不确定的。“在复杂性理论中，要证明给定的任务不能在多项式时间内解决是出了名的难题，”Jozsa说，“这是一个尴尬的事实。”因为没人知道因数分解的多项式时间算法，并不意味着这样一个等待我们发现的算法不存在。“也许，下周可能就有一个聪明的数论专家把这样的算法找出来，” Jozsa说，“对量子计算来说，这有点扫兴。”

复杂性问题

复杂性的等级

对于其他问题情况怎么样？在其他的比因数分解更难的问题中，量子计算的威力会超过经典计算吗？在回答这个问题之前我们要明确“更难”的含义，这把我们引导到了复杂性类（complexity classes）的分级这里。首先介绍“简单的”问题，这类问题拥有可在经典计算机上运行的多项式时间算法，这类问题组成了一个被称为P的类。接下来是我们没有找到多项式时间算法的问题，但我们可以在多项式时间内来检验解的正确性。这类问题被称为NP问题。因数分解正是属于这类问题。

在NP类问题中，有一些问题特别难解——这些问题被称为NP完全问题（NP-complete），旅行商问题属于这类问题。比NP完全问题更加复杂的问题这里将不再介绍。

因数分解被归纳于NP类问题但不属于NP完全问题。由于量子计算可以在因数分解问题中击败经典计算，接下来的问题是，当涉及NP完全问题时，量子计算机表现如何？有一种说法认为，量子计算机可以在眨眼之间解决NP完全问题。但这种说法过于乐观了。“我们不知道我们是否可以用量子计算机解决NP完全问题，事实上，我们认为量子计算机做不到这一点，”Jozsa解释道。

P和NP问题是同样复杂的问题吗？

在这里，我们应该认识到复杂性理论的核心问题：所有我们提到的东西都不能被证明。我们不仅不知道量子计算机能否有效地解决NP完全问题，甚至不知道普通计算机能否有效地解决这些问题。正如可能存在一个可以解决因数分解问题但尚未被发现的多项式时间算法一样，也可能存在解决其他NP问题或NP完全问题的多项式时间算法。如果我们找到了这些算法，那么我们的复杂性类层次的结构将会崩溃：P类、NP类和NP完全类将会属于同一类。如果你能证明或否定P类问题等价于NP类问题，那就厉害了，克莱数学研究所都会奖励你一百万美元：它被认为是数学中最有趣的七个开放问题之一。

量子计算机会做什么?

如果理论不是建立在坚实的基础上,那么我们怎样保证量子计算可以有实际用处呢？P问题在理论上是“容易”解决的，但是你仍然需要花费很多时间去解决它。这时量子计算机可以帮助我们吗？

答案是肯定的。一个例子是“大海捞针”问题，它指的是从庞大无规律的数据库中找到特定的信息。试想，从包含n个条目的电话号码簿中搜索一个特定的号码而不是一个特定的名字。这是一个需要消耗大量时间的任务，因为号码是无规则的，它不像名字一样是按规律排列的。经典计算机除了一个一个的检索号码之外没有其他办法，最坏的情况是，我们发现电话号码簿中根本不存在我们要找的号码，或者这个号码处于最后一个位置，这样就需要进行n次操作。而量子计算机只需要n0.5次操作。这看起来并没有提速多少，但是当n足够大时，提速是相当可观的：以n=1000000为例，经典计算机需要进行一百万次操作而量子计算机仅需要进行1000次操作。

分子由大量遵循量子规律的粒子组成

另一个量子计算机可以大展身手的领域是化学领域，生物和制药领域。如果你想理解一个分子系统，例如为了设计一种新药，一个明智的选择就是在计算机上模拟它的行为。困难在于分子是由很多粒子组成的，而这些粒子全部遵循量子力学的规律。我们知道，随着粒子数的增长，描述分子系统所需的信息量呈指数增长，这使得计算变得异常困难。“它具有指数级的复杂性，”Jozas说，“尽管是面对相对小的分子，最好的经典计算机在模拟分子的量子动力学性质时也显得无能为力，然而量子计算机可以胜任这项工作。”

密码学也会受益于量子计算机。例如，当量子态被观测时就会发生塌缩，利用这种性质可以监测信息是否被其他人窃取。利用这种方法，人们可以给每个人分发量子秘钥——一串可以用于对信息加密和解密的字符串。如果有人截获了秘钥我们马上就能知道。“这种器件之所以存在，是因为它们只需要几个量子比特，因此这属于量子技术的范畴。”Jozsa说。这种方法在2007年首次被用于公共实践，当时它被用来确保在瑞士日内瓦举行的选举中的选票安全转移。也许从理论的角度我们很难说量子计算机具有什么优势，但是至少我们知道破坏我们的加密方法是要付出一些代价的。

原文地址：

互动问题

【互动问题：你遇到的最复杂的事，有多复杂？】

请大家严格按照 互动：问题答案的格式在评论区留言参与互动，格式不符合要求者无效。

截止到本周四中午12点，点赞数前三名的朋友将获得我们送出的图书一本。

编辑：loulou

近期热门文章Top10

↓ 点击标题即可查看 ↓
1. 掉入地下一万米
2. 从前有个学生熬夜迟到了，错把困扰数学家的难题当作业做了出来
3. 原子弹制造指南
4. 吸猫一时爽，一直吸猫一直爽
5. 为什么长时间不洗头，洗的时候搓不出很多泡沫？| No.145
6. 一个大活人，还能让尿活活憋死？？？
7. 所以，WiFi 和 4G 到底哪个更耗电？
8. 传纸条被发现，一看竟写着...
9. 铅笔上面那块废柴橡皮为什么容易把纸擦破？
10. 一幅图读懂量子力学（薛定谔的猫）