导语

随机数在计算机和密码学等领域有广泛的应用，目前已经有了许多生成随机数的方法。但事实上，任何基于经典力学的过程所产生的随机数，本质上都不是真随机的。而量子世界特有性质使得可以从中产生可以验证的纯随机 (pure random) 数。本文将介绍两个把量子计算机变成随机数制造工厂的技术。

 

编译：集智俱乐部翻译组

原题：How to Turn a Quantum Computer Into the Ultimate Randomness Generator

来源：Quantamagazine

 

如果你在一个计算机科学家的聚会上谈论“量子优势”（quantum supremacy），很可能会收到白眼。量子优势是指，一台量子计算机能够轻松地解决那些传统计算机无法解决的某些特定的难问题，从而超越传统计算机。然而遗憾的是，这些所谓量子计算机能轻松解决的难问题在现实中并没有太多用武之地，这也就不奇怪为何会遭到白眼了。

 

但是，现在有传言说，Google 的量子处理器将能够实现这一目标。量子优势终于能够在一个方面得以应用——纯随机数生成。

 

在我们所使用的计算与通信基础设施中随机数的生成是极为重要的环节。特别是当涉及到数据加密问题时，随机数生成就尤为重要。因为，从日常通信到金融交易乃至国家机密一切都被随机数保护。

 

想象一个数列具备这样的特征：真正可以验证的随机性——永远无法预测下一时刻这个数列会出现哪个数字。但这样的数列极其难以获得。

 

量子计算机能可能攻破这一难题。研究者最初做这样任务可能只是为了展示量子计算机的威力所在，但是也有可能生成真正可以验证的随机数。“我们非常激动，”加州大学圣巴巴拉分校的物理学家、谷歌量子计算项目负责人 John Martinis 说，“我们希望这是量子计算机首次得以应用。”

 

随机性与信息熵

 

随机性和量子理论就像打雷的下雨一样, 是相伴相生，量子理论必然会带来随机性。在量子世界中，系统常常处于组合状态中——也就是所谓的“叠加”态。但是，当你去测量一个系统时，该系统就会塌缩到其中的某一种状态。虽然量子理论允许我们去计算测量时出现不同状态的概率，但从本质上来说，出现什么结果是具有随机性的。

 

物理学家一直都在试图去利用这种关联去制造随机数生成器。这些都依赖于对某种量子叠加态的测量。尽管这样的系统已经能够满足绝大多数人对于随机性的需求，但却很难实现。而且，要证明这些生成的随机数的随机性并不容易。最后，很多有效的验证随机性的方法要求把多台设备安置在彼此相隔甚远的地方。

             

近期有学者提出了一个提议：如何从单个设备中获得随机性——仅靠一台量子计算机。这被称之为采样任务（sampling task）。这也是首批进行测试的量子优势。我们可以这样理解这项任务：

 

假设，有一个装满卡片的盒子。每一个棋子上都有一些诸如 000、010、101 的 01 序列。如果是三位数字，那么一共有 8 种可能，但是每一种卡片都不是唯一的，也许会有 50 张“010”，25张 “001”。这些卡片数量的分布情况决定了每次随机抽取出一张卡片上数值的可能性。在上面那个例子中，拿出一张“010”的可能性是拿出“001”的两倍。

 

对于一个采样任务来说，其中包含着一个算法：一个盒子中装有以一定概率分布的各种卡片，从这个盒子中拿随机抽出一张卡片。一种卡片的分布概率越大，那么它被算法抽出的可能性也越大。

 

当然，一个抽象的算法并不会真的把手伸到某个盒子里去摸卡片。实以输出一个50位长度的随机数为例，实际上，这个算法首先会给出一个指定了这50位数所有可能的输出组合的概率分布，然后随机输出一个二进制数。

 

我希望这是量子计算机上的第一个应用。——John Martinis，谷歌量子计算项目主管

 

对于一台传统计算机来说，随着输出位数的增加，计算复杂度会指数快的增加。但是对于一台量子计算机而言，无论是 5 位还是 50 位随机数的生成都一样直接。

 

量子计算机从所有的量子比特（qubits）的某个特定状态开始运算（比如，初始态为 0）。就像传统计算机使用逻辑电路操纵比特一样，量子计算机使用量子等价物（量子门）操纵量子比特。

 

但是有所区别的是，量子门可以把量子比特置于奇怪的状态。比如，有一种门可以把始态为 0 的量子比特置入 0、1 叠加的状态中。这时如果你去测量这个量子比特的状态，它就会以相等的概率随机的塌缩至 0 或 1 状态。

 

更令人惊奇的是，同时作用于两个或多个量子比特的量子门会导致这两个量子比特发生纠缠。在这种情形下，量子比特的状态的测量结果就会出现统计关联。这时候，量子比特的状态就只能用量子状态来描述了。

 

如果把众多量子门连接在一起，让它们以特定的顺序作用于一组量子比特，就创建了一组量子电路。以我们上面提过的例子来说，为了得到 50 位的随机字符串，我们可以构建一个量子电路，把 50 个量子比特放在一起，形成一个叠加态，这个叠加态就包含了你可以调整的数位分布。

 

当这些量子比特被测量时，它们整体的叠加态就会随机的塌缩成一个 50 位的字符串。其中，所生成字符串的概率分布由量子电路决定。测量这些量子比特就好像是蒙上眼睛，伸手从盒子中摸出一个遵循该分布的随机字符串。

 

   

 

我们是如何得到这些随机数的？其中至关重要的一点是，被量子计算机所采样的 50 位字符串的信息熵很高。熵被用来度量无序程度和不可预测性，因此也就可以用来度量随机性。德克萨斯大学奥斯汀分校的计算机科学家 Scott Aaronson 认为：“实际上，随机数生成非常重要。”他提出了一个新的方案。“并不是因为生成随机数是量子计算机上最重要应用，而是在于这可能是在实际技术条件限制下, 第一个量子计算机应用。”

 

Aaronson 的随机数生成协议看起来非常的简单。一台传统计算机从一个可信的信源接受几个比特的随机数，并把这个随机数作为“种子”来决定量子门的类型和作用的先后顺序，并由此生成量子电路“图纸”。而后，传统计算机把这个“图纸”发送给量子计算机，由量子计算机来运行量子电路。最后，测量量子比特，得到生成的 50 位字符串并发送回去。

 

一次又一次地重复上以过程，比如，一个量子电路重复采样 10 次。利用统计学原理，传统计算机能保证得到的字符串的信息熵很高。Aaronson 和陈立杰合作的工作（部分尚未发表）表明：在特定可信的假设下，这些问题在计算上是困难的，没有一台传统计算机能够在做到量子计算机所做的类似工作并得到同样的信息熵。在经过检查后，传统计算机把所有得到的 50 位的字符串拼接在一起，并输入给了一个经典算法。“它得到了一个几乎完全随机的长字符串。”Aaronson 说。

 

参考论文：

Complexity-Theoretic Foundations of Quantum Supremacy Experiments

论文预印本：

https://arxiv.org/abs/1612.05903

 

量子陷门 (Trapdoor)

 

不过，Aaronson 的协议适合具备大约 50-100 个量子比特的量子计算机。当量子计算机中的量子比特超过这个阈值时，传统的超级计算机也难以应用这项协议。还有另外一项使用量子计算机生成可验证的随机数的方案。该方案运用了一项现有的数学技术，这项技术有着一个吓人的名字——无爪陷门函数（trapdoor claw-free function）。“这玩意听起来挺唬人的。”加州大学伯克利分校的计算机科学家 Umesh Vazirani 这样评价道。他和 Zvika Brakerski、Paul Christiano、Urmila Mahadev 以及 Thomas Vidick 一同设计了这个方案。

 

参考论文：

A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device

预印本网址：

https://arxiv.org/abs/1804.00640

               

还用我们之前提过的盒子来打比方，这一次我们不再是伸手去抽取字符串，而是放入一个 n 位字符串 x；盒子输出另一个 n 位字符串。这个盒子可以以某个方式把输入字符串映射到输出字符串。但是这样的盒子有一个特性， 对于每一个字符串 x，都存在另一个字符串，使得这两个字符串能得到同样的输出。

 

换句话说，存在两个唯一的字符串 x、y，他们能得到同样的输出字符串 z。于是这三个字符串 x、y、z 就被称之为爪（claw）。用计算机科学的话来说，这个盒子就是一个函数。给定 x 或 y，计算出 z 非常的容易。但是，已知 x、z 求出 y ——找出爪——就不容易了。即便是对于量子计算机而言也并非易事。

 

如果你想得到爪的唯一办法就是知道一些内部信息，也就是所谓的陷门（trapdoor）。

 

Vazirani 和他的同事们不仅想通过这些函数让量子计算机生成随机数，而且也希望验证量子计算机的行为遵循量子力学原理——这一点对于随机数的可信性尤为重要。

 

在该协议中，量子计算机把输入的 n 位量子比特置于所有 n 位字符串的叠加态中。而后，由传统计算机发送一个关于量子电路的描述，该描述刻画了要作用于叠加态的函数——无爪陷门函数。量子计算机实现这个量子电路，但是并不具备陷门的信息。

 

在这一阶段，量子计算机所处在的状态是：其中一组 n 位的量子比特处于叠加态（x 或 y），另一组则保存了把前文提到的函数作用于该叠加态的结果（未塌缩的 z）。这两组量子比特纠缠在一起。

 

然后，量子计算机去测量第二组量子比特，该组量子比特则随机的塌缩成输出结果 z。而第一组量子比特则是 x 和 y 叠加态塌缩的结果。因为，输入 x 或 y 都能得到输入结果 z。

 

传统计算机把 z 作为输入，可以做两项工作。大多数时候，它可以要求量子计算机测量其余的量子比特。因为塌缩至 x 或 y 的概率是均等的，所以这也就相当于随机地得到 0 或 1。

 

有时，为了检测量子计算机的量子性，传统计算机会提出一个特别的测量。该测量方法及其结果被设计为，只有具备陷门信息的经典计算机才能保证应答设备确实是量子计算机。Vazirani 和他的同事们表明，如果做出正确应答的设备没有使用塌缩的量子比特，那就等于不使用陷门信息就计算出了爪。然而这是不可能的，所以，为了应答询问，该设备内部至少导致了一位量子比特的塌缩（给出 0 或 1 的随机数）。Vazirani 表示，该协议能在一台不受信任的量子计算机内部创造出防篡改的量子比特。

 

在每次询问时，这种防篡改的量子比特能提供真正的随机比特信息。由此，就能用一个询问序列创造出长的随机字符串。

 

这个方案可能比 Aaronson 的量子采样协议更快，但是它也有一个明显的缺陷。Aaronson 认为：“让该协议包含 50 或 70 个量子比特并不现实。”

 

现在，Aaronson 在等待谷歌的系统得以实现：“他们做出的东西是不是足够好，能得到实际应用。这是一个大问题。”

 

如果，结果确实如此的话。那就意味着，由单台量子设备生成的可验证随机数就要实现了。Martinis 说：“我们认为它能够实用并且有市场潜力。这就是我们想要提供给人们的东西。”

 

翻译：Leo

审校：刘金国

编辑：陈安林

原文链接：

https://www.quantamagazine.org/how-to-turn-a-quantum-computer-into-the-ultimate-randomness-generator-20190619/