研究人员已经证明，在一个没有难解问题的世界里，安全量子加密是可能实现的。

让我们假设你想发送一条私密信息、进行秘密投票或是安全地签署文件。如果你在电脑上执行这些任务，就需要依靠加密来保证数据的安全。这种加密需要能够抵御密码破译者用他们自己的计算机进行的攻击，因此现代加密方法依赖于这样一种假设：哪些数学问题对计算机而言是难以解决的？

但在20世纪80年代，当密码学家为这种信息安全方法奠定数学基础时，一些研究人员发现，计算难度并不是守护秘密的唯一方法。量子理论起初是为了理解原子物理学而开发、构建，可事实证明，它竟然与信息和密码学有着深刻的联系。研究人员找到了一些方法，可以直接基于物理定律确保某些特定加密任务的安全性。但这些任务都属于少见的特例——对于其他所有任务而言，除了经典计算方法之外，似乎别无他法。

到了20世纪末，量子密码学研究人员认为这就是最后的答案了。但就在过去的几年里，这个领域又发生了翻天覆地的变化。

“我们对量子密码学可能实现的内容有了重新的认识。”美国哥伦比亚大学的量子信息理论家亨利 · 袁（Henry Yuen）说。

在最近的一系列论文中，研究人员表明，即使在几乎所有计算都变得很容易的假想世界中，大多数加密任务仍然可以安全地完成。真正关键的是一个有关量子理论本身的特殊计算问题的难度。

“你所需要的假设可以非常、非常、非常弱，”位于美国加利福尼亚州伯克利的西蒙斯计算理论研究所的量子密码学家费米 · 马（Fermi Ma）表示，“这让我们对计算难度本身有了新的认识。”

此信息将自动销毁

故事开始于20世纪60年代末，当时一位名叫史蒂芬 · 威斯纳（Stephen Wiesner）的物理学研究生开始思考量子理论中测量的破坏性。对任何受量子物理规则支配的系统进行测量，都会改变从数学层面描述其构形的量子状态。对于大多数物理学家来说，这种量子测量干扰都是一种障碍。但威斯纳持有以信息为中心的非正统观点，他开始思考能否让这种干扰变得有用。或许它可以成为敏感数据的一种内置防篡改保护。

但威斯纳的想法过于超前，在研究生毕业后，他就离开了学术界。幸运的是，他曾与他的朋友、物理学家查尔斯 · 贝内特（Charles Bennett）讨论过这些想法，后者在长达十年的时间里尝试引起他人对此话题的兴趣，始终未果。最后，1979年，贝内特在波多黎各的一次会议期间，于海边游泳时遇到了计算机科学家吉尔斯 · 布拉萨德（Gilles Brassard）。他们合作撰写了一篇开创性的论文，描述了一种解决重要加密任务的新方法。他们的协议基于量子测量干扰，无需任何关于计算问题难度的假设。

“量子信息在本质上似乎就是加密的。”费米 · 马说。

20世纪80年代，查尔斯·贝内特（左）和吉尔斯·布拉萨德开创了一种基于量子物理的新加密方法

贝内特和布拉萨德的突破让研究人员变得乐观起来，他们相信，其他加密任务也可以通过类似的量子技术达到完美的安全性。研究人员主要关注一种名为比特承诺的任务，它不仅本身非常有用，还是大多数高级加密协议的关键组成部分。

要理解比特承诺背后的基本概念，可以想象一场双人游戏。在这场游戏中，你必须做出一个秘密决定，这个决定需要在稍后揭示。一种方法是把决定写在纸条上，并放入密封的信封。这样，你之后就无法更改决定，你的对手也无法偷看结果。

现在想象一下，你们在网上玩同样的游戏。为了让作弊成为不可能，你需要把决定封在一个数字信封里，让双方都无法单独打开。这就是密码学的用武之地。1981 年，计算机科学家先驱曼纽尔 · 布卢姆（Manuel Blum）构建了第一个比特承诺协议——一种利用难解的计算问题构造不可破解信封的方法。

但“难解”具体有多难？计算复杂性理论领域的研究人员研究了许多不同类型的难题，并非所有难题都对密码学家有用。比特承诺和其他所有的加密协议都依赖于一类被复杂性理论学家称为“NP”类的问题，这类问题的定义特征是很容易检查候选解是否正确。

遗憾的是，研究人员尚未证明任何NP类问题都很难解。即使是看似最难的问题，也可能存在某种尚未发现的巧妙程序或算法能够将其一举解决。如果当真存在这样的程序，那么整个经典密码学都会崩溃。

这些考虑推动着人们探索基于量子的安全保证。但在1997年，两篇论文证明，完全基于量子物理定律的比特承诺方案永远不可能彻底安全。这两篇论文暗示，几乎所有加密任务都需要某种计算难度。

在接下来的近25年里，这成为量子比特承诺理论基础的定论。然后，在2021年，一位名叫威廉 · 克雷其默（William Kretschmer）的研究生发表了一篇论文，促使研究人员面对一个从未有人想过的问题。对于比特承诺和大多数其他形式的密码学来说，计算难度显然是必要的，但究竟是哪一种难度呢？

威廉·克雷其默在区分某些量子态方面的研究成果促使研究人员重新思考量子密码学的基础

答案比任何人预想的都要奇怪。

咨询谕示

2021年的论文源于克雷其默想要努力理解一个概念上看似简单的问题的特定版本：区分或判别两种表面上相似的量子态到底有多难？克雷其默眼下是西蒙斯研究所的博士后研究员，而他最初对这个问题产生兴趣的原因与比特承诺无关。

“密码学根本不在我的考虑范围内。”他说。

判别问题之所以有趣，部分原因在于，人们甚至不清楚如何用熟悉的数学语言来描述它。传统上，复杂性理论学家研究的问题都有不同的可能输入，这些输入由位串（即0和1）表示。例如，对于将大数分解为质因数的任务，输入的位串就代表要分解的数。

即使在研究人员开始研究如何利用量子物理进行计算之后，他们仍然把重点放在这种“经典输入”问题上。典型的量子算法以普通的经典位串为起始，然后使用量子技巧对其进行处理。但在克雷其默研究的这类“量子输入”问题中，输入并非位串，而是容易被计算干扰的量子态（就和测量的干扰一样）。

“我们无法使用传统复杂性理论中用来描述量子计算的语言直接谈论这些问题。”亨利 · 袁说。

起初，克雷其默认为他只需要把问题翻译成更标准的语言，但他想不出该怎么做。于是，他做了复杂性理论学家在走投无路时经常做的事：求助于谕示。

在复杂性理论中，“谕示”（oracle）指的是一种可以即时解决特定问题的假想设备。能够访问谕示的计算机可能会通过咨询谕示，将其作为算法的中间步骤，从而更轻松地解决其他问题。当然，谕示在现实世界中并不存在，但研究它们有助于复杂性理论学家理解不同问题的难度级别之间的关系。

克雷其默想知道，什么样的谕示可以轻松区分两种量子态，即所谓的态判别问题。他决定从一种特殊的谕示入手，这种谕示可以增强普通量子算法的能力，也就是那些利用量子技巧解决经典位串输入问题的算法。这类算法可以解决某些对经典算法来说太难的问题，比如大数分解，但它们并非万能的，还有许多问题超出了它们的能力范围。

访问克雷其默的谕示可以让这些算法解决现实中的量子计算机难以解决的某些经典输入问题。克雷其默本以为这些算法用来解决他的问题已经绰绰有余，但令他惊讶的是，他证明了这些加强版量子算法仍然被态判别问题难倒了。

“我完全被威廉的论文吸引了，”波士顿大学的密码学研究生钱洛文（音译）说，“我当时真的觉得它肯定错了，因为它太反直觉了。”

钱洛文、亨利 · 袁等人很快证明，如果克雷其默的态判别问题真的很难解决，那么安全的量子比特承诺方案就可能实现。这反过来又意味着许多更高级的加密协议也拥有了安全性。量子加密的范围远比20世纪90年代的研究人员所意识到的要广泛，而这一切都归结于一个问题的难解程度。

钱洛文（左）、阿维谢·塔尔（中）和马克兰德·辛哈与克雷其默合作，证明了即使在经典加密完全失效的情况下，许多量子加密技术仍然是安全的

能有多难？

克雷其默的结果有一个重大的前提——为了使证明成立，他不得不依赖一个只有量子算法才能咨询的不寻常谕示。或许，一个更为熟悉的谕示会让他的态判别问题变得更容易，从而使安全的量子比特承诺失效？2022年，克雷其默和钱洛文开始合作，研究他们能用一个人人都能理解的谕示证明出什么结论：一个可以瞬间解决任何NP问题的谕示。在拥有这种谕示的世界里，所有的经典加密都将失效。

克雷其默很快意识到，态判别问题在数学上与量子复杂性理论中一个看似不同的问题有着关联，于是他请来了该领域的两位专家——复杂性理论学家阿维谢 · 塔尔（Avishay Tal）和马克兰德 · 辛哈（Makrand Sinha）。“威廉就像个经理，而我们则是承包商。”塔尔说。

四位研究人员通力合作，很快就证明，即使是对于能够调用这个NP谕示的计算机，克雷其默的态判别问题可能仍然是不可解的。这意味着，即使支撑起经典加密的每一个问题都变得容易，几乎所有量子加密依然可以保持安全。经典密码学和量子密码学越来越像两个完全独立于彼此的世界。

这个结果引起了费米 · 马的注意，他开始琢磨，自己能把克雷其默开创的研究方向推到多远。即使引入更离奇的谕示——那些可以瞬间解决远比NP难得多的计算问题的谕示——量子加密是否仍能保持安全呢？“NP类问题并不是经典问题中最难的，”美国伊利诺伊大学厄巴纳-香槟分校的密码学家达克希塔 · 库拉纳（Dakshita Khurana）表示，“还有比它们更难的。”

费米 · 马与普林斯顿大学的密码学家亚历克斯 · 隆巴迪（Alex Lombardi）以及加州大学伯克利分校的量子计算研究员约翰 · 赖特（John Wright）集思广益，思索如何以最佳方式解决这个问题。“这个问题真是太迷人、太令人费解了，”赖特说，“我立刻就被吸引住了。”

费米·马（左）、约翰·赖特（中）和亚历克斯·隆巴迪证明，即使有一个可以瞬间解决任何经典输入计算问题的谕示，量子密码学仍然可以保持安全

在思考了一段时间却毫无进展后，费米 · 马提出，他们应当考虑最极端的情况：一个可以瞬间解决任何经典输入计算问题的谕示。这将囊括复杂性理论学家传统上研究的一切问题，甚至包括那些在现实世界中被认为不可解的问题。

“我觉得这听起来有点疯。”隆巴迪说。

但是，这个问题却取得了惊人的成果。经过近一年的努力，他们终于发表了一项惊人的结果。在能且只能咨询一次全能谕示的情况下，没有任何一个算法可以区分两种量子态，做不到这点，就无法破坏量子比特承诺方案。

只允许算法单次查询的限制并不像听起来那么大，因为量子算法可以利用一种叫作叠加的现象，在实际上要求谕示同时解决多个问题。能够连续进行多次查询的算法可能会更强大，因为它们可以利用前次查询的答案来决定下一次的查询内容。这些算法是否也会受到类似的限制，仍然是一个悬而未决的问题。

费米 · 马、隆巴迪和赖特的论文之所以意义重大，还有另一个原因。在这三位研究人员研究他们的问题时，他们意识到它与复杂性理论学家斯科特 · 阿伦森（Scott Aaronson）和数学家格雷格 · 库珀伯格（Greg Kuperberg）在16年前提出的一个重大未解问题密切相关，该问题涉及将一种量子态转化为另一种量子态的难度。这篇新论文是解决该问题的第一个重大进展。

“这是一个非常强有力的结果，也是一个非常令人惊讶的结果。”京都汤川理论物理研究所的量子密码学研究员森前智行表示。

一系列的最新成果表明，区分两种量子态这个看似无害的问题不仅很难，而且几乎是难以想象的难——远远超出了普通甚至更离奇的量子算法的能力范围。这对密码学来说是好消息，但对以量子态为输入的计算问题也有更广泛的影响。传统的复杂性理论似乎无法解决这些问题。要真正理解这些问题，可能需要一个全新的理论框架。

“感觉量子信息的行为方式有一些根本性的不同，”美国华盛顿大学的量子密码学家安德烈亚 · 克拉丹杰洛（Andrea Coladangelo）说，“它一定还与密码学之外的领域存在联系。”

资料来源 Quanta Magazine