量子计算入门

Brad Huntting克罗拉多大学
David MertzGnosis Software，Inc.

2001 年 9 月 01 日

在未来的几十年里，量子计算机很可能会走出科幻小说与科研实验室（主要在IBM）进入实际应用。在量子计算机（QuantumComputers，QC）上可以有效的解决与复杂的组合数学有关的一类问题，对于确定性计算机而言，这些问题是很讨厌的。建立在向量数学基本知识的基础之上，本文将对量子计算作一番介绍。说明用的示例使用了qcl（量子计算语言，quantum computing language），这是在 GNU GeneralPublic License管理之下分发的、用于量子计算机的一种免费的程序语言。qcl允许开发人员模拟并测试“虚拟的”量子计算机。本文作者，Brad Huntting和 David Mertz，是数学专家和经验丰富的程序员。David Mertz 经常为 developerWorks撰稿。
Alan Turing 在 1936 年发明可编程计算机（请参阅参考资料）是作为一种思想实验以证明某些数学问题不可计算。在他的论证中，隐含的观点是一台装有足够资源的计算机能实现任何合理的算法。

从那时起，计算机工业不仅得以建造可编程计算机器，而且还通过每十八个月左右就使能力加倍，从而超越了它们自身。虽然计算机技术疯狂的向前发展，但是现代计算机仍无法在难题方面取得显著进展。需要指数资源的问题（同问题本身的大小相比）在当今仍然同 1936 年时一样棘手。

1982 年 Richard Feynman 提出，值得尊敬的 Turing 机器的功能也许并没有人们所想的那么强大。当时 Feynman 正在试图用量子力学模拟 N 粒子之间的相互作用。尽管他很努力，但他没能找到不使用指数资源的一般性解法。

然而不知为什么，大自然能仅使用 N 粒子模拟这一数学问题。结论是不可避免的：大自然具有建造非常高级的计算设备的能力，这说明 Turing 机器还不是人们从前所认为的全能计算机。

使量子计算问题形象化

QC 算法涉及就概率因子进行思考，对于现在的程序员而言，这是概念上的变化。在某些方面，这就象第一次卷入使用 OOP（面向对象编程方法）、结构化编程或多线程时概念上的转变。从另一种角度来看，这种转变更为重要，因为这使全新的一类（有可能）没有替代物的问题开始出现了。

让我们想象一下下面这个问题。我们要找一条路穿过一个复杂的迷宫。每次我们沿着一条路走，很快就会碰到新的岔路。即使知道出去的路，还是容易迷路。换句话说，有一个著名的走迷宫算法就是右手法则－顺着右手边的墙走，直到出去（包括绕过绝路）。这条路也许并不很短，但是至少您不会反复走相同的过道。以计算机术语表述，这条规则也可以称作递归树下行。

现在让我们想象另外一种解决方案。站在迷宫入口，释放足够数量的着色气体，以同时充满迷宫的每条过道。让一位合作者站在出口处。当她看到一缕着色气体出来时，就向那些气体粒子询问它们走过的路径。她询问的第一个粒子走过的路径最有可能是穿过迷宫的所有可能路径中最短的一条。

当然，气体颗粒绝不会给我们讲述它们的旅行。但是 QC 以一种同我们的方案非常类似的方式运作。即，QC 先把整个问题空间填满，然后只需费心去问问正确的解决方案（把所有的绝路排除在答案空间以外）。

回页首

qcl 量子计算机模拟器

在一台传统的经典计算机上模拟量子计算机是个难题。需要的资源随被模拟的量子内存数量增加呈指数增长，以致于连模拟一台只有几十个量子位（quantum bit，qubit）的 QC 也远远超出了现在制造的任何一台计算机的能力范围。

qcl 只模拟非常小的量子计算机，但幸运的是，它的效力刚好足够大，可以展示一些有用的 QC 算法背后的概念。

和过去的超级计算机一样，未来的第一台 QC 的核心很可能由一些存储和控制量子态机器的奇特硬件组成。其外围将会是生命支持硬件以支援核心并把适当的编程环境呈现给用户。qcl 通过为经典程序结构提供量子数据类型及对其执行操作的特殊函数来模拟这样一种环境。

让我们从一些经典计算中常见的运算开始使用 qcl。由于 qcl 是语法上模糊的类似于 C 的交互式解释器，所以我们只要启动它就可以往里面输入命令。为了使我们的示例更具可读性，我们把被模拟的量子位数目限制为 5 位。

清单 1. 初始化 qcl 并转存一个量子位
$ qcl --bits=5
[0/8] 1 |00000>
qcl> qureg a[1];
qcl> dump a
: SPECTRUM a: |....0>
1 |0>

此处我们在 qcl 量子堆中为一个 1 量子位（布尔型）变量分配空间。机器的量子态（ |00000> ）被初始化为全 0。符号 |> 表示这是量子态（有时也叫做 ket），而 5 个 0 的字符串（一个 0 代表量子堆中的一位）就形成该状态的标签。这叫做量子力学的 Dirac 标记法（也可以称做 bra-ket）。同线性代数传统的数学标记法相比，其主要优点是更易于输入。

“qureg a[1]”为量子堆中的 1 位变量 a 分配空间。 dump a 命令给了我们一些关于 a 的信息。 SPECTRUM 行告诉我们在量子堆中分配给 a 的量子位的位置；在这种情况下， a 的 0 位是堆中右面第一位的量子位。下面一行告诉我们，如果我们要测量 a ，那么我们认为“0”的概率为“1”。

当然，因为 qcl 是一个模拟器，所以只是有可能能窥到量子内存。只有不可撤回的改变值才能观察到真正的量子位。后面还有更多这方面的内容。

qcl 提供的基本量子运算符中有许多在经典计算中很常见。例如， Not() 函数会把一位的值取反。

清单 2. 对一个量子位使用布尔型函数
qcl> Not(a);
[2/8] 1 |00001>

再次对同一量子位使用 Not() 将撤消第一次的结果，这正是我们在经典计算中所预期的。

CNot(x,y) 运算符测试 y 的值，如果是“1”，则对 x 的值取反。等价于 C 中的 x^=y 语句。

清单 3. 其它一些量子位运算符（CNot）
qcl> qureg b[2];
qcl> Not(b[1]);
[3/8] 1 |00100>
qcl> CNot(b[0], b[1]);
[3/8] 1 |00110>
qcl> dump b[0];
: SPECTRUM b[0]: |...0.>
1 |1>
qcl> dump b[1];
: SPECTRUM b[1]: |..0..>
1 |1>

CNot() 运算符同 Not() 运算符一样，是它本身的逆。第二次应用时，它会把第一次的结果反过来，使您回到同开始时一样的状态。

可逆性观点是理解量子计算的关键。理论物理学告诉我们对量子位进行的所有操作（除了测量以外）必须可撤消。我们必须一直保留足够的信息以复原任何操作。这意味着象赋值（x=y）、AND（ x&=y ）和 OR（ x|=y ）（在经典计算中我们认为这些运算是理所当然的）就必须为能在 QC 中使用而修改了。幸运的是，有一个简单的方案可以把不可逆的经典运算转换成量子运算。

首先，除了要把量子位初始化为“0”，我们绝不重写它。因此在我们本来可以进行赋值（x=y）的地方，我们没有这么做，而是把目标初始化（x=0）并如同上面的示例一样使用异或（x^=y）。

如果 y 和 z 的值都是“1”， CNot(x, y & z) 会对 x 的值取反。因此如果在开始前我们就把 x 初始化成“0”，那么这就象计算 y & z 并把值存到 x 里。这是一个细微的区别，但却是量子计算中的一个重要区别。

现在让我们看看一些无经典类似情况的运算。最引人注目的，同时也是最有用的其中之一就是 Hadamard 函数，qcl 把它恰当的标记为 Mix() 。 Mix() 把计算基态，如 |0> 或 |1> ，变成量子叠加。下面一个量子位的示例：

清单 5. 用 Mix() 进行状态叠加
[0/8] 1 |00000>
qcl> qureg a[1];
qcl> dump a;
: SPECTRUM a: |....0>
1 |0>
qcl> Mix(a);
[1/8] 0.707107 |00000> + 0.707107 |00001>
qcl> dump a;
: SPECTRUM a: |....0>
0.5 |0> + 0.5 |1>

本例中，我们利用了量子力学的叠加原理。根据 dump a ，如果我们要测量 a ，我们会认为“0”或“1”的概率都等于 0.5（0.707107 2）。

如果您以前从未接触过叠加这个概念，那么它可能有点儿令人困惑。量子力学告诉我们，小粒子，比如电子，可以同时处于两个位置。同样，一个量子位可以同时有两个不同的值。理解这一切的关键在于向量算术。

和经典计算机机器状态只是唯一的一串 1 和 0 不同，QC 的状态是一个向量，其分量包括所有可能的 1 和 0 组成的字符串。换一种方式来说，这些 1 和 0 组成的字符串构成了我们的机器状态生存的向量空间的基础。我们可以通过写出如下的和来把 QC 的状态写下来：

清单 6. 量子计算机的向量态
a|X> + b|Y> + ...

此处 X 、 Y 等是 1 和 0 组成的字符串， a 、 b 等是分量 X、Y 等的振幅。 |X> 标记正是物理学家们表示“名叫 X 的向量（或状态）”的方式。

如果我们有两个量子位 a 与 b （初始化成 0）并对 a 执行了一系列量子运算，然后对 b 执行同样的运算，我们应当预期结束时 a 和 b 的值相同，确实是这样。

清单 7. 独立叠加的量子位
qcl> qureg a[1];
qcl> Not(a);
[1/8] 1 |00001>
qcl> Mix(a);
[1/8] 0.707107 |00000> + -0.707107 |00001>
qcl> qureg b[1];
qcl> Not(b);
[2/8] 0.707107 |00010> + -0.707107 |00011>
qcl> Mix(b);
[2/8] 0.5 |00000> + -0.5 |00010> + -0.5 |00001> + 0.5 |00011>
qcl> dump a
: SPECTRUM a: |....0>
0.5 |0> + 0.5 |1>
qcl> dump b
: SPECTRUM b: |...0.>
0.5 |0> + 0.5 |1>

在这个示例中， a 和 b 是完全独立的。如果我们测量其中一个，那么不应当对另外一个造成任何影响。

清单 8. 独立测量的量子位
qcl> measure a;
[2/8] -0.707107 |00001> + 0.707107 |00011>
qcl> dump b
: SPECTRUM b: |...0.>
0.5 |0> + 0.5 |1>

正如我们所预期的， b 的频谱并没有因测量 a 而改变。

如果运算比简单的 Not();Mix() 要复杂，那么我们可能很想只对 a 执行一次这些运算，然后把值从 a 拷贝到 b 。不错，虽然我们无法真的进行拷贝（因为拷贝不是可逆运算），但是我们可以把 b 初始化为 0，然后用 CNot(b,a) 会达到相同的目的。

很可惜，它所做的并不是我们所预期的。但还是让我们尝试一下看看会得到什么结果：

清单 9. 尝试量子位拷贝运算
qcl> qureg a[1];
qcl> Not(a);
[1/8] 1 |00001>
qcl> Mix(a);
[1/8] 0.707107 |00000> + -0.707107 |00001>
qcl> qureg b[1];
qcl> CNot(b,a);
[2/8] 0.707107 |00000> + -0.707107 |00011>
qcl> dump a;
: SPECTRUM a: |....0>
0.5 |0> + 0.5 |1>
qcl> dump b;
: SPECTRUM b: |...0.>
0.5 |0> + 0.5 |1>

a 和 b 的频谱看起来是正确的。而且事实上如果我们只对 a 或 b 中的一个进行测量，我们就会得到和上面一样的结果。区别在于我们对 a 和 b 都进行测量时所发生的事。

请记住测量结果是随机的，因此如果您正反复做这个实验，您的结果可能会有所不同。

清单 10. 测量使量子位叠加坍缩
qcl> measure a;
[2/8] -1 |00011>
qcl> dump b
: SPECTRUM b: |...0.>
1 |1>

通过测量 a ，我们使 b 的叠加坍缩了。这是因为 a 与 b 纠缠在物理学家们所说的 EPR 对中，继 Einstein 之后，Podolsky 和 Rosen 都试图用它来说明量子力学是一个不完整的理论。然而，John Bell 后来通过实验反驳 Bell 不等式（正是它使 EPR 思维实验正式化）证明了真实粒子间的纠缠。

您试图把一个量子变量拷贝到另一个上时发生了什么事？您以最终得到的是纠缠，而非真正的拷贝。

回页首

Deutsch 问题

假定我们有一个函数，它有一个参数是一个二进制位，返回的也是一个二进制位。为了使事情向好的方向发展，让我们要求这是一个伪经典函数。如果我们传给它一个经典的二进制位（0 或 1）作参数，它将返回一个经典二进制位。

确切地说，有 4 种可能的函数满足这一要求。

清单 11. 共 4 种可能的布尔型一元函数
f(x) -> 0# constant zero result
f(x) -> 1# constant one result
f(x) -> x# identity function
f(x) -> ~x# boolean negation

前两个是常量，也就是说，不管输入如何，它们总是输出相同的值。后两个是对称的，即一半时间输出 0 ，一半时间输出 1。经典意义上，要确定 f() 是常量还是对称的只有对该函数进行两次计算。

Deutsch 问题要我们只对 f() 进行一次计算就确定 f() 是常量还是对称的。以下是其工作原理。

首先，我们得用 qcl 构造一个伪经典运算符来对 f(x) 进行计算。我们将定义一个带输入输出参数的量子函数来构造该函数。例如：

清单 12. 用 qcl 语言定义一个量子函数
qufunct F(qureg out, quconst in) {
CNot(out, in);
Not(out);
print "f(x)= ~x";
}

如果 out 被初始化成“0”，调用这个函数就会把 out 变成 f(x)=~x 。您可以把 CNot() 或 Not() 代码行注释掉得到其它三种可能的函数中的一种。我们把上面的代码片断放在一个叫做 f_def.qcl 的文件中以后，我们就可以测试 F() 以确保它所做的正是我们想要的：

qcl> dump out
: SPECTRUM out: |...0.>
1 |0>

现在让我们重置量子内存并运行 Deutsch 算法。它首先要把 in 和 out 位放到四种基态的叠加中去才能工作。

清单 14. Deutsch 算法（加上了行号）
(01) qcl> reset;
(02) qcl> int result;
(03) qcl> Not(out);
(04) [2/8] 1 |00010>
(05) qcl> Mix(out);
(06) [2/8] 0.707107 |00000> + -0.707107 |00010>
(07) qcl> Mix(in);
(08) [2/8] 0.5 |00000> + 0.5 |00001> + -0.5 |00010> + -0.5 |00011>
(09) qcl> F(out,in);
(10) : f(x)= ~x
(11) [2/8] 0.5 |00010> + 0.5 |00001> + -0.5 |00000> + -0.5 |00011>
(12) qcl> Mix(in);
(13) [2/8] 0.707107 |00011> + -0.707107 |00001>
(14) qcl> Mix(out);
(15) [2/8] -1 |00011>
(16) qcl> measure in, result;
(17) [2/8] -1 |00011>
(18) qcl> if (result == 0) { print "constant"; } else { print "balanced"; }
(19) : balanced

1-7 行我们把 in/out 位放入四种基态的一个叠加中，其中“out=0”状态为正振幅 +0.5，而“out=1”状态为负振幅 -0.5。请注意即使我们有四个非 0 振幅，这些振幅绝对值的平方和总能达到 1。

第 9 行我们运行量子函数 F() ，它把 f(in) 的值 XOR 到 out 量子位。函数 F() 是伪经典的，意味着它交换基本向量，但是不会对任何振幅作更改。因此应用 F() 后我们仍有两个振幅的值为“+0.5”，两个振幅的值为“-0.5”。

通过对叠加态应用 F() 函数，我们一下子就对所有的四种基态有效的应用了 F() 。这就是所谓的“量子并行性”，它是 QC 的一个重要元素。当然我们的模拟器不得不轮流在每种基态应用 F() ，但真正的 QC 是把 F() 作为一步运算应用到组合态。

14 行和 16 行的 Mix() 函数对机器状态的叠加态取反回到计算基态（ |00011> ）。如果我们没有运行第 9 行的 F() ，这会把我们带回到第 4 行的状态（因为 Mix() 是其本身的逆）。但是因为我们用 F() 交换了振幅，撤消叠加使我们处于一种不同于我们在第 9 行时的状态。特别是 in 量子位现在被设置成“1”而非“0”。

注意到在 15 行的振幅 -1 不重要也是很有益的。量子态是向量，我们并不关心其总长度（只要不是 0）。只有向量方向，即分振幅之间的比值，是重要的。通过保持量子态是单位向量，变换就都是幺正的。这不仅使理论数学容易的多了，而且还使经典计算机上数字计算中出现的错误不致于象滚雪球般失去控制。

回页首

受控相位变换

量子计算最初的目标是使用很少一部分基本元素模拟变化多端的量子系统的行为。到目前为止，我们已经讨论了 Not() 、 CNot() 和 Mix() 函数。要使集合完整并考虑普遍的量子计算，那么我们需要受控相位函数， CPhase() 。

CPhase() 的第一个参数是（经典的）浮点数，第二个参数是一个量子位。 CPhase(a,x) 对机器的基态分量振幅的改变如下：

x 是 |0> 的基态振幅没有更改，而
x 是 |1> 的基态振幅乘上了 exp(i*a)=cos(a)+i*sin(a)。
x=1 时的机器状态系数在复平面内转过了 a 弧度。例如：

清单 15. 演示 CPhase() 函数
$ qcl --bits=5
[0/5] 1 |00000>
qcl> qureg a[1];
qcl> Mix(a);
[1/5] 0.707107 |00000> + 0.707107 |00001>
qcl> CPhase(3.14159265, a);
[1/5] 0.707107 |00000> + -0.707107 |00001>
qcl> reset
[1/5] 1 |00000>
qcl> Mix(a);
[1/5] 0.707107 |00000> + 0.707107 |00001>
qcl> CPhase(0.01, a);
[1/5] 0.707107 |00000> + (0.707071,0.00707095) |00001>
qcl> dump a
: SPECTRUM a: |....0>
0.5 |0> + 0.5 |1>

由于 exp(i*pi)=-1， CPhase(pi,x) 会对 |1> 分量的符号取反。 CPhase(0.01, x) 在复平面内使 |1> 分量的相位转过了百分之一弧度。括弧里的元组（0.707071，0.00707095）是复数 exp(0.01*i)=0.707071+i*0.00707095 的 qcl 表达式。

回页首

更大的问题及解决方案

Deutsch 问题及其 N 位泛化，即 Deutsch-Jozsa 问题，也许有趣，但是没有太多的实际价值。幸运的是，另外还有一些量子算法让人希望会有更大的收益。

例如 Shor 的算法能在多项式时间内找到一个 N 位函数的周期。虽然听起来这并不是什么了不起的事，但分解并找到一个离散对数的困难形成了大部分公用密钥密码学系统的基础，如果不是全部的话。

虽然不那么壮观，但是用可以在 O(sqrt(N)) 时间内搜索一个无序的 N 项列表的 Grover 算法实现起来容易得多。要搜索这样的列表，最好的经典算法平均要 N/2 次迭代。

回页首

结论

自从经典计算机开始出现，模拟电子电路以促进更快的计算机的设计就一直是其任务之一。这一反馈循环一直在促进计算机工业半个世纪以来的爆炸式发展。量子计算机具有潜力把这一爆炸式的发展转变的更具活力，如同 QC 用于创造更快更有力的量子计算元件一样。

2000 年 8 月间，IBM Almaden Research Center 的 Isaac L. Chuang 宣布他和他的合作者们已经建造了一台 5 量子位的机器，利用的是一个有 5 个氟原子的分子（请参阅参考资料）。不幸的是，这一技术可能无法发展到可用的规模。

那么何时才能建成第一台可伸缩的量子计算机呢？有一些存储、操作和移动量子位的候选技术。完整的列表已超出了本文的范围，但是还要再过一、二十年才会有第一个有用的 QC 的说法可能还是可靠的。

[align=right][此贴子已经被作者于2006-5-19 21:14:30编辑过][/align]