人工智能时代：破解人机共存密码（套装共10册）

通过密码本把所有英文字母对应为0和1的组合，这样就可以通过电流的通断来传递信息了。

量子比特是量子信息的基本单元，是量子通信和量子计算中的主角。它的量子性质造就了量子通信和量子计算的神奇。有人甚至认为量子比特是组成世间万物的基本构件。可量子比特到底是个什么东西？它神奇在什么地方？

在经典物理中，最简单的系统就是一个比特。一个比特只有两个态：0或1。而量子叠加原理告诉我们：任何两个态的叠加也是一个可能的态。为了区分经典比特的态，我们用| 0〉和| 1〉来标记量子比特的状态。所以一个量子比特，不仅有| 0〉和| 1〉两个态，还有它们的任意叠加态：

$$
| \begin{array} { r c l l c r c l } { { } } & { { \Psi } } \end{array} \ = \ \begin{array} { l } { { \Psi } } & { { = } } & { { \Psi } } & { { | } } & { { 0 \ + } } & { { \Psi } } & { { | } } & { { 1 } } \end{array}
$$

这里ψ0和ψ1被称为叠加系数。我们发现一个量子比特可以有无穷多个不同的状态，这些状态由两个复数ψ0和ψ1来刻画。当然这无穷多个态大多都不是相互排斥的。常用的是两个相互排斥的态，如|0〉和| 1〉、| 0〉+ | 1〉和| 0〉– | 1〉，等等。两位量子比特可以存储（00，01，10，11）4个状态，而3位的量子比特可以同时存储（000，001，010，011，100，101，110，111）足足8个状态的信息。

只要是一个量子系统就可以当作量子比特的备选对象。困难在于如何有效地操控它们，同时避免环境的影响。一个电子的两个自旋态就可以实现一个量子比特：自旋向上对应于| 0〉态，自旋向下对应于| 1〉态。

我们知道光有偏振现象，光的偏振也可以有不同的方向，不同方向代表了光子自旋的不同状态。这无穷多个偏振方向，表示光子自旋可以有无穷多个不同的状态。像电子自旋一样，这无穷多个态大多都不是相互排斥的。我们一样有两个相互排斥的态，如竖偏振和横偏振。我们可以用竖偏振代表| 0〉，用横偏振代表| 1〉。这样一个光子的自旋（偏振态）就是一个量子比特。一个光子还可以有左斜偏振，其对应于一个又横又竖不横不竖的偏振态，记为| 0〉+ | 1〉。一个光子也可以有右斜偏振，其对应于另一个又横又竖不横不竖的偏振态，记为| 0〉– | 1〉。量子保密通信可以利用这4种状态的光子来实现的。

图9–2 光子偏振的几种方式，即几个不同的量子叠加态

量子随机数

对量子随机数最好的描绘，莫过于爱因斯坦所说的话：“上帝不可能掷骰子”。但玻尔回敬了一句，“别去指挥上帝该怎么做”。

在爱因斯坦的世界观里，基于牛顿力学所构建的局域实在，是不允许某一个事情的发生是没有原因的。这与经典逻辑所要求的第四条公设充分理由定律，即事情的发生必然有原因的要求一致。一个骰子落在了哪个面，不由任何外在的、内在的原因来决定？完全不可预测？这跟经典的经验并不吻合。当我们知道所有初始状态的信息并且有足够强大的计算能力，为什么我们不能够构建一个完美的方程来描述骰子的所有运动，从而对它的未来结果进行预测呢？这就引出了拉普拉斯（Pierre-Simon Laplace）悖论：当我们知道了宇宙所有粒子的运动状态，和它们的相互作用性质，我们总能够写出来足够多的方程，这些方程就成了描绘这些粒子运动的原因，而它们所描述的对象的演化，就是自然的结果。

如果拉普拉斯悖论为真，我们一样可以写出关于我们自己的计算程序，这样我们的历史和未来都是已经设计好的脚本。只要有这个脚本，或者将来有一台足够容量的计算机，就能计算整个人类的历史和未来。它已经知道了一切，而我们，自以为有自由意识的人，就像安排好的演员，有固定的脚本，时间到了就上去演戏。该做什么，有什么样的结果，都是预先已经设定好的。历史上有这样的辩论，因为所有事情都是预先设计好的，所以杀人犯也不用判刑，因为这不是他决定的，而是在很久很久以前，甚至是在他出生之前，这一切都被决定好了，他只是执行者或者也是这个决定的受害者。而法官可以回应说，我判处他这样受罚也是预先被决定好了的。

近代的物理学发展对拉普拉斯悖论做出了这样的回答。混沌力学发现即使动力学方程本身是确定的，但它的演化结果也有可能完全不确定。任何微小的差别，都可以演化出完全不同的结果。而这些初始的微小的不同，可以来源于量子力学的随机。我们完全没有办法预测量子的随机什么时候发生，发生在什么地方，怎样发生，不仅是我们无法预测，上帝都不能。

量子长程关联

量子长程关联揭示了一个完全不同于局域关联所限制的世界。当然从实现的技术和方案上我们还没有足够的进展来造出一台实用的量子计算机，但我们可以想象利用量子的长程关联，已经有一些与经典计算截然不同的效果。

经典计算单元需要局域的相互作用作为基础。对于一个经典计算机，它的每一个计算单元都要靠跟相邻的计算单元通过相互作用来实现计算。在物理器件中实现需要，比如说具体到导线的连接，这些物理连接制约了算法。当第一个计算单元完成计算的时候，它有N个有限的连接，接下去每一个连接也还有n个，这样继续下去，有N×N×N个连接，事实上，由于局域相互作要求的物理接触，使得由于物理空间的限制，N通常只能做到几个。但对非局域关联来说，所有的计算单元同时参与计算，这样的网络可以迅速遍历所有的计算通道，使某一类型的算法执行起来非常快。我们要谈到的量子随机行走，它可以在一个网络中迅速找到答案所需的节点，因为它几乎是同时遍历所有的节点，而不是一步一步依靠经典的物理联结（局域关联）扩散而找到答案。当我们讨论人脑细胞的相互作用，如果说人脑有130亿个脑细胞，假设每个细胞会跟6个细胞发生相互作用。它们是通过物理连接而局域关联的话，相互作用关联数量就是N×130亿，N是个不太大的数。而当它们是非局域关联的话，其关联数量就达到惊人的130亿的6次方，这远远超过了地球上所有计算单元的总和。

量子的随机行走

经典随机行走是一种随机过程算法，它描述了算法的演化过程有随机的机制，实践中它已经被证明是随机算法发展的一种非常有用的技术。除了在算法中发挥的关键作用之外，经典随机行走在物理学、生物学、金融理论、计算机视觉和地震建模等许多科学领域中也发挥了重要作用。

量子行走是经典随机行走的量子力学的对应，是构建量子算法的一种工具。量子行走被证明可以构成一类通用的量子算法。由于经典随机游走已被成功地用于开发经典算法，量子计算的主要议题之一是量子算法的创建比其经典算法更快，因此人们对理解量子行走的性质有着极大的兴趣。尽管一些作者选择了“量子随机行走”这个名称来指代量子现象，事实上，在费曼关于量子力学计算机的开创性工作中，我们发现它可以被解释为连续的量子行走。但更多人认为，第一篇以量子行走为主题的论文是由亚尔基·阿哈罗诺夫（YakirAharonov）等人于1993年发表的。自此，经典随机行走和量子行走之间的联系以及量子行走在计算机科学中的应用成为新的研究领域。目前我们常讨论的模型是离散量子行走模型，它由两个量子力学系统组成，一个负责走路，另一个负责丢硬币。离散量子随机行走的操作很简单，一个硬币，扔起来，如果是正面，朝左走，如果是背面，朝右走。当这个过程量子化的时候，我们会发现它的行走速度要比经典随机行走的速度快很多。尤其是对一个网络而言，用量子随机行走来搜索这个网络的节点时，其速度会远远快于经典随机行走的速度。基于连续量子行走的算法，给定一个图，由两个高度为n的二叉树组成，左侧树的2n个叶子用根据图9–3所示的方式，右树的2n个叶子，并且有两个标记的节点入口和出口，找到一个从入口到出口的算法。从中可以看出，有可能构建一个量子行走，它从入口到出口，比其相应的经典随机游动指数快得多。换句话说，这个模型提出的连续量子行走找到目标的时间是多项式的（与N的几次方成正比），而相应的经典随机行走找到目标的时间是指数级增长的（与2^N成正比）。

量子算法

1985年，戴维·多伊奇迈出了关于量子计算重要的一步，他设计了量子计算的第一个例子。多伊奇定义量子算法是一类可以在量子计算机上执行的算法，并证实了量子算法有可能比传统的算法更有效。多伊奇算法利用了量子叠加和量子纠缠原理，被广泛认为是量子计算的第一个蓝图。因为它具有足够的特性和简单性，可以考虑用真正的物理装置实现。多伊奇算法作用于一个二值状态系统。多伊奇证明，如果可以通过一组特定的简单操作这个二值态系统，就可以具有普适性，进而可以模拟任何物理系统的演化。他还讨论了如何使用相同的思路产生类似图灵机的计算装置，从而成为一个实际意义上的通用量子模拟器，尽管这点需要未来更多的发展来验证。

多伊奇的简单操作现在被称为量子门，因为它们在经典计算机中起着类似于二进制逻辑门的作用。多伊奇提出了量子图灵机的概念，成为所有今天所谈及的量子计算的原型。对应于经典计算机的比特电子操作，量子算法也有针对量子比特的量子门操作。设计一个对二值操作的量子门，Hadamard门。我读书的时候戏称哈德门，它可以将量子比特映射到完美的叠加态，如下：

$$
H = \frac { 1 } { \sqrt { 2 } } { \binom { 1 } { 1 } } - 1 \AA \AA \big )
$$

在多伊奇的设计中，他给出了一个输出值为0，1的函数 $f \ ( \mathrm { \ v { x } } _ { 1 }$ $\operatorname { x } _ { 2 } . . . . . \operatorname { x } _ { \mathrm { { n } } } )$ 的黑盒子。黑盒取 $n / { \vec { \mu } } , ~ \mathrm { x } _ { 1 } , ~ \mathrm { x } _ { 2 } . . . . . . . \mathrm { x } _ { \mathrm { { n } } } , ~ \mathrm { x } _ { \mathrm { { i } } }$ 取值为0或1，并输出值 $f \ ( \mathrm { x } _ { 1 } , \ \mathrm { x } _ { 2 } { \cdots } { } ^ { \mathrm { x } _ { \mathrm { n } } ) }$ ，黑盒子中的函数要么给出常数（所有输入都为0，所有输入都是1）或均衡（对于一半输入值返回1，对于另一半返回0），任务是确定f是常数还是均衡。对于经典的确定性算法，在最坏的情况下将需要2"次的f评估，即将0和1分别代入来比较结果是否都为0或者1，还是一半是0一半是1，利用经典随机算法，足够数量的评估可以产生高概率的正确答案，但如果我们总是想要正确答案，仍然需要 $2 ^ { \prime \prime }$ 次评估。而多伊奇量子算法利用哈德门形成计算单元的量子叠加，并利用计算结果的量子相干，只需1次f评估即可产生一个总是正确的答案。

多伊奇算法是最早的量子算法，后来有用于大数分解的彼得·舒尔（Peter Shor）算法和搜索的格罗弗（Lov Grover）算法，以及量子随机走动算法，这些算法都被证明比经典的算法要快，这种快不仅是计算速度的加快，而且是计算复杂程度意义上的降低。这里尤其要提到的是舒尔的大数分解算法，它使得需要计算时间为O（N^p）的问算法要1. $6 \times 1 0 ^ { 8 }$ 步，而经典算法要 $6 . 7 \times 1 0 ^ { 5 1 }$ 步。如果计算机执行每步时间为 $1 0 ^ { - 9 }$ 秒，舒尔的算法只要不到1秒，而经典计算机要大约两千亿亿亿亿年。而我们知道的今天通用的数据安全加密系统都是基于自然数的大数分解，一旦可以这样快地分解一个很大的自然数，常用的密码系统就变得很容易被破解了。

量子门是量子电路的基本模块，就像逻辑门用于经典数字电路一样。和经典电路逻辑门一样，设计类似于经典逻辑操作中的与非门，通用量子门（可控非门）可以实现量子计算的所有算法。在经典计算机系统中，通过逻辑门以某种方式改变和修改存储在经典存储器中的二进制值，产生新的值。对于在量子存储器中具有叠加的量子系统也是如此，应用于另一个叠加的量子门，得出有效输出。量子门和经典逻辑门之间的一个主要区别是其运算的可逆性。量子门操作是可逆的，即在X上应用量子门 A，得到Y，在Y上应用量子门的逆操作A^–1，A^–1Y就会再次得到X，没有信息丢失。经典逻辑门是不可逆的，数据处理会使信息丢失，这是经典计算的巨大的问题：根据香农定律，经典计算设备因为处理信息需要消耗大量的能量，所以对系统有热量的损耗。对于量子计算来说，这个问题几乎不存在。这是个有意思的事情，我们通过量子计算知道了某些新的东西，但没有以付出相应的热量为代价。这与香农的信息熵的处理有很大的不同，也违背了经典热力学第二定律的。这是否也意味着大脑作为信息处理工具也有着量子化的基础，如果它真是以量子计算为基础，会省很多能量，这跟我们的经验是一致的。到今天的人工智能算法都以其对计算资源的占用和耗费著称，而解决大多数类似问题的人脑，它的低功耗简直让人惊奇。

在经典系统中，任何逻辑门都可以使用布尔代数表示。类似的量子门表示的变换可以描述为酉变换矩阵。在这样的矩阵中，如果门作用于n输入量子态，则矩阵的大小为 $\vert 2 ^ { \mathrm { n } } \times 2 ^ { \mathrm { n } }$ ，其中输入量子比特的数量等于输出量子比特数量。当一个量子比特能同时存储两个信息的时候，那么两个量子比特就能同时存储4个经典信息，3个量子比特就是8个经典信息……由此，当我们有50个可控的量子比特的时候，我们就有了2⁵⁰个经典信息，这已经超过了宇宙中的粒子数量。而运算操作中，如果能够充分利用量子的叠加性质、纠缠性质，那么我们就可以设计合适的算法，同时对这么多计算单元进行操作，并能顺利地读出操作结果，这些算法的运算速度，就会远远超过经典算法的运算速度。而最近的一些研究表明，在经典算法所认为的不可解问题上，量子计算是可以为其中的一些问题提供解法的。这就是说，量子计算的计算能力比经典计算要强，速度也要更快，计算效率更加节能。量子计算可能会涵盖一个更大范围的可计算问题，这对数学本身来说是具有重大意义的。

量子计算的复杂性

理论计算机科学的一项基本任务是将问题按照复杂程度来分类。计算复杂性由解决这个问题所需的资源来决定，通常指的是计算时间和计算这个问题所需要的物理资源。

例如，我们有测试某个数字是否为质数的算法，但尚未找到有效的算法求解一个大数的质因数。前者是个P问题，而后者是个NP问题。我们定义P问题是经典计算机可以快速解决的所有问题。“这个数位是质数吗？”属于P问题。NP问题是经典计算机不一定能快速解决的所有问题，但如果有答案，它们可以快速验证答案。“一个大数的质因数是什么？”属于NP问题。计算机科学家认为P问题和NP问题是不同类别的问题，但两者之间的差别是这个领域至今没有定论的最著名和最重要的问题。

1993年，计算机科学家伊桑·伯恩斯坦和优曼许·沃兹内尼定义了一个新的复杂性类BQP问题，即有限误差的量子多项式时间内能解决的问题，量子计算机在多项式时间内可以解决的一类决策问题（确定“是”或“否”答案的问题），计算的随机错误概率小于1/3。BQP问题是量子计算机可以有效解决的所有决策问题。在同一时间，他们还证明了量子计算机可以解决经典计算机可以解决的所有问题。也就是说，BQP问题包含P问题中的所有问题。但科学家希望找到一类问题，是在经典计算机NP的问题之外，BQP可解的问题。这样，就可以证明量子计算机的范畴要大于经典计算机。理论计算机科学家已经知道量子计算机可以解决经典计算机所能解决的任何问题。

2018年两位量子计算学家然·拉茨（Ran Raz）和阿维沙伊·塔尔（Avishay Tal）的工作表明有一类计算问题，量子计算机可以有效地解决，但经典计算机却不能。拉茨和塔尔的论文表明，量子计算机和经典计算机确实是不同的类别——即使在一个经典计算机成功解决了NP问题的世界里，量子计算机仍然会超越它们。

但我们无法确定BQP问题是否包含另一个被称为PH的重要问题，PH代表多项式层次结构。PH问题是NP问题的推广，它意味着如果从NP中的问题开始，并通过分层诸如“存在”和“普遍存在”之类的限定语句使其更加复杂，它将包含所有问题。今天的经典图灵机不能解决PH中的大多数问题，但你可以把PH看作是经典计算机在P等于NP的情况下可以解决的所有问题的一类。换句话说，比较BQP和PH的范畴是为了确定量子计算机是否比传统计算机具有优势，能够比经典图灵机解决更多的问题。

区分两个类是否一致的最佳方法是找到一个问题，它可以被证明是在一类而不是另一个类中。然而，由于基本障碍和技术障碍的结合，发现这样的问题一直是一个挑战。如果你想要的是BQP中的问题，但不是PH中的问题，那么你必须确定一些问题，其答案无法被一台经典图灵机有效地验证。斯科特·阿伦森（Scott Aaronson）在2009年提出这样一个问题，并证明它属于BQP问题：有两个随机数生成器，每个生成一个数字序列。计算机面临的问题是：这两个序列是完全独立的，还是以某种隐含的方式相关？比如事实上其中一个序列是另一个序列的傅立叶变换的形式。