漫画：十分钟看懂量子比特、量子计算和量子算法

这是Sheldon的第40篇漫画，请做好准备，即将进入烧脑模式！

宏观世界的生活经验很多都是表象。比如，你可能认为世界的运行是确定的、可预测的；一个物体不可能同时处于两个相互矛盾的状态。

在微观世界中，这种表象被一种叫做量子力学的规律打破了。

量子力学指出，世界的运行并不确定，我们最多只能预测各种结果出现的概率；一个物体可以同时处于两个相互矛盾的状态中。

量子计算，就是直接利用量子力学的现象（例如量子叠加态）操纵数据的过程。

在本文中，我们简单地介绍量子叠加态、量子比特、量子测量和一种实现随机数据库搜索的量子算法。

夏天到了，烈日炎炎。当你带上偏振墨镜时，从某种程度上讲，你就已开始接触量子计算了。

为什么这么说呢？因为光的偏振正好“同时处于两个相互矛盾的状态”中，也就是量子叠加态。在量子计算中，光子的偏振就可以用来实现量子比特。

首先，光是一种电磁波，组成它的粒子叫做光子。电磁波的振动就像绳子抖动一样，可以朝这儿偏也可以朝那儿偏，形成各种各样的偏振。

其次，偏振墨镜就像一个筛子，只有跟筛子的缝隙方向一致，光子才能“钻过去”。如果跟筛子的缝隙方向垂直，光子就被完全“拦住”了。

用绳子的抖动比喻光子的偏振，你就很容易理解了。

如果光子偏振方向跟缝隙方向既不垂直也不平行，而是呈一定角度，又会怎样呢？

如果你在钻过去的朝方向偏振的光子后面，再放一个只过滤光子的偏振镜，就会发现一个非常诡异的量子力学现象：大约有一半儿偏振光子穿过了偏振镜，而且偏振方向都变成了。

这个时候，运用高中学过的矢量合成知识，我们可以试着解释这个现象。

由于光子的偏振既有方向又有大小，我们可以将每个光子的偏振看做一个矢量。于是，它们满足矢量的加法。

由于方向的振动等于方向的振动加上方向的振动，我们就可以说，偏振的光子可以看作是同时在朝和方向振动。

如果你不理解什么叫同时进行两种振动，想想你耳朵里的鼓膜，正是它同时进行多种振动，你才能同时听到各种各样的声音。

这个时候，我们就可以试着解释那个奇怪的量子现象了。如果把一个偏振的光子看作是一个光子同时进行和两种振动，那么我们可以说，当这个光子路过偏振镜的时候，其中一半儿振动被挡住了，另一半儿振动通过了。

然而，这个解释并不完全对。

如果你朝这个偏振镜发出一个光子，在偏振镜之后，你并不会接收到一个振动能量减弱了一半儿的光子。而是有50%的几率接收到一个光子；50%的几率什么也没接收到。

说到这里你可能想起来了，这就是量子力学常说的“上帝掷骰子”。

如果我们把光子看做比特0，光子看做比特1，那么，一个光子就处于比特0和比特1光子的叠加状态之中。

如果你硬要用一个偏振镜去测量它到底是比特0还是比特1，就会发现，测量结果有50%的概率是比特0，还有50%的概率是比特1。

光子所携带的这种诡异的“比特”就叫做量子比特。

电子计算机所做的计算，就是在操纵经典比特。同样的道理，所谓量子计算机，就是在量子力学允许的范围内操纵量子比特。

不知道你发现了没有，由于量子比特可以同时处于比特0和比特1的状态，量子门操纵它时，实际上同时操纵了其中的比特0和比特1的状态。

所以，操纵1个量子比特的量子计算机可以同时操纵2个状态。如果一个量子计算机可以同时操纵N个量子比特，那么它实际上可以同时操纵2N个状态，其中每个状态都是一个N位的经典比特。

这就是量子计算机传说中的并行计算能力。

最后，让我们用量子计算的Grover算法来说明它是如何并行计算的。

假设我们有N个未经排序的数据。如果使用经典算法寻找其中的某个数据x，条件是它（并且只有它）满足P(x)=TRUE，比方说x代表一个人的工号，P(x)是看他是不是现任CEO。那么你只能从第一个数据开始，一个一个地看它是不是CEO的工号，直到你瞎猫碰上死耗子。

在这种算法中，计算复杂度是O(N)。

在Grover算法中，我们可以将N个数据同时储存在log2N个量子比特中，然后同时计算N个函数P( )的取值，也就是同时看它是不是CEO的工号。

在N个计算结果中，必然有1个结果是CEO的工号，其他结果都不是。但如果你这个时候贸然去“读取”结果，就会发现，每个结果发生的概率都是1/N。

这就好比你用偏振镜去测量光子，得到和的概率各为1/2。

Grover算法的思想是，同时计算了N个P( )的取值后，先不要读取，而是通过量子操作略微增加结果为CEO工号的那个数据发生的概率。

数学计算证明，反复重复以上过程 (π√N)/4次之后，你要找的那个数据发生的概率就会达到最大，最终达到（1-2-N）。这个时候如果你再去读取数据，就会以极大的概率读到你要找的数据。

所以，Grover的量子搜索加速算法，可以将搜索复杂度降低到O(√N)，但你成功读取那个数据的概率永远也不会达到100%，而是会略小于100%。

从目前的情况看，量子计算只是在少数计算任务中表现的比经典计算更快，例如大数质因子（Shor算法）、随机数据库搜索（Grover算法），并且，这种快法不能挣脱量子力学的约束，达到十全十美。

注：为什么Grover算法的操作必须且最多只能重复(π√N)/4次？

请你想象一个N维空间，每个维度代表log2N个量子比特所存储的一个状态。由于这种空间在纸上画不出来，我们需要进行一些简化，假设右边这个二维空间代表那个N维空间。其中一个维度|X>表示你要搜索的数据对应的状态，另一个维度|s’>表示除|X>以外所有其他N-1个数据相叠加所对应的状态。

Grover算法的初始状态，就代表其中一个矢量|s>。

Grover算法采用的量子操作，就是像拨动表盘上的时针一样，不断将矢量|s>朝着|X>的方向拨过去，每次拨动的角度只能是θ，其中。θ=2arcsin(1/√N)。

注意我们说过，一个量子叠加态跟哪个方向的夹角越小，测量时得到哪个方向的结果的概率就越大。不难计算，将矢量|s>这样拨动π/2θ≃(π√N)/4次之后，它与|X>的夹角最小，测量时得到你要找的正确结果的概率最大。

注意，在这个比喻中，我们没有考虑N个状态之间的相位，但这并不影响讨论的结果。

对白：牛猫、美指：牛猫、绘制：赏鉴、排版：胡豆

本文已发表于腾讯内部资料《腾云》

参考文献：

1. E.Rieffel,W.Polak,An Introduction to Quantum Computing for Non-Physicists.

2.E.Strubell,An Introduction to Quantum Algorithms.