人民邮电出版社—科普分社量子计算带来的密码学革命
文：戴维•多伊奇 转载自公众号：中科院物理所
对于通用量子计算机的全部本领中包含的某些环境，用传统的方法营造它们是难解的，这一事实说明一些纯数学计算类也必定变得易解了。因为如伽利略所说，物理定律是用数学语言表达的，营造一个环境相当于计算一定的数学函数。的确，现在已经发现许多数学任务可以用量子计算高效地完成，而用所有已知的传统方法都是难解的。最引人注目的一个就是对大的自然数进行因数分解。该方法称为肖算法，由贝尔实验室的彼得·肖在1994年发现。
肖算法极其简单，对硬件的要求比通用量子计算机简单得多。因此，很可能量子因数分解引擎制造成功会远比量子计算技术全面可行化要早得多。这对于密码学（关于通信安全和信息认证的科学）具有重大意义。现实中的通信网络可以是全球化的，具有庞大的、持续变化的用户群，其通信模式不可预期。要求每一对用户事先物理地交换机密的密钥以备后来彼此通信而无需害怕窃听者，这是不切实际的。公钥密码学是一种在收发双方还没有约定任何机密信息时发送机密信息的方法。已知的最安全的公钥密码手段依赖于大数分解问题的难解性。该方法称为RSA密码体制，以纪念罗纳德·李维斯特、阿迪·沙米尔和伦纳德·阿德尔曼，他们丁1978年首次提出这一方法。它依赖于一个数学过程，用一个大数（比如250位）作为密钥给消息编码。接收方可以随意把该密钥公开，因为任何用它编码的消息只能在知道了那个数的因子以后才可以解码。于是，我（原作者）可以选择两个125位的素数并使它们保密，但是把它们乘起来，让250位的乘积公开。任何人可以用这个数作为密钥给我发消息，但是只有我能够读消息，因为只有我知道秘密因子。
我讲过，用传统方法分解250位数是不实际的，但是运行肖算法的量子因数分解引擎可以在仅仅几千步算术运算内完成，这只需要几分钟。所以，任何能使用这种机器的人都能够轻易地阅读任何窃听到的用RSA体制加密的消息。
密码员选择再大的数字作为密钥也没有用，因为肖算法需要的资源只随着待分解数字的长度缓慢地增长。在量子计算理论中，因数分解是非常易解的。有人认为，由于存在一定程度的脱散，可以分解的数字的长度会有一个实际的限制，但是还不知道在技术上可达到的脱散率有没有下限。所以，我们只能认为未来的某一天，在现在还不能预测的某个时候，任何给定密钥长度的RSA密码体制都会变得不安全。在一定意义上，甚至现在也不安全了。因为任何人或任何组织现在可以记录下用RSA加密的消息，一直等到他们购买了脱散率足够低的量子因数分解引擎，就可以对消息解码了。这种事情可能几百年都不会发生，或者可能在仅仅几十年甚至更短时间内就发生了，谁知道呢。但是对于原先RSA体制完美的安全性，现在只能指望这种事情在相当长时期内不会发生了。
当量子因数分解引擎分解250位数字的时候，相干宇宙的数目会达到10500量级，即10的500次方。这一令人惊愕的巨大数目是肖算法把因数分解变得易解的原因。我讲过，该算法只需要几千步算术运算，我当然指的是对答案有贡献的每一个宇宙中有几千步运算。所有计算是在不同的宇宙中并行完成的，并通过相干分享结果。
你可能感到奇怪，我们怎么能说服我们在10500多个宁宙中的副本和我们一起开始干分解因数的工作呢？他们对自己的计算机没有别的使用安排吗？不，无需说服。初始时肖算法仅仅在一组彼此相同的宇宙中操作，仅仅在分解因数引擎范围内使它们分化。所以，在我们指定了待分解的数字、等待答案算出来的时候，在所有相干宁宙中是一样的。毫无疑问，存在许多其他宁宙，其中的我们编制了不同的数字，或者根本没有造出分解因数引擎，但是那些宇宙与我们的宇宙在太多的变量上不同，或更准确地说，在那些肖算法程序没有使它们以正确方式相互作用的变量上不同，所以不与我们的宇宙发生干涉。
从逻辑上讲，复杂量子计算的可能性无助于解决不可回答的问题，但是它的确产生了心理影响。对于肖算法，论述已经写得很长。对那些仍然坚持单一宇宙世界观的人，我提出这一挑战：请解释肖算法的工作原理。我要求的不仅仅是预言它能够有效工作，这不过是求解几个没有争议的方程而已，我要求的是给出解释。当肖算法已经分解了一个数，使用的计算资源大约是可见存在的计算资源的10500倍的时候，这个数是在哪里被分解出来的？在整个可见的宇宙中只有大约1080个原子，与10500相比只是个零头。所以，如果可见的宇宙是物理实在的全部，那么物理实在所包含的资源将远远不足以分解这么大一个数。那么是谁分解了它？计算是如何以及在哪里完成的？
我一直在讨论的是量子计算机能够比现有的机器更快地求解传统类型的数学问题。但是存在另一类计算任务，传统计算机根本不能完成它，而量子计算机则是有希望的。由于不可思议的巧合，首批发现的这类问题之一也与公钥密码学有关。这一次不是破译现存的密码体制，而是实现一个新的、绝对安全的量子密码系统。1989年，在纽约约克镇高地IBM研究所，在理论家查尔斯·班尼特的办公室里，建成了第一台能够运转的量子计算机。这是一台专用量子计算机，由一对量子密码设备组成，由班尼特和蒙特利尔大学的吉勒斯·布拉萨德设计。它是第一台曾经完成过图灵机所不能完成的非平凡计算的机器。
在班尼特和布拉萨德的量子密码系统中，消息被编码在激光器发出的一个个光子的状态中。虽然传送一条消息需要许多光子（每比特一个光子，外加浪费在各种无效工作中的许多光子），但是可以用现有的技术造出这台机器，因为它一次只需在一个光子上执行量子计算。系统的安全性不是基于难解性（不论是传统的还是量子的难解性），而是直接基于量子干涉的性质：正是这才使它具有传统方法所不能获得的绝对安全性。无论是哪种计算机，无论做多少计算，无论算几百万年还是几万亿年，都无助于窃听者偷听到量子加密的消息，因为如果人们通过有干涉效应的媒介通信，那么他们就能够发觉窃听者。根据经典物理，没有办法能够防止已经接触到通信媒介（如电话线）的窃听者安装被动侦听装置。但是，我解释过，如果有人测量了一个量子系统，那么他就改变了以后的干涉性质。通信协议就依靠这一效应。通信双方有效地建立起反复的干涉实验，协调他们在公共信道上的行为。只有当干涉通过了检查，证明没有窃听者，他们才继续下一阶段的协议，这时才用一些传送的信息作为密钥。在最坏情况下，坚持不懈的窃听者可能会完全阻断通信（当然，切断电话线更容易达到目的）。但是对于阅读消息来说，只有指定的接收方才能读到，而且这是由物理定律保证的。
因为量子密码术依赖于操纵单个光子，所以它受到很大的局限。成功接收到的每一个光子负载1比特消息，必须设法完整地从发送方传送到接收方。但是所有传送方法都有损耗，如果损耗太大，消息就传达不到接受方了。建立中继站（在现有的通信系统中用来弥补损耗）会危及安全性，因为窃听者可以监听进入中继站的信息而不会被发觉。现有的最好的量子密码系统采用光纤，能传达大约10千米的范围。这足以给诸如城市的金融区这样的地方提供绝对安全的内部通信网。市场化的系统可能为期不远了，但是为了一般地解决公钥密码问题（如全球通信），还需要进一步发展量子密码学。
量子计算领域的实验和理论研究正在世界范围内加速进行，甚至更有希望的实现量子计算机的新技术已经提出，具有超过传统计算的各种优点的新型量子计算正在持续不断地被发现、被分析。我感到所有这些发展都很振奋人心，我相信它们中的某些发展会产生技术硕果。但就本书而言，那些是枝节问题了。从基础科学角度看，量子计算多么有用无关紧要，我们的第一台通用量子计算机是下星期建成还是几百年后建成，还是永远也建不成，这都无关紧要。无论怎样，对于那些寻求对真实世界的基本理解的人们来说，量子计算理论必定成为他们的世界观的不可或缺的组成部分。通过量子计算机的理论研究，我们可以发现而且正在发现关于物理定律、通用性以及真实世界结构的几个表面无关的解释之间的内在联系。
术 语
量子计算：需要量子力学过程，尤其是干涉效应的计算。换句话说，是通过平行宇宙间的协作来完成的计算。
指数计算：输入每增加一位数字，所需资源（如时间）增加大约常数倍的计算。
易解/难解：（粗略但管用的规则）：如果完成计算需要的资源不随着输入数的位数指数地增加，那么该计算任务被认为是易解的。
混沌：大多数经典系统运动的不稳定性。系统的两个初始状态的微小差异结果导致两条运动轨迹的差异呈指数增长。但是真实世界遵循量子物理，而不是经典物理。混沌造成的不可预期性一般都被相同宇宙变为不同宇宙的过程中所造成的量子不确定性所淹没。
通用量子计算机：能够完成任何其他量子计算机所能完成的计算，营造任何有限的、物理上可能的虚拟现实环境的计算机。
量子密码术：能够被量子计算机执行，而不能被传统计算机执行的任何形式的密码术。
专用量子计算机：非通用的量子计算机，如量子密码设备和量子因数分解引擎。
脱散：如果量子计算在不同宇宙中的不同分支对环境的影响不同，那么干涉作用会被削弱，计算可能失败。脱散是实际实现更强大量子计算机的主要障碍。
本文出自《真实世界的脉络：平行宇宙及其寓意（第2版）》第九章
较原文略有删减，如需白名单请在后台留言
作者：戴维·多伊奇
译者：梁焰 黄雄
隆普兰克科学图书奖入围作品，英国物理学会保罗·狄拉克奖、第四届国际量子通信奖获得者戴维·多伊奇经典著作。
原文链接
对于通用量子计算机的全部本领中包含的某些环境，用传统的方法营造它们是难解的，这一事实说明一些纯数学计算类也必定变得易解了。因为如伽利略所说，物理定律是用数学语言表达的，营造一个环境相当于计算一定的数学函数。的确，现在已经发现许多数学任务可以用量子计算高效地完成，而用所有已知的传统方法都是难解的。最引人注目的一个就是对大的自然数进行因数分解。该方法称为肖算法，由贝尔实验室的彼得·肖在1994年发现。
肖算法极其简单，对硬件的要求比通用量子计算机简单得多。因此，很可能量子因数分解引擎制造成功会远比量子计算技术全面可行化要早得多。这对于密码学（关于通信安全和信息认证的科学）具有重大意义。现实中的通信网络可以是全球化的，具有庞大的、持续变化的用户群，其通信模式不可预期。要求每一对用户事先物理地交换机密的密钥以备后来彼此通信而无需害怕窃听者，这是不切实际的。公钥密码学是一种在收发双方还没有约定任何机密信息时发送机密信息的方法。已知的最安全的公钥密码手段依赖于大数分解问题的难解性。该方法称为RSA密码体制，以纪念罗纳德·李维斯特、阿迪·沙米尔和伦纳德·阿德尔曼，他们丁1978年首次提出这一方法。它依赖于一个数学过程，用一个大数（比如250位）作为密钥给消息编码。接收方可以随意把该密钥公开，因为任何用它编码的消息只能在知道了那个数的因子以后才可以解码。于是，我（原作者）可以选择两个125位的素数并使它们保密，但是把它们乘起来，让250位的乘积公开。任何人可以用这个数作为密钥给我发消息，但是只有我能够读消息，因为只有我知道秘密因子。
我讲过，用传统方法分解250位数是不实际的，但是运行肖算法的量子因数分解引擎可以在仅仅几千步算术运算内完成，这只需要几分钟。所以，任何能使用这种机器的人都能够轻易地阅读任何窃听到的用RSA体制加密的消息。
密码员选择再大的数字作为密钥也没有用，因为肖算法需要的资源只随着待分解数字的长度缓慢地增长。在量子计算理论中，因数分解是非常易解的。有人认为，由于存在一定程度的脱散，可以分解的数字的长度会有一个实际的限制，但是还不知道在技术上可达到的脱散率有没有下限。所以，我们只能认为未来的某一天，在现在还不能预测的某个时候，任何给定密钥长度的RSA密码体制都会变得不安全。在一定意义上，甚至现在也不安全了。因为任何人或任何组织现在可以记录下用RSA加密的消息，一直等到他们购买了脱散率足够低的量子因数分解引擎，就可以对消息解码了。这种事情可能几百年都不会发生，或者可能在仅仅几十年甚至更短时间内就发生了，谁知道呢。但是对于原先RSA体制完美的安全性，现在只能指望这种事情在相当长时期内不会发生了。
当量子因数分解引擎分解250位数字的时候，相干宇宙的数目会达到10500量级，即10的500次方。这一令人惊愕的巨大数目是肖算法把因数分解变得易解的原因。我讲过，该算法只需要几千步算术运算，我当然指的是对答案有贡献的每一个宇宙中有几千步运算。所有计算是在不同的宇宙中并行完成的，并通过相干分享结果。
 |
（图片来自网络） |
你可能感到奇怪，我们怎么能说服我们在10500多个宁宙中的副本和我们一起开始干分解因数的工作呢？他们对自己的计算机没有别的使用安排吗？不，无需说服。初始时肖算法仅仅在一组彼此相同的宇宙中操作，仅仅在分解因数引擎范围内使它们分化。所以，在我们指定了待分解的数字、等待答案算出来的时候，在所有相干宁宙中是一样的。毫无疑问，存在许多其他宁宙，其中的我们编制了不同的数字，或者根本没有造出分解因数引擎，但是那些宇宙与我们的宇宙在太多的变量上不同，或更准确地说，在那些肖算法程序没有使它们以正确方式相互作用的变量上不同，所以不与我们的宇宙发生干涉。
从逻辑上讲，复杂量子计算的可能性无助于解决不可回答的问题，但是它的确产生了心理影响。对于肖算法，论述已经写得很长。对那些仍然坚持单一宇宙世界观的人，我提出这一挑战：请解释肖算法的工作原理。我要求的不仅仅是预言它能够有效工作，这不过是求解几个没有争议的方程而已，我要求的是给出解释。当肖算法已经分解了一个数，使用的计算资源大约是可见存在的计算资源的10500倍的时候，这个数是在哪里被分解出来的？在整个可见的宇宙中只有大约1080个原子，与10500相比只是个零头。所以，如果可见的宇宙是物理实在的全部，那么物理实在所包含的资源将远远不足以分解这么大一个数。那么是谁分解了它？计算是如何以及在哪里完成的？
我一直在讨论的是量子计算机能够比现有的机器更快地求解传统类型的数学问题。但是存在另一类计算任务，传统计算机根本不能完成它，而量子计算机则是有希望的。由于不可思议的巧合，首批发现的这类问题之一也与公钥密码学有关。这一次不是破译现存的密码体制，而是实现一个新的、绝对安全的量子密码系统。1989年，在纽约约克镇高地IBM研究所，在理论家查尔斯·班尼特的办公室里，建成了第一台能够运转的量子计算机。这是一台专用量子计算机，由一对量子密码设备组成，由班尼特和蒙特利尔大学的吉勒斯·布拉萨德设计。它是第一台曾经完成过图灵机所不能完成的非平凡计算的机器。
在班尼特和布拉萨德的量子密码系统中，消息被编码在激光器发出的一个个光子的状态中。虽然传送一条消息需要许多光子（每比特一个光子，外加浪费在各种无效工作中的许多光子），但是可以用现有的技术造出这台机器，因为它一次只需在一个光子上执行量子计算。系统的安全性不是基于难解性（不论是传统的还是量子的难解性），而是直接基于量子干涉的性质：正是这才使它具有传统方法所不能获得的绝对安全性。无论是哪种计算机，无论做多少计算，无论算几百万年还是几万亿年，都无助于窃听者偷听到量子加密的消息，因为如果人们通过有干涉效应的媒介通信，那么他们就能够发觉窃听者。根据经典物理，没有办法能够防止已经接触到通信媒介（如电话线）的窃听者安装被动侦听装置。但是，我解释过，如果有人测量了一个量子系统，那么他就改变了以后的干涉性质。通信协议就依靠这一效应。通信双方有效地建立起反复的干涉实验，协调他们在公共信道上的行为。只有当干涉通过了检查，证明没有窃听者，他们才继续下一阶段的协议，这时才用一些传送的信息作为密钥。在最坏情况下，坚持不懈的窃听者可能会完全阻断通信（当然，切断电话线更容易达到目的）。但是对于阅读消息来说，只有指定的接收方才能读到，而且这是由物理定律保证的。
 |
（图片来自网络） |
因为量子密码术依赖于操纵单个光子，所以它受到很大的局限。成功接收到的每一个光子负载1比特消息，必须设法完整地从发送方传送到接收方。但是所有传送方法都有损耗，如果损耗太大，消息就传达不到接受方了。建立中继站（在现有的通信系统中用来弥补损耗）会危及安全性，因为窃听者可以监听进入中继站的信息而不会被发觉。现有的最好的量子密码系统采用光纤，能传达大约10千米的范围。这足以给诸如城市的金融区这样的地方提供绝对安全的内部通信网。市场化的系统可能为期不远了，但是为了一般地解决公钥密码问题（如全球通信），还需要进一步发展量子密码学。
量子计算领域的实验和理论研究正在世界范围内加速进行，甚至更有希望的实现量子计算机的新技术已经提出，具有超过传统计算的各种优点的新型量子计算正在持续不断地被发现、被分析。我感到所有这些发展都很振奋人心，我相信它们中的某些发展会产生技术硕果。但就本书而言，那些是枝节问题了。从基础科学角度看，量子计算多么有用无关紧要，我们的第一台通用量子计算机是下星期建成还是几百年后建成，还是永远也建不成，这都无关紧要。无论怎样，对于那些寻求对真实世界的基本理解的人们来说，量子计算理论必定成为他们的世界观的不可或缺的组成部分。通过量子计算机的理论研究，我们可以发现而且正在发现关于物理定律、通用性以及真实世界结构的几个表面无关的解释之间的内在联系。
术 语
量子计算：需要量子力学过程，尤其是干涉效应的计算。换句话说，是通过平行宇宙间的协作来完成的计算。
指数计算：输入每增加一位数字，所需资源（如时间）增加大约常数倍的计算。
易解/难解：（粗略但管用的规则）：如果完成计算需要的资源不随着输入数的位数指数地增加，那么该计算任务被认为是易解的。
混沌：大多数经典系统运动的不稳定性。系统的两个初始状态的微小差异结果导致两条运动轨迹的差异呈指数增长。但是真实世界遵循量子物理，而不是经典物理。混沌造成的不可预期性一般都被相同宇宙变为不同宇宙的过程中所造成的量子不确定性所淹没。
通用量子计算机：能够完成任何其他量子计算机所能完成的计算，营造任何有限的、物理上可能的虚拟现实环境的计算机。
量子密码术：能够被量子计算机执行，而不能被传统计算机执行的任何形式的密码术。
专用量子计算机：非通用的量子计算机，如量子密码设备和量子因数分解引擎。
脱散：如果量子计算在不同宇宙中的不同分支对环境的影响不同，那么干涉作用会被削弱，计算可能失败。脱散是实际实现更强大量子计算机的主要障碍。
本文出自《真实世界的脉络：平行宇宙及其寓意（第2版）》第九章
较原文略有删减，如需白名单请在后台留言
 |
作者：戴维·多伊奇
译者：梁焰 黄雄
隆普兰克科学图书奖入围作品，英国物理学会保罗·狄拉克奖、第四届国际量子通信奖获得者戴维·多伊奇经典著作。
原文链接
> 我来回应