量子电路可以用来进行什么样的计算？与利用经典逻辑电路做的计算相比如何？是否能够找到量子计算机比经典计算机完成得更好的任务？在这一节我们将研究这些问题，解释如何在量子计算机上做经典计算，给出一些量子计算机优于经典计算机的例子，并总结已有的量子算法。
我们是否能用量子电路模拟一个经典逻辑电路？不出意外，答案是肯定的。如果答案是否定的，那么就太意外了。因为物理学家相信，我们周围的世界，包括经典逻辑电路，根本上都能用量子力学解释。在前面已指出，量子电路不能直接用于模拟经典电路，因为西量子逻辑门本质上是可逆的，然而许多经典逻辑门如与非门本质上是不可逆的。
任何经典电路都可以用等价的仅含可逆元件的，由可逆门 Toffoli 门构成的电路代替。Toffoli门含有 3 个输人比特，如图 1－14 所示。有两个比特是控制比特，它们不会受到 Toffoli 门作用的影响。第 3 个比特是目标比特，当两个控制比特都置为 1 时目标比特翻转，否则不变。注意到，作用 Toffoli 门两次后，比特变化为 $(a, b, c) \rightarrow(a, b, c \oplus a b) \rightarrow(a, b, c)$ 。因此，Toffoli 门是可逆门，且它的逆就是它自己。
Toffoli 门能被用于模拟与非门，如图 1－15 所示，还可以用于实现扇出，如图 1－16 所示。有了这两个操作就可以模拟经典电路中的其他元件，所以任意经典电路都可以被等价的可逆电路模拟。
Toffoli 门虽然以经典门出现，但是它可以作为量子逻辑门实现。根据定义，Toffoli 门的量子逻辑实现只是按照与经典 Toffoli 门同样的方式置换基矢态。例如，量子 Toffoli 门作用在态 $|110\rangle$
上翻转第 3 个比特，因为前两个比特被置位，最终得到量子态 $|111\rangle$ 。虽然很烦琐，但是具体写出这个 $8 \times 8$ 矩阵 $U$ 并不难，并且可以验证 $U$ 是一个酉矩阵。因此，Toffoli门是一个合法的量子门。就像经典 Toffoli 门一样，量子 Toffoli 门可用于模拟不可逆经典逻辑门，并且保证量子计算机可以进行任何经典（确定性）计算机能够完成的计算。
| 输入 | 输出 | ||||
|---|---|---|---|---|---|
| $a$ | $b$ | $c$ | $a^{\prime}$ | $b^{\prime}$ | $c^{\prime}$ |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 |
图 1－14 Toffoli 门的真值表和电路表示
图 1－15 利用 Toffoli 门实现 NAND 门的经典电路。上方两比特表示 NAND 门的输人，第 3 个比特设置为标准状态 1 ，有时被称为辅助态。NAND门的输人是第 3 个比特
图 1－16 用 Toffoli 门实现的扇出。第 2 个比特是扇出的输人（其他两个比特是标准辅助态），扇出的输出在第 2 个和第 3 个比特
如果经典计算机是非确定的，也就是说，在计算中有能力产生随机比特，又会怎么样呢？不奇怪，量子计算机可以很容易模拟它。为了实现这个模拟，只需产生一个均匀随机硬币的投掷，可以令单比特态 $|0\rangle$ 通过一个阿达玛门得到 $(|0\rangle+|1\rangle) / \sqrt{2}$ ，再测量这个态。结果是 $|0\rangle$ 和 $|1\rangle$ 各 $50 \%$ 的概率。这就为量子计算机提供了有效模拟不确定的经典计算机的能力。
当然，如果模拟经典计算机是量子计算机仅有的特点，那么探索量子效应就没有必要了。量子计算的优势在于利用量子比特和量子门可以计算功能更强大的函数。在下面几节中我们会借助 Deutsch－Jozsa 算法解释这是如何实现的，它是我们的第一个例子，量子算法能比任何经典算法都要更快地求解问题。
量子并行性（quantum parallelism）是许多量子算法的基本性质。简而言之，量子并行性允许量子计算机同时计算在不同 $x$ 值下的函数值 $f(x)$ 。本节我们将解释量子并行性的原理及其局限性。
假定 $f(x):{0,1} \rightarrow{0,1}$ 是定义域与值域均为一比特的函数。在量子计算机上计算这个函数的简单方式是考虑初态为 $|x, y\rangle$ 的两比特的量子计算机。通过适当的逻辑门序列可以将该初态
转化为 $|x, y \oplus f(x)\rangle$ ，其中 $\oplus$ 表示模 2 加法；第一个寄存器被称为数据寄存器，第二个寄存器被称为目标寄存器。我们将映射 $|x, y\rangle \rightarrow|x, y \oplus f(x)\rangle$ 定义为 $U_{f}$ ，并且注意到它是一个酉变换。如果 $y=0$ ，那么第二个量子比特的终态是值 $f(x)$ 。（在 3.2 .5 节，我们将说明给定一个计算 $f$ 的经典电路，在量子计算机中存在一个效率相当的量子电路计算变换 $U_{f}$ 。这里我们可以将它看成一个黑盒。）
考虑图 1－17 所示电路，把 $U_{f}$ 加到计算基以外的输人上。在数据寄存器中制备叠加态 $(|0\rangle+$ $|1\rangle) / \sqrt{2}$ ，它可以由将一个阿达玛门作用到 $|0\rangle$ 上得到。然后作用 $U_{f}$ ，得到态
$$ \begin{equation*} \frac{|0, f(0)\rangle+|1, f(1)\rangle}{\sqrt{2}} \tag{1.37} \end{equation*} $$
这是一个值得注意的状态。不同的项中包含 $f(0)$ 和 $f(1)$ 的信息；这看起来好像是同时计算了 $f(x)$ 的两个值，这就是＂量子并行性＂的特性。和经典的并行性用多个电路同时计算 $f(x)$ 不同，利用量子计算机处于不同状态的叠加态的能力，在这里单个 $f(x)$ 电路用来同时计算多个 $x$ 的函数值。
图 1－17 同时计算 $f(0)$ 和 $f(1)$ 的量子电路。量子电路 $U_{f}$ 将输人 $|x, y\rangle$ 转化为 $|x, y \oplus f(x)\rangle$ 利用阿达玛变换，有时也叫沃尔什－阿达玛变换（Walsh－Hadamard transform），这个过程很容易推广到任意比特的函数上。这个变换是将 $n$ 个阿达玛门同时作用在 $n$ 比特上。举个例子，如图 1－18 所示，当比特数 $n=2$ 且初态制备为 $|0\rangle$ 时，输出为
$$ \begin{equation*} \left(\frac{|0\rangle+|1\rangle}{\sqrt{2}}\right)\left(\frac{|0\rangle+|1\rangle}{\sqrt{2}}\right)=\frac{|00\rangle+|01\rangle+|10\rangle+|11\rangle}{2} \tag{1.38} \end{equation*} $$
我们用 $H^{\otimes 2}$ 表示两个阿达玛门并行作用，将 $\otimes$ 读作＂张量积＂。更一般地，当初态均为 $|0\rangle$ 时，$n$比特上均作用阿达玛门后得到
$$ \begin{equation*} \frac{1}{\sqrt{2^{n}}} \sum_{x}|x\rangle \tag{1.39} \end{equation*} $$
其中求和是对所有 $x$ 的可能值求和，我们用 $H^{\otimes n}$ 表示这个作用。也就是说，阿达玛变换可以产生所有计算基的平衡叠加。此外，它的效率非常高，仅用 $n$ 个门就产生了 $2^{n}$ 个状态的叠加。
$$ \begin{aligned} & -\sqrt{H}- \\ & -\sqrt{H} \end{aligned} $$
图 1－18 两个量子比特的阿达玛变换 $H^{\otimes 2}$ 可以采用下面的方法进行 $n$ 比特输人 $x$ 和单比特输出 $f(x)$ 函数的量子并行性计算。制备 $n+1$ 比特的量子态 $|0\rangle^{\otimes n}|0\rangle$ ，然后将阿达玛变换作用在前 $n$ 个量子比特上，再通过量子电路 $U_{f}$ 。
产生的态为
$$ \begin{equation*} \frac{1}{\sqrt{2^{n}}} \sum_{x}|x\rangle|f(x)\rangle \tag{1.40} \end{equation*} $$
在某种程度上，量子并行性能同时计算出函数 $f$ 的所有值，即使我们只计算了函数 $f$ 一次。然而，并行性并不能马上起作用。在单量子比特的例子中，测量量子态最终只能得到 $|0, f(0)\rangle$ 或者 $|1, f(1)\rangle$ ！类似地，在通常情况下，测量量子态 $\sum_{x}|x, f(x)\rangle$ 只能得到一个 $x$ 的函数值 $f(x)$ 。当然，经典计算机也能很容易做到这一点！为了真正有用，量子计算要求的不仅仅是量子并行性，它要求比从叠加态 $\sum_{x}|x, f(x)\rangle$ 中得到一个 $f(x)$ 值更高的信息抽取能力。下面我们会通过两个例子看到这是如何实现的。
将图 1－17 所示电路稍加修改，就可以实现 Deutsch 算法并说明量子电路如何超越经典电路 （我们实际上展示的是对原始算法的简化和改进版本；参见本章末尾的＂背景资料与延伸阅读＂）。 Deutsch 算法将量子并行性和量子力学中的重要性质相干性结合了起来。和以前一样，我们用阿达玛门将第一个量子比特制备为叠加态 $(|0\rangle+|1\rangle) / \sqrt{2}$ ，但将阿达玛门作用在 $|1\rangle$ 上将第二个量子比特 $y$ 制备为叠加态 $(|0\rangle-|1\rangle) / \sqrt{2}$ 。让我们随着状态看到底会发生什么，如图 1－19 所示。
图 1－19 Deutsch 算法的量子电路实现 输人态
$$ \begin{equation*} \left|\psi_{0}\right\rangle=|01\rangle \tag{1.41} \end{equation*} $$
通过两个阿达玛门后得到
$$ \begin{equation*} \left|\psi_{1}\right\rangle=\left[\frac{|0\rangle+|1\rangle}{\sqrt{2}}\right]\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right] \tag{1.42} \end{equation*} $$
容易得到，如果将 $U_{f}$ 作用在态 $|x\rangle(|0\rangle-|1\rangle) / \sqrt{2}$ 将得到 $(-1)^{f(x)}|x\rangle(|0\rangle-|1\rangle) / \sqrt{2}$ 。将 $U_{f}$ 作用在 $\left|\psi_{1}\right\rangle$ 上得到下面两种可能情况中的一个：
$$ \left|\psi_{2}\right\rangle= \begin{cases} \pm\left[\frac{|0\rangle+|1\rangle}{\sqrt{2}}\right]\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right] & \text { 若 } f(0)=f(1) \tag{1.43}\\ \pm\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right]\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right] & \text { 若 } f(0) \neq f(1)\end{cases} $$
最后的阿达玛门作用在第一个量子比特上得到
$$ \left|\psi_{3}\right\rangle= \begin{cases} \pm|0\rangle\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right] & \text { 若 } f(0)=f(1) \tag{1.44}\\ \pm|1\rangle\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right] & \text { 若 } f(0) \neq f(1)\end{cases} $$
注意到当 $f(0)=f(1)$ 时 $f(0) \oplus f(1)$ 的值为 0 ，否则为 1 。我们可以将结果写作
$$ \begin{equation*} \left|\psi_{3}\right\rangle= \pm|f(0) \oplus f(1)\rangle\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right] \tag{1.45} \end{equation*} $$
所以通过测量第一个量子比特，我们可以确定 $f(0) \oplus f(1)$ 。这确实非常有趣：量子电路有能力通过计算一次 $f(x)$ 来确定 $f(x)$ 的全局性质，也就是 $f(0) \oplus f(1)$ ！这比任何经典的设备都要快，经典设备至少需要两次计算。
这个例子使量子并行性与经典随机算法区分开来。人们可能简单地认为状态 $|0\rangle|f(0)\rangle+$ $|1\rangle|f(1)\rangle$ 接近于以 $1 / 2$ 的概率计算 $f(0)$ ，以 $1 / 2$ 的概率计算 $f(1)$ 的经典计算机。和在经典计算机中这两种选择互斥不同，在量子计算机中，两种选择可能通过相互干涉而给出函数 $f(x)$ 的某些全局性质，就像在 Deutsch 算法中利用类似阿达玛门将不同的选择重新结合起来。众多量子算法其设计的本质都是精心选择函数和最终变换，使得能高效地确定有用的全局信息——这些信息无法很快地在经典计算机上得到。
Deutsch 算法是某种更一般的量子算法的简单情况，后者称为 Deutsch－Jozsa 算法。该算法的应用——Deutsch 问题，可以描述成如下游戏。在阿姆斯特丹的 Alice，从 0 到 $2^{n}-1$ 中选择一个数 $x$ ，将它写信寄给波士顿的 Bob。Bob 计算出某个函数 $f(x)$ 的值，不是 0 就是 1 ，并将它寄回给 Alice。现在，Bob 保证只使用两种函数中的一种；要么 $f(x)$ 对于所有的 $x$ 均为常数，要么 $f(x)$ 是平衡函数，即恰好对于所有可能的 $x$ 一半取 1 ，另一半取 0 。Alice 的目标是利用尽可能少的通信，确定 Bob 究竟选择了常函数还是平衡函数。Alice 多快能成功？
在经典的情况中，Alice一次只能发一个 $x$ 的值给 Bob。在最坏的情况下，Alice 将会询问 Bob至少 $2^{n} / 2+1$ 次，因为在她最终收到一个 1 之前可能将会收到 $2^{n} / 2$ 个 0 ，从而知道 Bob 选择了平衡函数。她能使用的最好的确定性经典算法需要 $2^{n} / 2+1$ 次查询。注意到在每封信中，Alice发送给 Bob 共 $n$ 比特的信息。此外在这个例子中，物理距离被用来人为地增加计算函数 $f(x)$ 的开销，但是在一般问题中这不必要，因为 $f(x)$ 可能固有地难以计算。
如果 Bob 和 Alice 被允许交换量子比特，而不是经典比特，并且如果 Bob 同意用一个西变换 $U_{f}$ 计算 $f(x)$ ，那么 Alice 可以利用下面的算法，仅仅通过与 Bob 的一次通信来达到目的。
和 Deutsch 算法类似，Alice 用 $n$ 量子比特寄存器来存储她的输人，给 Bob一个单量子比特寄存器存储答案。开始时她将查询和答案寄存器制备为一个叠加态。Bob 将会利用量子并行性计
算 $f(x)$ 并将答案写进答案寄存器中。Alice 随后利用阿达玛变换干涉查询寄存器的叠加状态，再通过合适的测量确定 $f$ 是平衡函数还是常函数。
算法的具体细节如图 1－20 所示。让我们考察电路中的状态。类似于式（1.41），输人态为
$$ \begin{equation*} \left|\psi_{0}\right\rangle=|0\rangle^{\otimes n}|1\rangle \tag{1.46} \end{equation*} $$
但是查询寄存器描述了处于 $|0\rangle$ 状态的全部 $n$ 量子比特的状态。经过查询寄存器上阿达玛变换的作用和答案寄存器上阿达玛门的作用，我们得到
$$ \begin{equation*} \left|\psi_{1}\right\rangle=\sum_{x \in{0,1}^{n}} \frac{|x\rangle}{\sqrt{2^{n}}}\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right] \tag{1.47} \end{equation*} $$
查询寄存器是所有值的叠加，而答案寄存器是 0 和 1 的一个平衡叠加。接下来，使用 $U_{f}:|x, y\rangle \rightarrow$ $|x, y \oplus f(x)\rangle$ 计算函数 $f$（由 Bob 计算），得到
$$ \begin{equation*} \left|\psi_{2}\right\rangle=\sum_{x} \frac{(-1)^{f(x)}|x\rangle}{\sqrt{2^{n}}}\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right] \tag{1.48} \end{equation*} $$
Alice 现在拥有一组量子比特，Bob 的计算结果保存在这些量子叠加态的振幅之中。她现在在查询寄存器中利用阿达玛变换来干涉叠加态中的项。为了确定阿达玛变换的结果，可以先计算出阿达玛变换在一个状态 $|x\rangle$ 的效应。分别验证 $x=0$ 和 $x=1$ 的情况，我们知道对于单量子比特 $H|x\rangle=\sum_{z}(-1)^{x z}|z\rangle / \sqrt{2}$ 。因此
$$ \begin{equation*} H^{\otimes n}\left|x_{1}, \cdots, x_{n}\right\rangle=\frac{\sum_{z_{1}, \cdots, z_{n}}(-1)^{x_{1} z_{1}+\cdots+x_{n} z_{n}}\left|z_{1}, \cdots, z_{n}\right\rangle}{\sqrt{2^{n}}} \tag{1.49} \end{equation*} $$
上式还可以总结为更简洁有用的形式
$$ \begin{equation*} H^{\otimes n}|x\rangle=\frac{\sum_{z}(-1)^{x \cdot z}|z\rangle}{\sqrt{2^{n}}} \tag{1.50} \end{equation*} $$
其中 $x \cdot z$ 表示 $x$ 和 $z$ 按位模 2 的内积。利用式（1.48），我们现在计算 $\left|\psi_{3}\right\rangle$ ：
$$ \begin{equation*} \left|\psi_{3}\right\rangle=\sum_{z} \sum_{x} \frac{(-1)^{x \cdot z+f(x)}|z\rangle}{2^{n}}\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right] \tag{1.51} \end{equation*} $$
Alice 现在开始观察查询寄存器。注意到态 $|0\rangle^{\otimes n}$ 的振幅是 $\sum_{x}(-1)^{f(x)} / 2^{n}$ 。让我们考虑两种可能的情况—— $f$ 是常函数和 $f$ 是平衡函数——辨别到底发生了什么。当 $f$ 是常函数时，$|0\rangle^{\otimes n}$ 的振幅是 +1 或 -1 。因为 $\left|\psi_{3}\right\rangle$ 是单位长度，所以其他振幅均为 0 ，而且观测会使得查询寄存器的所有量子比特均为 0 。如果 $f$ 是平衡函数，那么 $|0\rangle^{\otimes n}$ 的振幅正负抵消，最终振幅为 0 ，测量会使得查询寄存器至少有一个量子比特不是 0 。总之，如果 Alice 测量的结果全为 0 ，则函数是常函数；否则函数是平衡函数。Deutsch－Jozsa 算法总结如下。
图 1－20 一般 Deutsch－Jozsa 算法的量子电路实现。类似于工程上的符号，带有／的线表示穿过此线的一组 $n$ 量子比特
输入：（1）黑盒 $U_{f}$ 作用变换 $|x\rangle|y\rangle \rightarrow|x\rangle|y \oplus f(x)\rangle$ ，其中 $x \in\left\{0, \cdots, 2^{n}-1\right\}$ 且 $f(x) \in{0,1}$ 。要求函数 $f(x)$ 对于所有的 $x$ 要么是常函数，要么是平衡函数，也就是说，对于所有可能的 $x$ 恰好一半为 1 另一半为 0 。
输出： 0 当且仅当 $f$ 是常函数。 运行时间：一次 $U_{f}$ 计算。总是成功。
步骤：
| 步骤 | 数学表达式 | 中文解释 |
|---|---|---|
| 1 | $ | 0\rangle^{\otimes n} |
| 2 | $\rightarrow \frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n - 1} | x\rangle \left[\frac{ |
| 3 | $\rightarrow \sum_{x} \frac{(-1)^{f(x)}}{\sqrt{2^n}} | x\rangle \left[\frac{ |
| 4 | $\rightarrow \sum_{z} \sum_{x} \frac{(-1)^{x \cdot z + f(x)}}{2^n} | z\rangle \left[\frac{ |
| 5 | $\rightarrow z$ | 测量得到最终结果$z$ |
我们已经展示了对于 Deutsch 问题，量子计算机仅需计算一次函数 $f$ 就能求解，而经典计算机则需 $2^{n} / 2+1$ 次。这令人印象深刻，但是仍有几点需要注意。第一，Deutsch 问题不是一个非常重要的问题；它尚未找到应用场景。第二，从某种意义上量子算法与经典算法的比较就像比较苹果和橙子，因为它们计算函数的方法很不一样。第三，如果 Alice 允许使用概率经典计算机，那么随机选取几个 $x$ 后询问 $\operatorname{Bob} f(x)$ 能够很快以高概率确定 $f$ 是常函数还是平衡函数。这种概率模型比我们考虑的确定性模型也许更现实。尽管如此，Deutsch－Jozsa 算法仍包含了影响更加深远的量子算法的种子，它对于我们试图理解操作背后的规律具有启发性。 习题1.1（概率经典算法）假定问题不是确定性地区分常函数和平衡函数，而是容许有误差 $\epsilon < 1 / 2$ 。那么该问题的最好经典算法性能如何？
Deutsch－Jozsa 算法暗示在求解某些计算问题上，量子计算机比经典计算机更加有效。但不幸的是，它解决的问题实际意义有限。是否存在能被量子算法求解的更有意义的问题呢？这类算法背后的基本原理是什么？量子计算机的计算极限是什么？
广义上来说，有三类量子算法优于已有的经典算法。第一类是基于傅里叶变换的量子算法，它是广泛运用于经典算法的工具。Deutsch－Jozsa 算法是这类算法的一个例子，Shor 的素因子分解算法和离散对数算法也是如此。第二类算法是量子搜索算法。第三类算法是量子模拟，它利用量子计算机模拟量子系统。下面我们简要描述各类算法，并总结关于量子计算机计算能力的已知或预期的结果。
离散傅里叶变换通常描述为 $N$ 元复数集 $x_{0}, \cdots, x_{N-1}$ 到复数集 $y_{0}, \cdots, y_{N-1}$ 的变换，其中
$$ \begin{equation*} y_{k} \equiv \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} \mathrm{e}^{2 \pi \mathrm{i} j k / N} x_{j} \tag{1.52} \end{equation*} $$
这个变换在许多科学分支中有大量的应用；作用傅里叶变换后的问题常常比原问题更容易解决。傅里叶变换非常有用，事实上傅里叶变换有一套超出式（1.52）的优美理论。这个一般理论涉及源于有限群特征的一些技巧和思想，我们不打算在这里阐述。重要的是，用于 Deutsch－Jozsa 算法的阿达玛变换是一类广义傅里叶变换的特例。此外，许多其他重要量子算法也涉及某种傅里叶变换。
已知的最重要的量子算法——Shor 快速素因子分解算法和离散对数算法，是基于式（1.52）的傅里叶变换的两个例子。式（1.52）的表示并没有呈现量子力学的形式。试想一下，我们在计算基 $|j\rangle$ 上定义 $n$ 量子比特上的线性变换 $U$ ，其中 $0 \leqslant j \leqslant 2^{n}-1$ ：
$$ \begin{equation*} |j\rangle \longrightarrow \frac{1}{\sqrt{2^{n}}} \sum_{k=0}^{2^{n}-1} \mathrm{e}^{2 \pi \mathrm{i} j k / 2^{n}}|k\rangle \tag{1.53} \end{equation*} $$
很容易验证这是一个西变换，并且可以用量子电路实现。此外，如果我们写出它在叠加态上的作用：
$$ \begin{equation*} \sum_{j=0}^{2^{n}-1} x_{j}|j\rangle \longrightarrow \frac{1}{\sqrt{2^{n}}} \sum_{k=0}^{2^{n}-1}\left[\sum_{j=0}^{2^{n}-1} \mathrm{e}^{2 \pi \mathrm{i} j k / 2^{n}} x_{j}\right]|k\rangle=\sum_{k=0}^{2^{n}-1} y_{k}|k\rangle \tag{1.54} \end{equation*} $$
可以看到，当 $N=2^{n}$ 时，它对应傅里叶变换式（1.52）的一种向量形式。 傅里叶变换的作用能有多快？经典世界中，快速傅里叶变换花费大约 $N \log (N)=n 2^{n}$ 个步骤来完成 $N=2^{n}$ 个数的傅里叶变换。在量子计算机上，傅里叶变换可以用大约 $\log {}^{2}(N)=n^{2}$ 个步骤完成，节省的步骤可达到指数量级。它的量子电路将在第 5 章给出。
这个结果似乎说明量子计算机可以非常迅速地计算 $2^{n}$ 个复数向量的傅里叶变换，这在许多应用中有重要的作用。然而，事实并非完全如此；傅里叶变换作用在＂隐含＂于量子态振幅的信息上。这些信息不能通过测量直接得到。问题是，如果输出态被直接测量，那么每个量子比特将会坍缩到 $|0\rangle$ 或 $|1\rangle$ ，使得我们无法直接得到变换后的结果 $y_{k}$ 。这个例子触及了设计量子算法之谜的核心。一方面，我们可以在 $n$ 量子比特对应的 $2^{n}$ 个振幅上进行某项运算，它远远比经典计
算机上的计算快。但是另一方面，直接进行计算的话，我们无法利用这些结果。为了利用量子计算的能力，我们需要更聪明的方法。
幸运的是，已经证明对于某些被认为在经典计算机上无法有效求解的问题，可以利用量子傅里叶变换求解。这些问题包括 Deutsch 问题，以及 Shor 的离散对数和素因子分解算法。Kitaev 发现的阿贝尔（Abel）稳定子问题的一种解决方法和对隐子群问题的推广使这个方向达到了高潮。隐子群问题如下：
令 $f$ 是从有限生成群 $G$ 到有限集 $X$ 的函数，$f$ 在子群 $K$ 的陪集上是常数，且每个陪集的取值不同。给定如下变换的量子黑盒 $U|g\rangle|h\rangle=|g\rangle|h \oplus f(g)\rangle$ ，其中 $g \in G, h \in X$ ，且 $\oplus$ 是在 $X$ 上适当选取的二元运算，找到 $K$ 的一个生成集。
Deutsch－Jozsa 算法，Shor 算法及指数加速的量子算法均可被视为该算法的特殊情况。量子傅里叶变换及其应用将在第 5 章给出。
量子搜索算法是一类全然不同的量子算法，其原理由 Grover 发现。量子搜索算法用于解决下面的问题：给定一个大小为 $N$ 的搜索空间，没有关于其结构的先验知识，我们想要在捜索空间中找到一个满足已知性质的元素。在经典问题中，这个问题需要大约 $N$ 个操作，但是量子搜索算法解决这个问题只需要大约 $\sqrt{N}$ 个操作。
量子搜索算法只有平方量级加速，不如基于量子傅里叶变换的算法的指数加速令人印象深刻。但是量子搜索算法仍然引起了人们极大的兴趣，因为启发式搜索方法的应用范围比使用量子傅里叶变换解决的问题更广泛，并且对量子搜索算法的拓展可能会解决非常广泛的问题。量子搜索算法及其应用将在第 6 章描述。
模拟自然发生的量子系统是量子计算机擅长而经典计算机难以完成的任务。经典计算机难以模拟一般的量子系统的原因和它难以模拟量子计算机是一样的——在经典系统中，描述量子系统需要的复数的个数往往关于系统大小呈指数增长，而不是线性。通常来说，储存一个由 $n$ 个不同部分组成的系统的量子态需要大约 $c^{n}$ 比特的经典计算机内存，其中 $c$ 是依赖于被模拟系统的细节和模拟精度的常数。
相比之下，量子计算机可以用 $k n$ 个量子比特完成模拟，其中 $k$ 仍然是一个关于被模拟系统的细节的常数。这使得量子计算机能够有效地模拟量子力学系统，而经典计算机被认为不能有效地模拟。值得注意的是，尽管量子计算机能比经典计算机更加有效地模拟许多量子系统，但这并不意味着快速模拟能够使我们得到量子系统中所期望得到的信息。在测量以后，一个 $k n$ 个量子比特的模拟将会坍缩到一个确定的态，只留下 $k n$ 比特的信息；在波函数中 $c^{n}$ 比特的＂隐藏信息＂不能全部访问。因此，要使得量子模拟有用的关键步骤是，研究能够有效抽取期望得到的答案的方法；但是如何去完成这件事还没有完全弄清楚。
尽管如此，量子模拟仍将成为量子计算的一个重要应用。量子系统的模拟在许多领域是非常重要的问题，特别是在量子化学中，由于计算能力上的限制，经典计算机很难精确模拟哪怕是中等规模的分子，更不用说在许多重要生物系统中出现的超大分子。因此，对这些系统进行更快更精确的模拟将令人欣喜，使其他量子现象起重要作用的领域取得进展。
在未来我们可能会发现自然界中某种无法用量子计算机模拟的物理现象。这绝不是一个坏消息，简直太棒了！至少，它会激励我们去扩展我们的计算模型来包含新的现象，并且在已有的量子计算模型下进一步提升我们的计算模型的能力。有趣的新物理效应也很可能与这样的现象有关！
量子模拟的另一个作用是作为获取其他量子算法灵感的一般途径；例如，在 6.2 节中，我们将解释量子搜索算法如何被看成一个量子模拟问题的解。通过这种方式可以更加容易地理解量子搜索算法的由来。
最后，量子模拟算法也为摩尔定律提供了一个有趣且乐观的＂量子推论＂。回想一下，摩尔定律指出，在成本不变的情况下，经典计算机的计算能力将大约每两年增加一倍。然而，设想如果我们在经典计算机上模拟量子系统，并且想在模拟过程中再增加一个量子比特（或一个更大的系统）。这将使得经典计算机存储量子系统状态的描述所需的内存需求加倍甚至更多，而模拟动力学需要大致相当或更长的时间。从这一观察得出的摩尔定律的量子推论是，如果能够每两年向量子计算机增加一个量子比特，量子计算机将保持与经典计算机相同的步伐。对于这一推论不必太认真，因为即使量子计算机的计算能力超过经典计算机，到底能有什么收获也尚不清楚。尽管如此，这个启发式的陈述可以帮助说明我们为什么会对量子计算机感兴趣，以及希望终有一天量子计算机至少在某些应用上超过经典计算机。
量子计算机的能力究竞有多强大？是什么赋予它们能力？尽管像素因子分解的例子让人们猜测量子计算机比经典计算机更加强大，但现在没有人能够回答这些问题。在量子计算机上能够高效解决的问题可能在经典计算机上也能有效求解，从这个意义上来说仍然存在量子计算机不比经典计算机更强大的可能性。另一方面，也有可能最终能够证明量子计算机比经典计算机更强大。下面我们将简要总结一下关于量子计算机计算能力的已知事实。
计算复杂性理论（computational complexity theory）是对包括经典世界和量子世界中的不同计算问题进行分类的学科，为了理解量子计算机的计算能力，我们先来考察一些计算复杂性的基本概念。最基本的概念是复杂性类（complexity class）。一个复杂性类可视为一系列计算问题的集合，所有这些问题在求解所需的计算资源上具有相同的性质。
两个最重要的复杂性类分别是 P 和 NP 。粗略地说， P 是在经典计算机中能够快速求解的计算问题的复杂性类。NP 是在经典计算机中能够快速验证解的计算问题的复杂性类。为了理解 $P$和 NP 的区别，考虑求解一个整数 $n$ 的素因子问题。到目前为止还没有在经典计算机上能求解该问题的快速算法，这表明该问题不在 P 中。另一方面，如果别人告诉你 $p$ 是 $n$ 的一个因子，我们能够很快地验证 $n$ 是否能被 $p$ 整除，所以素因子分解在 NP 中。
很显然 P 是 NP 的一个子集，因为能够求解蕴含能够验证潜在的解。现在还不清楚是否有问题存在于 NP 中而不在 P 中。在理论计算机科学领域最重要的未解的问题可能是确定这两个复杂性类是否不同：
$$ \begin{equation*} \mathbf{P} \stackrel{?}{\neq} \mathbf{N P} \tag{1.55} \end{equation*} $$
大多数研究者相信存在在 NP 中但不在 P 中的问题。特别地，在 NP 问题中有一个重要的子类， NP 完全问题（NP－complete）。NP 完全问题特别重要有两个原因。首先，有成千上万的问题，包括一些重要的问题都是 NP 完全问题。其次，任何一个给定的 NP 完全问题在某种意义下至少和其他 NP 问题是＂一样难的＂。更精确地，一个算法如果能够用于求解一个特殊的 NP 完全问题，那么稍微增加一点计算资源就可以被用于求解其他 NP 问题。特别地，如果 $\mathrm{P} \neq \mathrm{NP}$ ，那么在经典计算机上没有 NP 完全问题能够被有效求解。
现在仍然不知道量子计算机是否可以用来快速求解 NP 完全问题，尽管它们可以用于求解一些问题——如素因子分解问题——这个问题被普遍相信在 NP 中而不在 P 中。（注意，素因子分解问题现在还不知道是否是 NP 完全问题，否则我们已经知道如何使用量子计算机高效求解全部 NP 中的问题。）如果量子计算机真的能够高效求解 NP 中的所有问题，那将是非常令人兴奋的。在这一方向上有一个已知的非常有趣的反面结论，它排除了用量子并行性的简单变型来求解所有 NP 问题的可能性。具体来说，求解 NP 问题的一种方法是尝试使用某种形式的量子并行性来搜索该问题的所有可能的解。在 6.6 节我们将看到，这种基于搜索的方法并不能有效地给出所有 NP 问题的解。这一方法的失败令人感到沮丧，但是它并不能排除 NP 问题存在着一些更深层次的结构，使得量子计算机能够快速地将它们全部解决。
P 和 NP 只是人们定义的众多复杂性类中的两个。另外一个重要的复杂性类是 PSPACE。粗略来说，PSPACE 包含那些能用有限空间资源求解的问题（即计算机很＂小＂），但是时间上未必短（＂长＂时间计算是允许的）。PSPACE 被相信是严格要比 P 和 NP 大的，尽管同样也没有被证明。最后，复杂性类 BPP 是如果允许有界的错误概率（例如 $1 / 4$ ），能够用随机算法在多项式时间内求解的问题。BPP 被认为是比 P 更广泛接受的能够在经典计算机上有效解决的问题。这里我们集中在 P 上而不是 BPP 的原因是，我们对于 P 有更深人的研究，尽管在 BPP 中有许多相似的想法和结论。
量子复杂性类会怎样？我们定义 BQP 为能被量子计算机有效求解的计算问题所组成的复杂性类，其中允许有界错误概率。（严格地说，这使得 BQP 更加类似于经典复杂性类 BPP 而不是 P，然而我们暂时忽略这个差别，而将它看成 P 的类似物。）目前还不知道 BQP 与 P，NP 及 PSPACE的准确关系。目前已知的是量子计算机能有效地求解 P 中的问题，但是 PSPACE 以外的问题不能被有效求解。因此，BQP 处在 P 和 PSPACE 中间的某个位置，如图 1－21 所示。一个暗含的重要的结论是，如果证明了量子计算机的计算能力严格强于经典计算机，那么将会得到 P 不等于 PSPACE。有许多计算机科学家尝试过去证明后面的这个结论，但都没有成功，这表明证明量子计算机计算能力强于经典计算机很可能是不平凡的，尽管有许多证据支持这个命题。
现在我们将不再去猜测量子计算的能力极限，而将等到对快速量子算法的基本原理有更好的理解之后再进行讨论，快速量子算法的基本原理是本书第二部分花大量篇幅介绍的主题。现在已经清楚的是，量子计算理论的提出对传统计算概念提出了许多有趣而重要的挑战。这些挑战之所
以重要是因为量子计算的理论模型被认为在实验上是可实现的，因为到目前为止，这个理论与自然界的运行方式相符。若非如此，量子计算将仅仅在数学上令人好奇。
图 1－21 经典与量子复杂性类的关系。量子计算机能够快速求解 P中的问题，并且已经知道它不能很快求解 PSPACE 以外的问题。量子计算机处于 P 和 PSPACE 之间的哪个位置仍不清楚，部分原因是我们甚至不知道 PSPACE 是否大于 P！
量子计算与量子信息是一个奇妙的理论发现，但它的中心概念，例如叠加与纠缠，却与我们从周围的日常世界中获得的直觉相矛盾。我们有什么证据证明这些概念真的描述了大自然的运行规律呢？大规模量子计算是否真的能在实验上实现？或者可能有一些物理定律从根本上禁止了大规模实现？在接下来的两节中，我们将讨论这些问题。我们首先回顾一下著名的＂Stern－Gerlach＂实验，它为自然界中量子比特的存在提供了证据。然后我们扩大范围，解决如何构建实用量子信息处理系统的更广泛问题。
量子比特是量子计算和量子信息的基本元素。我们怎样知道自然界中存在具有量子比特属性的系统？到撰写本文时已有大量证据证明的确如此，但在量子力学的早期阶段，量子比特结构一点也不显然，人们努力理解我们现在以量子比特来解释的现象，即两能级量子系统。
一个决定性的（并且非常著名的）表明量子比特结构的早期实验，是由 Stern 于 1921 年构思并于1922年在法兰克福与 Gerlach一起进行的。在最初的 Stern－Gerlach 实验中，热原子从烤箱中＂射出＂，通过一个导致原子偏转的磁场，然后记录每个原子的位置，如图 1－22 所示。最初的实验是用银原子完成的，银原子具有复杂的结构，因而模糊了我们正在讨论的效果。我们下面描述的实际上是 1927 年使用氢原子完成的实验。在这个实验中，相同的基本效应被观察到，但是对于氢原子的讨论会更加容易。请记住，在 20 世纪 20 年代早期的人们还没有这种技术，他们必须非常聪明才能想出对他们观察到的更为复杂的效应的解释。
氢原子有一个质子和一个环绕的电子。你可以把这个电子想象成质子周围的一点＂电流＂。该电流使原子具有磁场；每个原子都有物理学家所说的＂磁偶极矩＂。其结果是每个原子表现得
像一块小的条形磁铁，其轴线对应于电子旋转的轴。把小磁铁扔过一个磁场会导致磁铁被磁场偏转，我们期望在 Stern－Gerlach 实验中看到类似的原子偏转。
图 1－22 Stern－Gerlach 实验的抽象框图。热的氢原子从炉内出来再经过磁场，引起向上 $(1+Z)$ ）或者向下 $(|-Z\rangle)$ 的偏转
原子如何偏转取决于原子的磁偶极矩——电子旋转的轴——及 Stern－Gerlach 装置产生的磁场。我们不打算也没有必要陷人过多的细节当中，通过适当地构造 Stern－Gerlach 器件，我们可以使原子偏转一定量，该量取决于原子磁偶极矩的 $z$ 分量，其中 $z$ 是一些固定的外轴。
该实验的进行给人类带来了两个主要的惊喜。首先，我们自然地预期离开炉子的热原子的偶极子在每个方向上随机取向，因此应当会出现原子连续分布，看到原子从 Stern－Gerlach 装置的各个角度射出。然而事实上看到的是原子从一组离散的角度出现。物理学家通过假设原子的磁偶极矩是量子化的能够解释这一现象，即，磁偶极矩是一些基本量的离散倍。
Stern－Gerlach 实验中观察到的量子化，对于 20 世纪 20 年代的物理学家来说是令人惊奇的，但并不完全令人震惊，因为在其他系统中，量子化效应正在变得很普遍。真正令人惊讶的是实验中看到的峰值数量。使用的氢原子本应该具有零磁偶极矩。经典理论中这本身就令人惊讶，因为它对应于电子没有轨道运动，但是基于当时对于量子力学的理解，这个观念是可以接受的。由于氢原子因此具有零磁矩，所以预期将只能看到一束原子，这束光不会被磁场偏转。然而事实上观测到了两个光束，一个被磁场向上偏转，而另一个则向下偏转！
通过巨大的努力，这种令人费解的倍增现象可以通过假设氢原子中的电子有一个叫做自旋 （ spin）的量来解释。这个自旋和电子围绕质子的通常旋转运动完全不同。它是与电子相关的一个全新的量。这一观点提出后，伟大的物理学家海森伯（旧译作海森堡）称其＂勇敢＂，因为它向自然界引人了一个全新的物理量。除了由于电子的旋转运动引起的贡献，它还假定电子的自旋对氢原子的磁偶极矩产生额外的贡献。
什么是电子自旋的正确描述？作为第一直觉，我们可能会假设旋转由一个比特描述，指示氢原子上升或下降。进一步的实验结果提供了更多有用的信息，以确定此猜测是否需要改进或替换。让我们用图 1－22 来代表原始的 Stern－Gerlach 设备，它的输出是两束原子束，我们称其为 $|+Z\rangle$ 和 $|-Z\rangle$ 。（我们正在使用看起来和量子力学相似的符号，您当然可以自由使用喜欢的任何符号。）现在假设我们将两个 Stern－Gerlach 设备级联在一起，如图 1－23 所示。我们将它排列成使第二个设备侧向倾斜，因此磁场沿 $\hat{x}$ 轴偏转原子。在我们的思想实验中，我们将阻止来自第一台 Stern－Gerlach 设备的 $|-Z\rangle$ 输出，而 $|+Z\rangle$ 输出发送至沿着 $\hat{x}$ 轴的第二设备。将检测器放置在最终输出处以测量沿 $\hat{x}$ 轴的原子分布。
指向 $+\hat{z}$ 方向的经典磁偶极子在 $x$ 方向上没有净磁矩，因此我们可以预期最终输出将具有一个中心峰值。然而，实验上观察到有两个强度相等的峰值！所以也许这些原子很奇特，独立地沿
着每个轴都有明确的磁矩。也就是说，也许通过第二个设备的每个原子可以被描述为一个态，我们将其写作 $|+Z\rangle|+X\rangle$ 或者 $|+Z\rangle|-X\rangle$ ，来指代可能被观测到的自旋的两个值。
图 1－23 级联的 Stern－Gerlach 测量
另一个实验，如图 1－24 所示，可以通过发送之前的输出通过第二个 $\hat{z}$ 导向的 Stern－Gerlach 设备来测试这个假设。如果这些原子保持了其 $|+Z\rangle$ 方向，那么输出预计只有一个峰值，在 $|+Z\rangle$输出。然而，在最终输出处再次观察到两个强度相等的光束。因此，结论似乎与经典预期相反，一个 $|+Z\rangle$ 态由相等比例的 $|+X\rangle$ 和 $|-X\rangle$ 态组成，一个 $|+X\rangle$ 态由相等比例的 $|+Z\rangle$ 和 $|-Z\rangle$态组成。如果 Stern－Gerlach 设备沿着其他轴对齐，比如 $\hat{y}$ 轴，可以得出类似的结论。
图 1－24 三段级联的 Stern－Gerlach 测量 量子比特模型提供了对这种实验观察到的行为的简单解释。用 $|0\rangle$ 和 $|1\rangle$ 表示量子比特的状态，并且做以下分配
$$ \begin{align*} & |+Z\rangle \leftarrow|0\rangle \tag{1.56}\\ & |-Z\rangle \leftarrow|1\rangle \tag{1.57}\\ & |+X\rangle \leftarrow(|0\rangle+|1\rangle) / \sqrt{2} \tag{1.58}\\ & |-X\rangle \leftarrow(|0\rangle-|1\rangle) / \sqrt{2} \tag{1.59} \end{align*} $$
那么通过假设 $\hat{z}$ Stern－Gerlach 装置在计算基 $|0\rangle,|1\rangle$ 下测量自旋（也就是量子比特），$\hat{x}$ Stern－ Gerlach 装置在基 $(|0\rangle+|1\rangle) / \sqrt{2},|0\rangle-|1\rangle) / \sqrt{2}$ 下测量自旋，可以解释级联的 Stern－Gerlach 实验结果。例如，在级联 $\hat{z}-\hat{x}-\hat{z}$ 实验中，如果我们假设从第一个 Stern－Gerlach 实验射出的自旋处于状态 $|+Z\rangle=|0\rangle=(|+X\rangle+|-X\rangle) / \sqrt{2}$ ，那么第二个装置得到 $|+X\rangle$ 的概率是 $1 / 2$ 。相似地，第三个装置得到 $|+Z\rangle$ 的概率是 $1 / 2$ 。因此，量子比特模型正确预测了这种级联 Stern－Gerlach 实验的结果。
这个例子演示了量子比特在自然界中如何成为一种可信的建模系统的方式。当然，它没有证明量子比特是毫无疑问的理解电子自旋的正确方式——需要更多的实验证据。然而，由于这类实验很多，我们现在相信量子比特是描述电子自旋的最好模型。更进一步，我们相信量子比特模型 （以及它向更高维度的推广；换句话说，量子力学）能够描述每个物理系统。我们现在转向哪些系统特别适合于量子信息处理的问题。
建立量子信息处理设备对第三个千年的科学家和工程师来说是一个巨大的挑战。我们能够迎接挑战吗？有可能实现吗？值得尝试吗？如果值得，这项壮举将如何实现？这些是困难而重要的问题，我们将在本节进行简要回答，并在全书进行延展。
最基本的问题是，是否存在某种原理禁止我们进行一种或多种形式的量子信息处理？可能的障碍有两个：噪声可能对有用的量子信息处理构成根本性障碍；或者量子力学可能是不正确的。
毫无疑问，噪声是实用量子信息处理设备发展的重大障碍。这是一个根本上无法解决的障碍吗？会永远阻碍大规模量子信息处理设备的发展吗？量子纠错码的理论有力地表明，虽然量子噪声是一个需要解决的实际问题，但不存在根本性的原理问题。特别是存在一个量子计算的阈值定理，粗略地说，该定理表明，如果量子计算机中的噪声水平可以降低到某个常数＂阈值＂以下，那么就可以使用量子纠错码来进一步地降低噪声，只需要很小的计算复杂性的开销，基本上可以降低到任意小。阈值定理对量子计算机中出现的噪声的性质和大小，以及可用于执行量子计算的体系结构做了一些广泛的假设；但是，如果这些假设被满足，那么对于量子信息处理噪声的影响基本上可以忽略不计。第 8 章，第 10 章和第 12 章将详细讨论量子噪声，量子纠错和阈值定理。
妨碍量子信息处理的第二种可能性是量子力学是不正确的。实际上，探究量子力学（相对论性和非相对论性）的有效性是对构建量子信息处理设备感兴趣的其中一个原因。我们以前从未探索过在大规模量子系统中获得完全控制的自然体系，也许在这些体系中大自然可能会揭示出一些新的惊喜，而量子力学并没有对此做出充分的解释。如果发生这种情况，它将成为科学史上的一个重大发现，并且有望像量子力学的发现一样在其他学科和技术领域产生重大的影响。这样的发现也可能影响量子计算和量子信息；然而，无论这种影响是否会增强，减弱或不影响量子信息处理的能力，现在都无法提前预测。除非发现了这些影响，否则我们无法知道它们将如何影响信息处理，因此在本书的其余部分我们会考虑迄今为止的所有证据，并假设量子力学是对世界正确和完备的描述。
既然构建量子信息处理设备没有根本性的障碍，为什么我们要投人大量的时间和金钱这样做？我们已经讨论过几个要这样做的原因：实际应用，如量子密码学和大型合数的素因子分解；以及渴望获得对自然和信息处理的基本见解。
这些都是很好的理由，并且证明了在建立量子信息处理设备方面投人大量时间和金钱的合理性。但是平心而论，为了评估它们的相对优点，需要更清楚地了解量子和经典信息处理的相对能力。要想做到这一点，需要在关于量子计算和量子信息基础方面进一步的理论工作。尤其令人感兴趣的是对＂量子计算机比经典计算机更强大吗？＂这一问题的决定性答案。即使我们暂时无法回答这个问题，但在不同的复杂度情况下给出一个明确的有趣应用路径以帮助研究人员实验性地实现量子信息处理，将会是很有用的。从历史上来看，技术的进步往往是通过使用短期和中期激励作为实现长期目标的垫脚石来加速的。比如微处理器，在最终成为个人计算机的基本组件（之前没人知道这是什么）之前，最初用作电梯和其他简单设备的控制器。下面我们为有兴趣实现大规模量子信息处理的长期目标的人们勾画一条中短期目标路径。
令人惊讶的是，许多量子计算和量子信息的小规模应用是已知的。并非所有的都像量子素因
子分解算法一样华丽，但实施小规模应用程序相对容易，使其作为中期目标非常重要。 量子态层析和量子过程层析成像是两个基本过程，其完善性对于量子计算和量子信息非常重要，并且它们自身也有独立的价值。量子态层析是确定系统的量子状态的方法。要做到这一点，它必须克服量子态的＂隐藏＂性质——记住，量子状态不能通过一次测量直接确定——通过重复制备同一个量子态，然后以不同的方式测量，以建立量子态的完整描述。量子过程层析成像是一个更加雄心勃勃的（但是密切相关的）过程，旨在完全表征量子系统的动态学。例如，量子过程层析成像可用于表征所谓的量子门或量子通信信道的性能，或用于确定系统中不同噪声过程的类型和大小。除了在量子计算和量子信息中的明显应用，作为一种诊断工具，对于量子效应重要的科学和技术领域，量子过程层析成像可以预期协助评估和改进任何其中的基本操作。量子态层析和量子过程层析成像在第 8 章中有更详细的描述。
各种小规模通信原语也是非常令人感兴趣的。我们已经提到了量子加密和量子隐形传态。前者可能在实际应用中很有用，它涉及分发少量需要高度安全的关键材料。量子隐形传态的用途也许还有待解决。我们将在第 12 章中看到，在存在噪声的情况下，远距传送对于在网络中的远程节点之间传输量子状态可能是非常有用的原语。其想法是集中精力在希望通信的节点之间分配 EPR 对。通信期间 EPR 对可能会被损坏，但是，特殊的＂纠缠蒸馏＂协议可用于＂纯化＂EPR 对，使其能够用于将量子态从一个位置传送到另一个位置。事实上，基于纠缠蒸馏和远距传送的协议在实现量子比特的无噪声通信方面优于更常规的量子纠错技术。
中等规模能怎么样？一个有前景的中等规模量子信息处理应用是量子系统的模拟。 为了模拟包含甚至只有几十个＂量子比特＂的量子系统（或者等价的一些其他基本系统），即使使用最先进的超级计算机的资源也不够用。一些简单的计算给出了指导性的解释。假设我们有一个包含 50 个量子比特的系统，要描述这种系统的状态需要 $2^{50} \approx 10^{15}$ 个复数振幅。如果振幅存储到 128 位精度，那么它需要 256 位或 32 字节以存储每个振幅，总共 $3210^{15}$ 字节的信息，或者说大约 $32,000 \mathrm{~T}$ 字节的信息，远远超出现有计算机的容量，并且，如果假设摩尔定律一直成立，那么相当于预期在 21 世纪的第二个十年出现的超级计算机的存储容量。在相同精度水平下的 90 个量子比特需要 $32 \times 10^{27}$ 个字节，即使使用单个原子来表示一位，也需要数千克（或更多）的物质。
量子模拟有多大用处？似乎传统方法仍然可用于确定材料的基本性质，例如粘合强度和基本光谱性质。然而，一旦基本属性得到很好的理解，量子模拟作为实验室设计和测试新分子性质的工具很有可能会非常有用。在传统的实验室设置中，可能需要许多不同类型的＂硬件＂——化学品，检测设备等——来测试分子的各种可能的设计。在量子计算机上，这些不同类型的硬件都可以用软件模拟，这可能更便宜，而且速度更快。当然，最终的设计和测试必须在真实的物理系统上进行；然而，量子计算机能探索更大范围的潜在设计，并且评估得到更好的最终设计方案。值得注意的是，这种狭义第一性原理（ab initio）计算来协助设计新分子的方法在经典电脑上尝试过；然而，由于在经典计算机上模拟量子力学所需的巨大计算资源，只取得了有限的成功。量子计算机应该能够在不久的将来做得更好。
大规模的应用有哪些？除了扩展量子模拟和量子密码学等应用，众所周知的大规模应用相对较少：大整数素因子分解，计算离散对数和量子搜索。对前两个问题的兴趣主要来自它们对限制
现有公钥密码系统生命力的负面影响。（对于那些对这两个问题感兴趣的数学家，仅仅出于他们自身的兴趣，它们也可能具有实质性的实际意义。）因此从长远来看，分解素因子和离散对数似乎不太可能一直是重要的应用。由于启发式搜索的广泛应用，量子搜索可能具有巨大的用途，我们将在第 6 章讨论一些可能的应用。真正非凡的可能是量子信息处理的更多大规模应用。这是未来的伟大目标！
假设有量子信息处理的潜在应用途径，如何在真实物理系统中实现？在几个量子比特的小规模上已经有几个关于量子信息处理设备的实现方案。也许最容易实现的是基于光学技术，即电磁辐射。像反射镜和分光镜这样的简单设备可用于对光子进行基本操作。有趣的是，一个主要的困难是按需要产生单光子；实验物理学家改而选择使用一种＂时不时地＂能随机生成单光子的方案，并等待此事件的发生。使用这种光学技术已经实现了量子密码技术，超密编码和量子隐形传态。光学技术的主要优势是光子往往是量子力学信息高度稳定的载体。其主要缺点是光子不直接相互作用。作为替代，相互作用必须由其他介质调节，例如原子，它会为实验引人额外的噪声和复杂性。建立两个光子之间的有效相互作用，本质上分两步工作：第一个光子与原子相互作用，而原子又与第二个光子相互作用，从而导致两个光子之间的整体相互作用。
另一种方案是基于囚禁不同类型原子的方法：包括离子阱，其中少量带电原子被囚禁在受限空间中；以及中性原子阱，用于在受限空间中囚禁不带电荷的原子。基于原子阱的量子信息处理方案使用原子来存储量子比特。电磁辐射也出现在这些方案中，但其方式与我们称为量子信息处理的＂光学＂方法的方式完全不同。在这些方案中，光子用于操纵存储在原子本身中的信息，而不是作为存储信息的载体。单量子比特门可以通过在个别原子上施加适当的电磁辐射脉冲来执行。相邻原子可以通过（例如）偶极子力相互作用来实现量子门。此外，相邻原子间相互作用的确切性质可以通过向原子施加适当的电磁辐射脉冲来修改，使实验者能控制在系统中执行哪种门。最后，量子测量可以通过在这些系统使用已经成熟的量子跳跃技术实现，该技术能以极高的精度实现计算基下的测量。
另一类量子信息处理方案基于核磁共振，通常以其首字母缩写 NMR 为人熟知。这些方案将量子信息存储在分子中原子的核自旋中，并使用电磁辐射操纵该信息。这样的方案带来了特殊的困难，因为在 NMR 中不可能直接操作单个核。相反，大量（通常约 $10^{15}$ 个）本质上相同的分子存储在溶液中。将电磁脉冲施加到样品上，使得每个分子以大致相同的方式响应。您应该将每个分子视为一台独立的计算机，而将样本视为包含大量（经典地）并行计算机。核磁共振量子信息处理面临着三个特殊的困难，这些困难使它与其他量子信息处理方案十分不同。首先，这些分子通常通过使它们在室温下平衡来制备，这比典型的自旋翻转能量高得多，使得自旋几乎完全随机取向。这一事实使得初始状态比量子信息处理所需的更＂嘈杂＂。如何克服这种噪声是我们在第 7章中要讲述的一个有趣的故事。第二个问题是，可以在核磁共振中执行的测量类别远远少于我们希望在量子信息处理中使用的一般测量。不过，对于许多量子信息处理实例，NMR 中允许的测量类别已经足够。第三，因为分子不能在 NMR 中单独处理，您可能会问，如何以适当的方式操纵各个量子比特。幸运的是，分子中的不同核可以具有不同的性质，使它们能够被单独处理——或者至少以足够细粒度的尺度进行处理，以允许量子计算所需要的操作。
执行大规模量子信息处理所需的许多要素都可以在现有方案中找到：精湛的状态准备和量子
测量可以在离子阱中的少量量子比特上实现；极好的动态演化可以用 NMR 在小分子中进行；固态系统中的制造技术可以使设计得以大规模扩展。具有所有这些要素的单个系统将是通向梦想量子计算机的一条漫漫长路。不幸的是，这些系统都非常不同，我们距离拥有大型量子计算机还有很多很多年。但是，我们相信在现有（尽管有所不同）系统中所有这些属性的存在，对于大规模量子信息处理器的存在是个好兆头。此外，它表明推动结合现有技术中两个或更多好的特点的混合设计可能会有优势。例如，在电磁腔内囚禁原子方面已经做了很多工作，这使得能够通过光学技术灵活地在腔内部操纵原子，并且可以以常规原子陷阱中无法实现的方式对单原子进行实时反馈控制。
最后，请注意不要将量子信息处理看作仅仅是另一种信息处理技术。例如，很容易将量子计算视为计算机发展中的另一种技术潮流，就像其他技术潮流一样将随着时间而消逝。例如，＂泡沫内存＂在 20 世纪 80 年代早期被广泛宣传为存储的下一代技术。这是一个错误，因为量子计算是信息处理的一个抽象范式，可能在技术上有许多不同的实现。人们可以比较量子计算的两个不同方案的技术优点——将＂好＂的方案与＂坏＂的方案进行比较是有意义的——无论如何，即使量子计算机的一个非常糟糕的方案，它与精湛设计的经典计算机也具有定性的本质不同。
＂量子信息＂这一术语在量子计算和量子信息领域中有两种不同的使用方式。第一种用法是广义的，它可以理解为与使用量子力学的信息处理相关的所有操作。这种用法包括诸如量子计算，量子隐形传态，不可克隆定理，以及本书中几乎所有其他主题。 ＂量子信息＂的第二种用法更加具体化：它指的是对基本量子信息处理任务的研究。它通常不包括例如量子算法设计，因为特定量子算法的细节超出了＂基本＂的范围。为了避免混淆，我们将使用术语＂量子信息理论＂来指代这个更专业的领域，并行地用广泛使用的术语＂（经典）信息理论＂来描述相应的经典领域。当然，＂量子信息理论＂这个术语有其自身的缺点——它可能被视为在暗示理论上的考虑因素至关重要！事实显然并非如此，对于量子信息理论研究的基本过程的实验验证引起了学者的极大兴趣。
本节的目的是介绍量子信息理论的基本思想。即使将范围限制在基本量子信息处理任务，量子信息理论对初学者来说也可能看起来像一个混乱的动物园，许多明显不相关的主题都属于＂量子信息理论＂。在某种程度上，这是因为该理论仍处于发展阶段，目前尚不清楚所有部分如何统一在一起。但是，我们可以确定一些基本目标来统一这些量子信息理论的工作：
1.确定量子力学中的基本静态资源类。一个例子是量子比特，另一个例子是经典比特；经典物理学是量子物理学的一个特例，因此在经典信息理论中出现的基本静态资源在量子信息理论中具有重要意义也就不足为奇了。另一个基本静态资源类的例子是相距遥远的两方之间共享的贝尔态。
2.确定量子力学中动力学过程的基本类。一个简单的例子是内存，即在一段时间内存储量子态的能力。较不平凡的过程是两方 Alice 和 Bob 之间的量子信息传输；复制（或试图复制）量子态，以及保护量子信息处理免受噪声影响的过程。
3.量化执行基本动态过程所需的资源折表。例如，使用嘈杂的通信信道在两方之间可靠地传输量子信息所需的最小资源是多少？
类似目标定义了经典信息理论；然而，量子信息理论的范围比经典信息理论更广泛，因为量子信息理论包括经典信息理论的所有静态和动态要素，以及额外的静态和动态要素。
本节的其余部分描述了量子信息理论所研究问题的一些例子，在每种情况下都强调了所考虑的基本静态和动态要素，以及相应的资源折衷。我们从一个对经典信息理论家来说非常熟悉的例子开始：通过量子信道发送经典信息的问题。然后我们开始拓展范围，分析并探索量子力学中存在的一些新的静态和动态过程，例如量子纠错，区分量子态的问题，以及纠缠转换。再往后本章总结了一些如何将量子信息理论的工具应用到量子计算和量子信息的思考。
经典信息理论的基本结果是香农的无噪声信道编码定理和有噪声信道编码定理。无噪声信道编码定理量化了存储信息源发出的信息所需的比特数，而有噪声信道编码定理量化了可以通过嘈杂信道可靠传输的信息量。
我们说的信息源是什么？定义这个概念是经典和量子信息理论的基本问题，我们将多次重新审视它。现在，让我们来看一个临时定义：经典信息源由一组概率 $p_{j}, j=1,2, \cdots, d$ 描述。信源每次随机地以概率 $p_{j}$ 产生＂字母＂$j$ ，信源每次使用都相互独立。例如，如果信源是英文文本，则数字 $j$ 可能对应于某个字母或标点符号，概率 $p_{j}$ 对应不同字母在常规英文文本中出现的相对频率。虽然英语中的字母不是以相互独立的方式出现，但就我们的目的而言这将是一个足够好的近似。
常规英文文本包含大量的冗余，可以利用该冗余来压缩文本。例如，字母＂e＂在普通英文文本中的出现频率高于字母＂$z$＂。因此，好的英文文本压缩方案将使用相比于＂$z$＂更少的信息来表示字母＂e＂。香农的无噪声信道编码定理精确地量化了这种压缩方案的工作效果。更确切地说，无噪声信道编码定理告诉我们，由概率 $p_{j}$ 描述的经典信源可以被压缩，以使得平均每次使用信源可用 $H\left(p_{j}\right)$ 位信息来表示，其中 $H\left(p_{j}\right) \equiv-\Sigma_{j} p_{j} \log \left(p_{j}\right)$ 是信源概率分布的函数，称为香农摘。此外，无噪声信道编码定理告诉我们，如果尝试使用比这更少的比特来对信源进行压缩时会导致在信息解压缩时出错的概率很高。（香农无噪声信道编码定理将在第 12 章中更详细讨论。）
香农的无噪声信道编码定理提供了一个很好的例子，满足了前面列出的信息理论的目标。确定了两个静态资源（目标 1 ）：比特和信息源。确定了两阶段动态过程（目标 2 ）：压缩信息源，然后解压缩以恢复信息源。最后通过找到最优数据压缩方案确定消耗资源的量化标准（目标 3 ）。
香农的第二个主要结果，有噪声信道编码定理，量化了可以通过有噪声信道可靠传输的信息量。特别是，假设我们希望通过嘈杂的信道将某些信息源产生的信息传送到另一个位置。这个位置可能是空间中的另一个点，或者是另一个时间点——后者是存在噪声时信息的存储问题。在两种情况下其思想都是使用纠错码对正在产生的信息进行编码，以便可以在信道的另一端纠正由信
道引人的任何噪声。纠错码实现这一目标的方法是在信道发送的信息中引入足够多的冗余，这样即使在某些信息被破坏之后，仍然可以恢复原始消息。例如，假设噪声信道用于传输单个比特，并且信道中的噪声使得为了实现可靠传输，每个比特在通过通道发送之前必须使用两位进行编码。我们说这样的信道具有半比特的容量，因为每次使用该信道可以用于可靠地传送大约一半的信息。香农的有噪声信道编码定理提供了计算任意噪声信道容量的通用过程。
香农的有噪声信道编码定理也实现了我们前面提到的信息理论的三个目标。涉及两种类型的静态资源（目标 1 ），即信息源，以及通过信道发送的比特。涉及三个动态过程（目标 2 ）。主要过程是信道中的噪声。为了对抗这种噪声，我们使用纠错码对状态执行编码和解码的双重过程。对于固定噪声模型，香农的定理告诉我们如果要实现可靠的信息传输，最佳纠错方案必须引人多少冗余（目标 3 ）。
对于无噪声和有噪声的信道编码定理，香农将自己限制在将信息源的输出存储在经典系统中 ——例如比特等。量子信息理论的一个自然问题是，如果存储介质被改变，使用量子态作为介质传输经典信息会发生什么。例如，可能 Alice 希望压缩由信息源产生的一些经典信息，将压缩后的信息发送给 Bob，然后 Bob 将其解压缩。如果用于存储压缩信息的介质是量子态，那么香农的无噪声信道编码定理不能用于确定最佳压缩和解压缩方案。人们可能想知道，例如，使用量子比特是否允许比经典编码更好的压缩率。在第 12 章中我们将研究这一问题，并证明：实际上在无噪声信道中传输信息时，量子比特不会导致所需的通信量有任何显著的节省。
自然地，下一步是研究通过带噪声的量子信道传输经典信息的问题。理想情况下，我们希望得到的是这种信道传输信息时容量的量化结果。但由于几个原因，评估容量是一项非常栜手的工作。量子力学为我们提供了各种各样的噪声模型，因为量子力学发生在连续的空间中，如何应用经典的误差校正技术来对抗这种噪声并不是很显然的事。例如，使用纠缠态来对经典信息进行编码，然后通过噪声信道一次传输一部分，这样会有利吗？或者使用纠缠测量进行解码可能更有利？在第 12 章中，我们将证明 HSW（Holevo－Schumacher－Westmoreland）定理，该定理提供了这种信道容量的下界。实际上，人们普遍认为 HSW 定理提供了对容量的精确评估，尽管这一点尚未完全证明！另外一个问题是，是否可以使用纠缠态编码来提高容量，使其超出 HSW 定理所提供的下限。迄今为止的所有证据表明，这无助于提高容量，但证明或证否这个猜想仍然是量子信息理论中一个令人着迷的悬而未决问题。
当然，经典信息不是量子力学中唯一可用的静态资源。量子态本身是一种自然的静态资源，甚至比经典信息更自然。让我们看一下香农编码定理的不同量子类比，这次涉及量子态的压缩和解压缩。
首先，我们需要定义量子信息源，类似于经典信息源的定义。与经典情况一样，有几种不同的方式来定义，但为了明确起见，让我们做出临时定义，即量子信源由一组概率 $p_{j}$ 和相应的量子态 $\left|\psi_{j}\right\rangle$ 描述。信源的每次使用都以概率 $p_{j}$ 产生状态 $\left|\psi_{j}\right\rangle$ ，信源的每次使用相互独立。
是否有可能压缩这种量子力学信源的输出？考虑单比特量子信源的情况，它以概率 $p$ 输出状态 $|0\rangle$ ，以概率 $1-p$ 输出状态 $|1\rangle$ 。这基本上与发射单个比特的经典源相同，以概率 $p$ 发送 0 ，以
概率 $1-p$ 发送 1 ，因此并不奇怪可以用与经典类似的技术来压缩信息源，即只需要 $H(p, 1-p)$量子比特来存储压缩信息，其中 $H(\cdot)$ 是香农嫡函数。
如果信源以概率 $p$ 产生状态 $|0\rangle$ ，以概率 $1-p$ 产生状态 $(|0\rangle+|1\rangle) / \sqrt{2}$ 会怎么样？经典数据压缩的标准技术将不再适用，因为一般来说我们不可能区分开状态 $|0\rangle$ 和 $(|0\rangle+|1\rangle) / \sqrt{2}$ 。是否仍然可以执行某种类型的压缩操作？
事实证明，即使在这种情况下，仍然可以进行一种压缩。有趣的是，压缩可能不再是无差错的，从某种意义上说信源产生的量子态可能会因压缩——解压缩过程略微失真。但是，我们要求这种失真变化应该非常小，在增大被压缩的信源输出块的极限意义下最终可以忽略不计。为了量化失真，我们为压缩方案引人保真度，它度量由压缩方案引入的平均失真。量子数据压缩的思想是压缩数据应该能以非常好的保真度恢复。保真度可以被视为类似于正确进行解压缩的概率——在增大块长度的极限意义下它应该趋向于无误差的 1 。
Schumacher 的无噪声信道编码定理量化了在以接近 1 的保真度恢复信息源的限制下，进行量子数据压缩所需的资源。在信源以概率 $p_{j}$ 产生正交量子态 $\left|\psi_{j}\right\rangle$ 的情况下，Schumacher 定理退化为，信源可以被压缩但不超过经典极限 $H\left(p_{j}\right)$ 。然而，在更一般的信源产生非正交态的情况下， Schumacher 定理告诉了我们量子信源可以被压缩多少，并且答案不是香农熵 $H\left(p_{j}\right)$ ！取而代之的是一个新的熵量——冯•诺伊曼熵——才是正确的答案。通常，当且仅当状态 $\left|\psi_{j}\right\rangle$ 彼此正交时，冯•诺伊曼熵与香农嫡一致。否则，信源 $\left(p_{j},\left|\psi_{j}\right\rangle\right)$ 的冯•诺伊曼嫡通常严格小于香农熵 $H\left(p_{j}\right)$ 。因此，例如，若信源以概率 $p$ 产生状态 $|0\rangle$ ，以概率 $1-p$ 产生状态 $(|0\rangle+|1\rangle) / \sqrt{2}$ ，那么对它的每次使用都能以少于 $H(p, 1-p)$ 的量子比特来可靠压缩！
这种资源需求下降背后的基本直觉很容易理解。假设以概率 $p$ 发送量子态 $|0\rangle$ ，以概率 $1-p$发送 $(|0\rangle+|1\rangle) / \sqrt{2}$ 的信息源被使用了 $n$ 次，其中 $n$ 是一个很大的数。那么由大数定理，信源会以高概率发送 $n p$ 份 $|0\rangle$ 和 $n(1-p)$ 份 $(|0\rangle+|1\rangle) / \sqrt{2}$ 。也就是，在重新将系统排序的意义下，它有如下形式
$$ \begin{equation*} |0\rangle^{\otimes n p}\left(\frac{|0\rangle+|1\rangle}{\sqrt{2}}\right)^{\otimes n(1-p)} \tag{1.60} \end{equation*} $$
假设我们将右侧的 $|0\rangle+|1\rangle$ 展开，因为 $n(1-p)$ 很大，我们可以用大数定理来推断乘积中的项大约一半是 $|0\rangle$ ，一半是 $|1\rangle$ 。也就是，$|0\rangle+|1\rangle$ 的乘积项可以用如下形式的状态的叠加来很好地近似：
$$ \begin{equation*} |0\rangle^{\otimes n(1-p) / 2}|1\rangle^{\otimes n(1-p) / 2} \tag{1.61} \end{equation*} $$
因此，信源发送的态可以由以下形式的态的叠加来估计
$$ \begin{equation*} |0\rangle^{\otimes n(1+p) / 2}|1\rangle^{\otimes n(1-p) / 2} \tag{1.62} \end{equation*} $$
这种形式的态一共有多少个呢？大致是从 $n$ 个数中选取 $n(1+p) / 2$ 个的组合数，根据斯特林公式可以被近似为 $N \equiv 2^{n H[(1+p) / 2,(1-p) / 2]}$ 。然后一个简单的压缩方法是将式（1.62）的所有态标记为 $\left|c_{1}\right\rangle$ 至 $\left|c_{N}\right\rangle$ 。因为 $j$ 是一个 $n H[(1+p) / 2,(1-p) / 2]$ 比特的数，我们可以执行一个在信源发出的 $n$ 量子比特上的西变换，将 $\left|c_{j}\right\rangle$ 映射到 $|j\rangle|0\rangle^{n-n H[(1+p) / 2,(1-p) / 2]}$ 。压缩过程是执行这个西变换，
然后将最后 $n-n H[(1+p) / 2,(1-p) / 2]$ 个量子比特丢弃，剩下 $n H[(1+p) / 2,(1-p) / 2]$ 量子比特的压缩态。为了解压缩，我们在压缩态末尾添上 $|0\rangle^{n-n H[(1+p) / 2,(1-p) / 2]}$ ，然后执行西变换的逆。
这一量子数据的压缩和解压缩过程每次使用信源需要 $H[(1+p) / 2,(1-p) / 2]$ 量子比特的存储，当 $p \geqslant 1 / 3$ 时它是简单依据香农无噪声信道编码定理所预期的 $H(p, 1-p)$ 量子比特的一个改进。事实上，正如我们将在第 12 章中看到的那样，Schumacher 的无噪声信道编码定理使我们能够做得更好。然而，此构造的根本原因和我们在这里做的压缩一样：我们利用了 $|0\rangle$ 和 $(|0\rangle+|1\rangle) / \sqrt{2}$不正交的事实。直觉上，这些状态包含一些冗余，因为它们都在 $|0\rangle$ 方向有分量，这导致它们比正交状态有更多的物理相似性。我们在刚才描述的编码方案中利用了这种冗余性，它也被用在 Schumacher 无噪声信道编码定理的完整证明中。请注意，需要要求 $p \geqslant 1 / 3$ 是因为当 $p < 1 / 3$ 时，这个特定的方案不会利用到状态中的冗余：我们最终有效地增加了问题中存在的冗余！当然，这是我们所选择的特定方案的结果，通用方案将以一种更为巧妙的方式利用冗余来实现数据压缩。
Schumacher 的无噪声信道编码定理相当于量子态的压缩和解压缩领域的香农无噪声信道编码定理。我们能找到香农有噪声信道编码定理的对应吗？利用量子纠错码理论，关于这一重要问题的研究已经取得了相当大的进展；然而，尚未找到完全令人满意的类似定理。我们将在第 12章中回顾一些关于量子信道容量的知识。
到目前为止，我们所考虑的所有动态过程——压缩，解压缩，噪声，纠错码的编码与解码 ——在经典和量子信息理论中都出现过。然而，诸如量子态之类的新类型信息的引入扩大了动态过程的范畴，它超出了经典信息理论所考虑的范围。一个很好的例子是量子态区分问题。经典信息理论里，我们习惯于能够区分不同的信息项，至少在原则上是这样。当然在实际中，页面上写的字母＂a＂可能很难与字母＂ o ＂区分开来，但原则上可以完全确定地区分这两种可能性。
另一方面，量子力学并不总是可以区分任意状态。例如，量子力学不允许任何过程可靠地区分状态 $|0\rangle$ 和 $(|0\rangle+|1\rangle) / \sqrt{2}$ 。严格证明这一点需要我们目前没有的工具（在第 2 章中），但通过考虑示例，很容易说明这是不可能的。例如，假设我们试图通过在计算基上进行测量来区分这两种状态。然后，如果给的是状态 $|0\rangle$ ，则测量将以概率 1 产生 0 。然而，当我们测量 $(|0\rangle+|1\rangle) / \sqrt{2}$时，会以概率 $1 / 2$ 产生 0 ，并以概率 $1 / 2$ 产生 1 。因此，虽然测量结果为 1 意味着状态必须是 $(|0\rangle+|1\rangle) / \sqrt{2}$ ，因为它不可能是 $|0\rangle$ 。但我们无法从测量结果为 0 推断出有关量子态身份的任何信息。
这种非正交量子态的不可区分性是量子计算和量子信息的核心。它是我们断言的本质，即量子态包含无法通过测量获得的隐藏信息，因此这些信息在量子算法和量子密码学中起着关键作用。量子信息理论的核心问题之一是发展度量来量化非正交量子态的可区分度，第 9 章和第 12章的大部分内容都与此目标有关。在本节介绍中我们将局限于指出有关不可区分的两个有趣方面 ——与超光速通信的可能性的联系，以及在＂量子货币＂中的应用。
想象一下，假如我们可以区分任意量子态，我们将证明这意味着使用纠缠能够比光速更快地进行通信。假设 Alice 和 Bob 共享两个量子比特，这两个量子比特处于状态 $(|00\rangle+|11\rangle) / \sqrt{2}$ 。然
后，如果 Alice 在计算基上测量，则测量后状态将以概率 $1 / 2$ 处于 $|00\rangle$ ，以概率 $1 / 2$ 处于 $|11\rangle$ 。因此，Bob 的系统以概率 $1 / 2$ 处于状态 $|0\rangle$ ，以概率 $1 / 2$ 处于状态 $|1\rangle$ 。但是，假设 Alice 是用 $|+\rangle,|-\rangle$基进行测量。回想一下 $|0\rangle=(|+\rangle+|-\rangle) / \sqrt{2},|1\rangle=(|+\rangle-|-\rangle) / \sqrt{2}$ 。简单的代数运算表明，Alice和 Bob 系统的初始状态可以改写为 $(|++\rangle+|--\rangle) / \sqrt{2}$ 。如果 Alice 在 $|+\rangle,|-\rangle$ 基下测量，那么测量后 Bob 的系统状态将分别以 $1 / 2$ 概率处于 $|+\rangle,|-\rangle$ 。到目前为止，这都在基本量子力学范围内。但是，如果 Bob 有一台设备能将这 4 个状态 $|0\rangle,|1\rangle,|+\rangle,|-\rangle$ 相互区分，那么他就可以判断出 Alice 是在计算基上进行的测量，还是在 $|+\rangle,|-\rangle$ 上进行测量。而且，只要 Alice 进行了测量，他就可以立即获得该信息，从而提供了一种手段使得 Alice 和 Bob 能实现超光速通信！当然，我们知道不可能区分非正交量子态；这个例子表明这种限制也与我们期望世界服从的其他物理性质密切相关。
非正交量子态的不可区分性并不总是障碍，有时它可能是一种福音。想象一下，银行印制带有（经典）序列号以及处于状态 $|0\rangle$ 或 $(|0\rangle+|1\rangle) / \sqrt{2}$ 的量子比特序列的钞票。除了银行，没有人知道嵌人的这两种状态的顺序是什么，而银行维护着一个将序列号与状态相匹配的列表。该钞票不可能精确伪造，因为一个想要伪造的人不可能确定地得到其中的量子比特状态，而不破坏它们。当使用该钞票时，商家（或认证者）可以通过致电银行来核实它不是伪造品，商家告诉银行序列号，然后询问钞票中嵌人的量子状态序列。然后他们可以按照银行的提示，通过在 $|0\rangle,|1\rangle$ 基或 $(|0\rangle+|1\rangle) / \sqrt{2},(|0\rangle-|1\rangle) / \sqrt{2}$ 基上测量来验证真伪。在这一阶段任何伪造者都将以随被检查的量子比特数目指数速度增加到 1 的概率被检测出！这个想法是许多其他量子密码协议的基础，它表明了非正交量子态不可区分性的实用性。
习题1.2 解释如何利用一个能正确区分非正交量子态 $|\psi\rangle$ 和 $|\varphi\rangle$ 的设备，来构造能克隆量子态 $|\psi\rangle$ 和 $|\varphi\rangle$ 的设备，从而违背不可克隆定理。相应地，解释如何利用一个克隆设备来区分非正交量子态。
纠缠是量子力学的另一个基本静态资源。它的属性与经典信息理论中最熟悉的资源有着惊人的不同，这些属性还没有得到很好的理解；充其量我们只有与纠缠有关的结果的不完整拼图。虽然我们现在还没有要理解这些结果所需的所有语言，但至少让我们来看两个与纠缠有关的信息理论问题。
产生纠缠是量子信息理论感兴趣的一个简单动力学过程。如果两方要创建一个在他们之间共享的特定纠缠态，假设它们之前没有共享纠缠，那么双方必须交换多少量子比特？第二个有趣的动态过程是将纠缠从一种形态转化为另一种形态。例如，假设 Alice 和 Bob 之间共享了一个贝尔态，他们希望将其转换为其他类型的纠缠状态。他们需要什么资源才能完成这项任务？他们可以不通信吗？或者只需要经典通信？如果需要量子通信，那么需要多少量子通信呢？
回答关于纠缠的创建和转化的这些及更复杂的问题本身就构成了一个迷人的研究领域，而且它们有望给诸如量子计算等任务提供新的见解。例如，分布式量子计算可以简单地视为用于在两方或更多方之间产生纠缠的方法；实现这样的分布式量子计算的通信量的下界也是实现相应的纠缠态所需的通信量的下界。
我们已经看到量子信息理论最硬核的部分，虽然是一小部分。本书的第三部分更详细地讨论了量子信息理论，特别是第 11 章和第 12 章，第 11 章涉及量子和经典信息理论中摘的基本性质，第 12 章则侧重于纯量子信息理论。
量子信息理论是量子计算和量子信息中最抽象的部分，但在某种意义上它也是最基本的部分。推动量子信息论并最终推动所有量子计算和量子信息发展的问题是，是什么使量子信息处理成为可能？是什么分离了量子世界与经典世界？量子计算中正在利用哪些经典世界中无法获得的资源？这些问题的现有答案是模糊和不完整的；我们希望在未来几年中迷雾会消散，从而能够对量子信息处理的可能性和局限性有一个清晰的认识。
问题1.1（费曼－盖茨谈话）设想一段比尔•盖茨与理查德•费曼之间关于未来计算技术的约 2000 字的虚构的友好讨论。（注释：你可能想在阅读完本书的剩余部分之后再来回答这个问题。请参阅下面的＂背景资料与延伸阅读＂，以获取对于这个问题的一种可能答案的指引。）
问题1.2 量子计算和量子信息中最重要的发现是什么？为一位受过良好教育的非专业读者撰写一篇关于该发现的约 2000 字的文章。（注释：如上一个问题一样，您可能想等到阅读完本书的其余部分之后再尝试回答这个问题。）
本章的大部分内容将在后面的章节中进行更深入的讨论。因此，下列背景资料和延伸读物仅限于后面章节中不再出现的部分。
将量子计算和量子信息的发展历史整合在一起需要对许多领域的历史进行广泛的概述。我们试图在本章中将这段历史联系在一起，但由于篇幅和专业知识有限，不可避免地会遗漏很多文献资料。以下建议将试图弥补这一遗漏。
量子力学的历史在很多地方都被讲述过。我们特别推荐 Pais ${ }^{[P a i 82, ~ P a i 86, ~ P a i 91] ~}$ 的优秀著作。在这三部著作中，［Pai86］最直接关注量子力学的发展；然而，Pais 关于爱因斯坦 ${ }^{[P a i 82]}$ 和玻尔 ${ }^{[P a i 91]}$ 的传记也包含了很多有趣的材料，虽然程度没那么深。Milburn ${ }^{[M i 197, ~ M i l 98] ~}$ 描述了基于量子力学的技术的兴起。图灵关于计算机科学基础的精彩论文 ${ }^{[T u r 36]}$ 非常值得一读，它可以在 Davis ${ }^{[D a v 65]}$ 的珍贵历史收藏中找到。Hofstadter ${ }^{[H o f 79]}$ 和 Penrose ${ }^{[P e n 89]}$ 包含有关计算机科学基础的有趣且内容丰富的讨论。Shasha 和 Lazere 的关于 15 位计算机科学家的传记 ${ }^{[S L 98]}$ 对计算机科学史的许多不同方面给予了相当深人的介绍。最后，高德纳一系列令人惊叹的著作 ${ }^{[K n u 97, ~ K n u 98 a, ~ K n u 98 b] ~}$ 包含了大量的历史信息。香农创立信息论的精彩论文 ${ }^{[S h a 48]}$ 是极好的阅读材料（也在［SW49］中重印）。MacWilliams和 Sloane ${ }^{[\mathrm{MS} 77]}$ 不仅是介绍纠错码的优秀教材，而且还包含大量有用的历史信息。同样，Cover 和 Thomas ${ }^{[C T 91]}$ 是一本关于信息论的优秀教材，且具有广泛的历史信息。香农的作品集，以及许多有用的历史资料收录在 Sloane 和 Wyner 编辑的图书 ${ }^{[S W 93]}$ 中。Slepian 还收集了一套有用的信息论重印本 ${ }^{[S l e 74]}$ 。密码学是一门古老的艺术，具有错综复杂且往往有趣的历史。Kahn ${ }^{[K a h 96]}$ 是一个包
含丰富信息的密码学史。对于最近的发展，我们推荐 Menezes，van Oorschot 和 Vanstone ${ }^{[\mathrm{MvOV} 96]}$ ， Schneier ${ }^{[S c h 96 a]}$ 以及 Diffie 和 Landau ${ }^{[D L 98]}$ 的书。
量子隐形传态由 Bennett，Brassard，Crepeau，Jozsa，Peres和Wootters $\left.{ }^{[B B C}{ }^{+} 93\right]$ 发现，后来通过各种不同形式的实验实现，包括 Boschi，Branca，De Martini，Hardy和Popescu $\left.{ }^{[B B M}{ }^{+} 98\right]$ 使用光学技术， Bouwmeester，Pan，Mattle，Eibl，Weinfurter和Zeilinger $\left.{ }^{[B P M}{ }^{+} 97\right]$ 使用光子极化，Furusawa，Sørensen， Braunstein，Fuchs，Kimble 和 Polzik 使用光的＂挤压＂态 ${ }^{\left[\mathrm{FSB}^{+} 98\right]}$ ，Nielsen，Knill 和 Laflamme 使用 $N M R^{[N K L 98]}$ 。
Deutsch 问题由 Deutsch ${ }^{[\mathrm{Deu} 85]}$ 提出，并在同一篇论文中给出了一比特的解决方案。 $n$ 比特情况的扩展由 Deutsch 和 Jozsa ${ }^{[\text {DJ92 }] ~}$ 给出。这些早期论文中的算法随后由 Cleve，Ekert，Macchiavello和 Mosca ${ }^{[C E M M 98]}$ 进行了大幅改进，Tapp 在未发表的工作中也独立给出了这个结果。在本章中，我们给出了算法的改进版本，它非常适合于在第 5 章中讨论的隐藏子群问题框架。Deutsch 的原始算法仅以一定概率成功；Deutsch 和 Jozsa 对此进行改进以获得确定性算法，但是与本章介绍的改进算法相比，他们的方法需要两次函数计算。尽管如此，通常我们仍将这些算法称为 Deutsch算法和 Deutsch－Jozsa 算法，用来纪念这两个巨大的飞跃：Deutsch 确凿地表明量子计算机可以比传统计算机更快地完成某些任务；以及 Deutsch 和 Jozsa 的扩展首次表明了解决问题所需的时间规模上的类似差距。
关于 Stern－Gerlach 实验的精彩讨论可以在标准量子力学教科书中找到，如 Sakurai ${ }^{[S a k 95]}$ ，费曼，Leighton 和 Sands 的第三卷［FLS65a］，以及 Cohen－Tannoudji，Diu 和 Laloe ${ }^{[C T D L 77 a, ~ C T D L 77 b] ~}$ 的书。问题1.1是由 Rahim 在论文 ${ }^{[R a h 99]}$ 中提出的。