论文部分内容阅读
量子计算机的进步意味着只需要再过几年时间它们就能够破解所有的公钥加密。每个秘密都将大白于天下的那一天已经离我们不远了。
十多年前，我正在进行关于量子加密的介绍性演讲，正如我之前多次做过的演讲一样。我介绍了量子物理学、量子计算机和量子密码学的基本概念。我当时以一个展望作为结语结束了那次演讲，那就是当量子计算成为主流时，我们当前依赖于难以求解的大质数方程加密的大部分秘密都将会立刻被破解。
自从Whitfield Diffie、Mark Hellman和Ralph Merkle于1976年在他们开创性的论文《密码学中的新方向》中披露这一概念以来，大多数秘密都受到了某种形式的非对称加密保护，比如RSA、SSL、TLS和HTTPS。然而，我们所谈论的大多数网站、数字签名下载、在线金融交易、VPN、智能卡和大多数无线网络，所有的这些都能够立即被量子计算机所破解。
当今的安全通信都基于一个事实，那就是传统数字计算机不容易分解涉及大质数的多因子方程。如果量子计算机具备了这种能力，那么对于采取上述方式加密的任何秘密而言，游戏都结束了。
从理论上讲，世界上大多数的强国都在记录和存储全球大部分加密的网络流量以便将来解密，等待即将到来的那一天。届时美国将能够阅读俄罗斯和中国的绝密通信，反之亦然。我差不多八年前在专栏中就曾经提到过这种威胁。
回到我多年前的那次演讲：在演讲结束时的提问环节，有人问我，量子计算机还有多长时间就能够破解所有秘密。我的回答是“10年。大多数量子物理专家都认为只有10年时间了。”当我走出讲台后，业界知名人士Bruce Schneier走了过来。正如他那貌似漫不经心的步伐一样，他随口问了我一句，“你口中的10年到底是多久？”
我给出的10年这个答案是说可能至少10年时间。Bruce让我意识到我们都不知道确切的答案。量子物理学界流传的一个笑话是量子计算机总是在10年后出現。
量子计算机的工作原理
现在来看，不再需要10年了。据剑桥量子计算（CQC）商业发展科学主管兼理论物理学家Mark Jackson博士称，我们现在可能只需要四到五年的时间就可迎来量子计算，在某些领域或有限的商业应用当中，例如量子化学，甚至可能在2021年中期就会出现。什么东西发生了变化？我们现在的许多量子计算机、设备和软件虽然设计的足够巧妙并且十分有用，但是却没有被称为“纠错”的东西。
量子计算机可以凭借其独特的工作原理“秒杀”传统的数字计算机。显然，量子计算机依赖于量子力学（这里涉及的主题太大并且十分复杂），但简而言之，这就是优势。数字计算机是二进制的，其中央处理单元（CPU）内的每个晶体管或逻辑门同一时刻只能保持一种“状态”，是“开”还是“关”，是否通电，是“1”还是“0”。这就是所谓的二进制。
量子计算机的基础是量子比特。每个量子比特可以同时处于两个状态。因此，一个量子比特相当于两个二进制逻辑门。当引入它们后，量子比特会呈指数级增长。两个量子比特可以同时保持四种状态，三个量子比特可以同时保持八种状态，依此类推。
一台普通的量子计算机就可能会破解我们之前所有采用公钥/私钥对加密的秘密，但是这个过程需要有效的纠错。
量子计算机将在何时1.2何种方式破解公钥加密
为了让量子计算成为现实，我们已经等待了很长时间。到底有多久呢？至少可以追溯到1959年Richard Feynman博士就此进行的演讲。不过许多量子计算专家将Peter Shor博士在1994年公布的算法视为量子计算的真正开端。
Shor的算法表明，基于量子的计算可快速破解大多数传统形式的非对称加密。二十多年后，量子计算的光明前景（和威胁）几乎近在眼前。不仅仅是理论模型，而是出现了一些能够工作的量子计算机、软件、网络和其他通信设备。
最大的挑战之一是让量子比特保持足够的稳定和足够长的时间，在严肃的计算中不会出错。我会在下面的介绍中使用非技术术语“完美”和“不完美”来描述量子比特的这一品质。美国德克萨斯大学奥斯汀分校量子信息中心主任兼计算机科学教授Scott Aarenson称：“要破解公钥加密，实际上需要成千上万的‘逻辑’或‘编码’量子比特。而在现实世界中，由于纠错以及现有容错方案的庞大需求，对高品质的物理量子比特的需求很容易就会上升至百万级。”
那么我们在量子计算生命周期中已经处于哪个阶段了？按照Jackson博士的说法，量子计算机仅需要49个完美的量子比特就可以胜过传统的二进制计算机。这就是被大家熟知的“量子优势”，这将是量子计算机最终超越二进制计算机的关键节点。这一时刻的意义与IBM深蓝超级计算机在1997年击败世界象棋冠军加里·卡斯帕罗夫时一样。
为了破解当前大多数公钥加密，量子计算机需要至少4000个完美的量子比特，如果量子比特不完美，那么所需的数量将会翻上许多倍。那么我们距离完美的4000个量子比特还有多远？这个问题的答案要取决于你问谁。Jackson博士认为，我们将在未来五年制造出拥有4000个完美量子比特的量子计算机。虽然他有一些证据支持他的这一说法，但是我们距离4000个完美的量子比特还非常遥远。
2018年3月，谷歌公布了一台拥有72个不完美量子比特的计算机。谷歌目前的量子计算机每执行200次计算就会出一次错误。当每秒进行数十亿次计算时，这么高的错误率将是一场灾难。在全世界范围内，在制造更稳定的量子计算机的投入上没有数千万亿美元也至少有数百万亿美元。部分人认为如今达到4000个完美量子比特所需付出的努力已经不再像以前那样令人望而生畏了。
直接从事量子计算机研发的Jackson博士称：“我们在短短一年内就已经从9个量子比特发展到了72个量子比特，所以我们在今后的五年内获得4000个量子比特并不是一个疯狂的想法。鉴于美国政府已经在几个月前最终决定参与进来，我认为这个时间只是一个保守的估计。” 更多知识渊博的人依然认为我们仍无法知道会在何时取得用于破解公钥加密的突破性成就。Schneier长期撰写关于量子密码学的文章。当得知这一时间是5年时，他说：“我不相信这一说法。没人知道前面还有什么不可预料的问题。”
Aaronson博士也对此持怀疑态度。他在文章中写道：“如果这种情况在五年内发生，我会感到十分惊讶。我不是说这不可能，但我认为它们需要更长的时间。如果谷歌、IBM或其他公司在三到五年内成功地制造出了拥有70个量子比特的量子计算机，或是它们能够在一些（主要是人工）任务中开始超越经典计算机，我会对此感到非常高兴。即便如此，由于纠错和现有容错方案的庞大需求，它们还远不能威胁到公钥密码技术，因为这很容易导致对高品质的物理量子比特的需求上升至数百万量级。”
显然，对于量子计算机何时能够破解公钥加密，大家各执一词，但是这已经不再是科幻小说中的虚构内容了。
虽然美国国家安全局（NSA）也尚未承认很快就会实现量子突破，不过他们已经认为现在是时候开始着手准备了。具体说来，在他们的一份常见问题解答中曾提到，“NSA认为现在时机已经成熟……量子计算正在不断取得进展……NSA正在寻求与所有的NSA供应商和运营商一起实施基于标准的抗量子破解的密码技术以保护他们的数据和通信。”
新兴的量子计算行业
越来越多的企业和组织，至少有44个已知实体正在尝试制造量子计算机。4家全球知名的美国企业谷歌、IBM、英特尔和微软均参与其中。与此同时，越来越多的初创公司似乎也在不断取得进展。Jackson博士的公司CQC作为其中的一员，目前正与谷歌和IBM等公司展开合作。
虽然许多企业正在使用相似的技术，但还是有少数企业正在使用他们自己的方法，也有一些公司在同时使用多种方法以期在竞争中成为赢家。在过去的几个月里，IBM和谷歌均已经成立了业务开发部门，这表明他们的重点已经从理论转向了商用。
另外，许多企业竞相投入数十亿美元的现象也非常重要。当许多企业和国家开始为此投入大量资金时，必然会出现杀手级应用。以云计算为例。多年来，云只是一个深受怀疑的流行词，如今情况已经完全发生了改变。量子计算机也是一样。
常用的量子计算方法包括超导、离子阱和马约拉纳费米子法。超导和离子阱是目前产生量子比特最多的方法。但超导需要非常低的温度，这个温度接近绝对零度（接近-460F或-273C），且产生的量子比特非常脆弱且不稳定。
微软使用不太成熟的马约拉纳费米子法。目前，这种方法产生的量子比特比其他方法要少，但似乎更不易碎。Jackson博士形容马约拉纳费米子法就像编辫子一样。它们可以被外部环境推挤，但它们的量子状态会保持不变。他说：“如果我们能够让它们大规模地工作，那么这种方法无疑将会胜出，但我们对它们知之甚少。”
这场竞赛是一场国际性的竞争。人们普遍认为，即使没有处于领先地位，中国也具有很强的竞争力。正如Jackson博士所说，“他们非常重视这方面的研究，并且几乎没有任何预算限制。”中国在前段时间已经宣称使用卫星完成了量子通信实验。
剑桥量子计算（CQC）
CQC成立于4年前，當时投资重点开始从大学实验室转移到了微软、谷歌和IBM等大企业。CQC积极参与设计了一系列提升量子计算机效率的工具。最近他们设计并测试了一种全新的加密设备，理论上可提供牢不可破的保护。
CQC拥有名为“t|ket！”的专利量子编程语言和编译器。Jackson博士称这种语言有点类似c语言。其编译器与平台无关，适用于所有基于众多不同平台的量子计算机。它们可以在传统的数字CPU和新的量子处理单元（QPU）之间分配计算工作。
Jackson博士称，与传统的图形处理单元（GPU）负责处理密集的图形负载一样，传统的数字处理器单元（NPU）负责处理常规数字计算机的繁重数学负载，QPU负责处理量子负载。
CQC的编译器会将传统数字计算机的工作负载交给普通的CPU，将量子计算需求交给QPU，然后再将各自的处理结果重新合成为通用输出流。Jackson博士称：“你不需要急于淘汰你的数字电脑，我们仍然需要它们。”这是一个好消息，因为我想知道我们将如何携带需要超低温环境的计算机。
可验证的随机数生成器
CQC还设计了一些硬件，其中包括“可验证的”量子随机数生成器。传统的数字计算机从未能够生成过真正的随机数，因为从机制上说就是不可能的。传统计算机由非常稳定且可自然预测的石英时钟驱动，这些时钟可确定CPU将在何时以及以何种速度将信息存入和取出CPU寄存器。每个时钟周期都是固定的。这意味着任何传统随机数生成器背后的最终“真实数据来源”是可预测的（即不是真正随机的）。
传统计算机中的随机性实际上是在某种程度上近似于随机性。缺乏真正的随机性将导致许多以随机生成数字为开始的加密解决方案被破解。因此我们不仅需要真正的随机数生成器，还需要验证它们是否真正随机才能完全信任它们。
美国国家标准与技术研究院（NIST）在2018年4月出版的《自然》杂志上讨论了对真正随机数生成器的需求。结果证明量子计算实际上非常擅长生成经过验证的随机数。最早的可验证的量子随机数生成器的体积非常庞大且速度相当慢。
随机数如何在后量子世界中保护密码
CQC已经研发了一款名为IronBridge的基于硬件的原型单元，大小与VCR相当，预计每秒可产生大约400万个随机比特。它们足以投入商业使用支持加密协议，提供量子安全。所有这些数字都被贝尔不等式验证为真正随机的。
谁最在意获取这类真正的随机数呢？任何希望在量子计算打破传统加密方法后保护数据和信息的人。这其中包括政府、科技企业以及需要保护其宝贵的知识产权、研究和信息的公司。
在差不多二十年前，我曾经说过量子“审判日”到来的那一天距我们还有10年时间，当时这种想法就如同飞行汽车和水下城市的想法一样看似遥不可及。我和其他人也并不真正相信它们会很快到来。
但是今天，它们比以往任何时候都更接近我们。我们已经有了可运行的量子计算机，量子比特的数量也正在快速增长。它们已不再是一个被炒作起来的自日梦。强国和大大小小的公司正在努力在剩余的少数问题上取得实质性进展。这些只是一个时间问题，而现在是时候开始评估量子计算的到来时间了，这一时间已经缩短到了几个月或几年而不再是几十年。
十多年前，我正在进行关于量子加密的介绍性演讲，正如我之前多次做过的演讲一样。我介绍了量子物理学、量子计算机和量子密码学的基本概念。我当时以一个展望作为结语结束了那次演讲，那就是当量子计算成为主流时，我们当前依赖于难以求解的大质数方程加密的大部分秘密都将会立刻被破解。
自从Whitfield Diffie、Mark Hellman和Ralph Merkle于1976年在他们开创性的论文《密码学中的新方向》中披露这一概念以来，大多数秘密都受到了某种形式的非对称加密保护，比如RSA、SSL、TLS和HTTPS。然而，我们所谈论的大多数网站、数字签名下载、在线金融交易、VPN、智能卡和大多数无线网络，所有的这些都能够立即被量子计算机所破解。
当今的安全通信都基于一个事实，那就是传统数字计算机不容易分解涉及大质数的多因子方程。如果量子计算机具备了这种能力，那么对于采取上述方式加密的任何秘密而言，游戏都结束了。
从理论上讲，世界上大多数的强国都在记录和存储全球大部分加密的网络流量以便将来解密，等待即将到来的那一天。届时美国将能够阅读俄罗斯和中国的绝密通信，反之亦然。我差不多八年前在专栏中就曾经提到过这种威胁。
回到我多年前的那次演讲：在演讲结束时的提问环节，有人问我，量子计算机还有多长时间就能够破解所有秘密。我的回答是“10年。大多数量子物理专家都认为只有10年时间了。”当我走出讲台后，业界知名人士Bruce Schneier走了过来。正如他那貌似漫不经心的步伐一样，他随口问了我一句，“你口中的10年到底是多久？”
我给出的10年这个答案是说可能至少10年时间。Bruce让我意识到我们都不知道确切的答案。量子物理学界流传的一个笑话是量子计算机总是在10年后出現。
量子计算机的工作原理
现在来看，不再需要10年了。据剑桥量子计算（CQC）商业发展科学主管兼理论物理学家Mark Jackson博士称，我们现在可能只需要四到五年的时间就可迎来量子计算，在某些领域或有限的商业应用当中，例如量子化学，甚至可能在2021年中期就会出现。什么东西发生了变化？我们现在的许多量子计算机、设备和软件虽然设计的足够巧妙并且十分有用，但是却没有被称为“纠错”的东西。
量子计算机可以凭借其独特的工作原理“秒杀”传统的数字计算机。显然，量子计算机依赖于量子力学（这里涉及的主题太大并且十分复杂），但简而言之，这就是优势。数字计算机是二进制的，其中央处理单元（CPU）内的每个晶体管或逻辑门同一时刻只能保持一种“状态”，是“开”还是“关”，是否通电，是“1”还是“0”。这就是所谓的二进制。
量子计算机的基础是量子比特。每个量子比特可以同时处于两个状态。因此，一个量子比特相当于两个二进制逻辑门。当引入它们后，量子比特会呈指数级增长。两个量子比特可以同时保持四种状态，三个量子比特可以同时保持八种状态，依此类推。
一台普通的量子计算机就可能会破解我们之前所有采用公钥/私钥对加密的秘密，但是这个过程需要有效的纠错。
量子计算机将在何时1.2何种方式破解公钥加密
为了让量子计算成为现实，我们已经等待了很长时间。到底有多久呢？至少可以追溯到1959年Richard Feynman博士就此进行的演讲。不过许多量子计算专家将Peter Shor博士在1994年公布的算法视为量子计算的真正开端。
Shor的算法表明，基于量子的计算可快速破解大多数传统形式的非对称加密。二十多年后，量子计算的光明前景（和威胁）几乎近在眼前。不仅仅是理论模型，而是出现了一些能够工作的量子计算机、软件、网络和其他通信设备。
最大的挑战之一是让量子比特保持足够的稳定和足够长的时间，在严肃的计算中不会出错。我会在下面的介绍中使用非技术术语“完美”和“不完美”来描述量子比特的这一品质。美国德克萨斯大学奥斯汀分校量子信息中心主任兼计算机科学教授Scott Aarenson称：“要破解公钥加密，实际上需要成千上万的‘逻辑’或‘编码’量子比特。而在现实世界中，由于纠错以及现有容错方案的庞大需求，对高品质的物理量子比特的需求很容易就会上升至百万级。”
那么我们在量子计算生命周期中已经处于哪个阶段了？按照Jackson博士的说法，量子计算机仅需要49个完美的量子比特就可以胜过传统的二进制计算机。这就是被大家熟知的“量子优势”，这将是量子计算机最终超越二进制计算机的关键节点。这一时刻的意义与IBM深蓝超级计算机在1997年击败世界象棋冠军加里·卡斯帕罗夫时一样。
为了破解当前大多数公钥加密，量子计算机需要至少4000个完美的量子比特，如果量子比特不完美，那么所需的数量将会翻上许多倍。那么我们距离完美的4000个量子比特还有多远？这个问题的答案要取决于你问谁。Jackson博士认为，我们将在未来五年制造出拥有4000个完美量子比特的量子计算机。虽然他有一些证据支持他的这一说法，但是我们距离4000个完美的量子比特还非常遥远。
2018年3月，谷歌公布了一台拥有72个不完美量子比特的计算机。谷歌目前的量子计算机每执行200次计算就会出一次错误。当每秒进行数十亿次计算时，这么高的错误率将是一场灾难。在全世界范围内，在制造更稳定的量子计算机的投入上没有数千万亿美元也至少有数百万亿美元。部分人认为如今达到4000个完美量子比特所需付出的努力已经不再像以前那样令人望而生畏了。
直接从事量子计算机研发的Jackson博士称：“我们在短短一年内就已经从9个量子比特发展到了72个量子比特，所以我们在今后的五年内获得4000个量子比特并不是一个疯狂的想法。鉴于美国政府已经在几个月前最终决定参与进来，我认为这个时间只是一个保守的估计。” 更多知识渊博的人依然认为我们仍无法知道会在何时取得用于破解公钥加密的突破性成就。Schneier长期撰写关于量子密码学的文章。当得知这一时间是5年时，他说：“我不相信这一说法。没人知道前面还有什么不可预料的问题。”
Aaronson博士也对此持怀疑态度。他在文章中写道：“如果这种情况在五年内发生，我会感到十分惊讶。我不是说这不可能，但我认为它们需要更长的时间。如果谷歌、IBM或其他公司在三到五年内成功地制造出了拥有70个量子比特的量子计算机，或是它们能够在一些（主要是人工）任务中开始超越经典计算机，我会对此感到非常高兴。即便如此，由于纠错和现有容错方案的庞大需求，它们还远不能威胁到公钥密码技术，因为这很容易导致对高品质的物理量子比特的需求上升至数百万量级。”
显然，对于量子计算机何时能够破解公钥加密，大家各执一词，但是这已经不再是科幻小说中的虚构内容了。
虽然美国国家安全局（NSA）也尚未承认很快就会实现量子突破，不过他们已经认为现在是时候开始着手准备了。具体说来，在他们的一份常见问题解答中曾提到，“NSA认为现在时机已经成熟……量子计算正在不断取得进展……NSA正在寻求与所有的NSA供应商和运营商一起实施基于标准的抗量子破解的密码技术以保护他们的数据和通信。”
新兴的量子计算行业
越来越多的企业和组织，至少有44个已知实体正在尝试制造量子计算机。4家全球知名的美国企业谷歌、IBM、英特尔和微软均参与其中。与此同时，越来越多的初创公司似乎也在不断取得进展。Jackson博士的公司CQC作为其中的一员，目前正与谷歌和IBM等公司展开合作。
虽然许多企业正在使用相似的技术，但还是有少数企业正在使用他们自己的方法，也有一些公司在同时使用多种方法以期在竞争中成为赢家。在过去的几个月里，IBM和谷歌均已经成立了业务开发部门，这表明他们的重点已经从理论转向了商用。
另外，许多企业竞相投入数十亿美元的现象也非常重要。当许多企业和国家开始为此投入大量资金时，必然会出现杀手级应用。以云计算为例。多年来，云只是一个深受怀疑的流行词，如今情况已经完全发生了改变。量子计算机也是一样。
常用的量子计算方法包括超导、离子阱和马约拉纳费米子法。超导和离子阱是目前产生量子比特最多的方法。但超导需要非常低的温度，这个温度接近绝对零度（接近-460F或-273C），且产生的量子比特非常脆弱且不稳定。
微软使用不太成熟的马约拉纳费米子法。目前，这种方法产生的量子比特比其他方法要少，但似乎更不易碎。Jackson博士形容马约拉纳费米子法就像编辫子一样。它们可以被外部环境推挤，但它们的量子状态会保持不变。他说：“如果我们能够让它们大规模地工作，那么这种方法无疑将会胜出，但我们对它们知之甚少。”
这场竞赛是一场国际性的竞争。人们普遍认为，即使没有处于领先地位，中国也具有很强的竞争力。正如Jackson博士所说，“他们非常重视这方面的研究，并且几乎没有任何预算限制。”中国在前段时间已经宣称使用卫星完成了量子通信实验。
剑桥量子计算（CQC）
CQC成立于4年前，當时投资重点开始从大学实验室转移到了微软、谷歌和IBM等大企业。CQC积极参与设计了一系列提升量子计算机效率的工具。最近他们设计并测试了一种全新的加密设备，理论上可提供牢不可破的保护。
CQC拥有名为“t|ket！”的专利量子编程语言和编译器。Jackson博士称这种语言有点类似c语言。其编译器与平台无关，适用于所有基于众多不同平台的量子计算机。它们可以在传统的数字CPU和新的量子处理单元（QPU）之间分配计算工作。
Jackson博士称，与传统的图形处理单元（GPU）负责处理密集的图形负载一样，传统的数字处理器单元（NPU）负责处理常规数字计算机的繁重数学负载，QPU负责处理量子负载。
CQC的编译器会将传统数字计算机的工作负载交给普通的CPU，将量子计算需求交给QPU，然后再将各自的处理结果重新合成为通用输出流。Jackson博士称：“你不需要急于淘汰你的数字电脑，我们仍然需要它们。”这是一个好消息，因为我想知道我们将如何携带需要超低温环境的计算机。
可验证的随机数生成器
CQC还设计了一些硬件，其中包括“可验证的”量子随机数生成器。传统的数字计算机从未能够生成过真正的随机数，因为从机制上说就是不可能的。传统计算机由非常稳定且可自然预测的石英时钟驱动，这些时钟可确定CPU将在何时以及以何种速度将信息存入和取出CPU寄存器。每个时钟周期都是固定的。这意味着任何传统随机数生成器背后的最终“真实数据来源”是可预测的（即不是真正随机的）。
传统计算机中的随机性实际上是在某种程度上近似于随机性。缺乏真正的随机性将导致许多以随机生成数字为开始的加密解决方案被破解。因此我们不仅需要真正的随机数生成器，还需要验证它们是否真正随机才能完全信任它们。
美国国家标准与技术研究院（NIST）在2018年4月出版的《自然》杂志上讨论了对真正随机数生成器的需求。结果证明量子计算实际上非常擅长生成经过验证的随机数。最早的可验证的量子随机数生成器的体积非常庞大且速度相当慢。
随机数如何在后量子世界中保护密码
CQC已经研发了一款名为IronBridge的基于硬件的原型单元，大小与VCR相当，预计每秒可产生大约400万个随机比特。它们足以投入商业使用支持加密协议，提供量子安全。所有这些数字都被贝尔不等式验证为真正随机的。
谁最在意获取这类真正的随机数呢？任何希望在量子计算打破传统加密方法后保护数据和信息的人。这其中包括政府、科技企业以及需要保护其宝贵的知识产权、研究和信息的公司。
在差不多二十年前，我曾经说过量子“审判日”到来的那一天距我们还有10年时间，当时这种想法就如同飞行汽车和水下城市的想法一样看似遥不可及。我和其他人也并不真正相信它们会很快到来。
但是今天，它们比以往任何时候都更接近我们。我们已经有了可运行的量子计算机，量子比特的数量也正在快速增长。它们已不再是一个被炒作起来的自日梦。强国和大大小小的公司正在努力在剩余的少数问题上取得实质性进展。这些只是一个时间问题，而现在是时候开始评估量子计算的到来时间了，这一时间已经缩短到了几个月或几年而不再是几十年。