量子计算(一)——前置知识

量子计算（一）——前置知识

通过这篇文章，我们希望读者对量子计算能有一个初步的了解。而量子信息的表示与经典世界中的不同，因此我们会首先用经典的情形介绍概率模型，而后逐步过渡到量子的情形。

一、在经典情况下的概率模型

简便起见，我们首先对一个位(比特, Bit)进行研究。一个位只有两种可能的状态(State)，数学上将其记为一个集合 $Σ = {0, 1}$ 。为了与之后的量子情形区别，通常将这里的状态具体称为经典状态(Classical State)。

假设一个我们事先不知道具体处于哪个状态的位，不妨将其记为 $𝑏$ ，那么可以以概率(Probability)来描述它。由于一个位只可能处于两种状态中的一种，所以可以用一个具有两个元素的向量来描述：

𝑣 = [\begin{matrix} 𝑝_{0} \\ 𝑝_{1} \end{matrix}]

这个向量称为概率向量(Probability Vector)。其中， $𝑝_{0}$ 是 $𝑏 = 0$ 的概率， $𝑝_{1}$ 是 $𝑏 = 1$ 的概率。这隐含了两个信息：由于概率必定非负，因此 $𝑝_{0} \geq 0$ 且 $𝑝_{1} \geq 0$ ；同时由于概率之和必为 $1$ ，显然 $𝑝_{0} + 𝑝_{1} = 1$ 应当恒成立。

但在观察 $𝑏$ 之后， $𝑏$ 处于哪个状态就被确定了。这时候概率向量就会落入确定的状态，即：

𝑣 = [\begin{matrix} 𝑝_{0} \\ 𝑝_{1} \end{matrix}] ⟶ 𝑤 = [\begin{matrix} 0 \\ 1 \end{matrix}] or 𝑤 = [\begin{matrix} 1 \\ 0 \end{matrix}]

观察——事实上常常称为测量(Measurement)——是一种改变概率向量的方法，而操作(Operation)亦是一种。操作可以用一个矩阵来描述，操作一个概率向量就是用操作矩阵左乘这个向量。例如，一个执行非操作的矩阵是：

NOT = [\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}]

对一个概率向量执行非操作就是：

[\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}] \cdot [\begin{matrix} 𝑝_{0} \\ 𝑝_{1} \end{matrix}] = [\begin{matrix} 𝑝_{1} \\ 𝑝_{0} \end{matrix}]

描述操作的矩阵总是一个方阵，它的阶会取决于概率向量的元素个数，也即取决于取值集合 $Σ$ 的元素个数。只是在一般情况下，我们的研究对象总是基于位，使得 $Σ$ 总只有 ${0, 1}$ 的取值。

在经典情况下，描述操作的矩阵被称为随机矩阵(Stochastic Matrix)，这个矩阵的特性是：它的列向量都是概率向量——同时也说明其元素都是非负实数。这个特性将它与量子情况下的操作矩阵区分开来。

二、张量积(Tensor product)与狄拉克符号(Dirac Notation)

由上所述，在取值集合 $Σ = {0, 1}$ 下，一个位可以用具有两个元素(概率)的概率向量描述。但如果有两个位呢？例如有下述两个分立的位，分别有概率向量：

𝑣_{1} = [\begin{matrix} 𝑝_{10} \\ 𝑝_{11} \end{matrix}], 𝑣_{2} = [\begin{matrix} 𝑝_{20} \\ 𝑝_{21} \end{matrix}]

那么其整体的概率向量又如何？这将会是一个具有 $2^{2} = 4$ 个元素的向量。我们规定，概率向量的行号总从 $0$ 开始记，每往后一行递增 $1$ ，那么某行的元素就代表取值为这一行的行数的二进制码的概率。显然这个例子对应概率向量：

𝑣 = [\begin{matrix} 𝑝_{10} 𝑝_{20} \\ 𝑝_{10} 𝑝_{21} \\ 𝑝_{11} 𝑝_{20} \\ 𝑝_{11} 𝑝_{21} \end{matrix}] \begin{matrix} \leftarrow probability of 00 \\ \leftarrow probability of 01 \\ \leftarrow probability of 10 \\ \leftarrow probability of 11 \end{matrix}

这个向量的生成可以用张量积(Tensor Product)来表示。张量积像下述这样简单地计算：

定义 1.（张量积(Kronecker积)）

若有分别是 $𝑛 \times 𝑚$ 和 $𝑝 \times 𝑞$ 的矩阵 $𝐴, 𝐵$ ，其中 $𝐴$ 是：

𝐴 = [\begin{matrix} 𝑎_{11} & 𝑎_{12} & \dots & 𝑎_{1 𝑚} \\ 𝑎_{21} & 𝑎_{22} & \dots & 𝑎_{2 𝑚} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 𝑎_{𝑛 1} & 𝑎_{𝑛 2} & \dots & 𝑎_{𝑛 𝑚} \end{matrix}]

那么 $𝐴$ 与 $𝐵$ 的张量积 $𝐴 \otimes 𝐵$ 是一个 $𝑛 𝑝 \times 𝑚 𝑞$ 的矩阵：

𝐴 \otimes 𝐵 = [\begin{matrix} 𝑎_{11} 𝐵 & 𝑎_{12} 𝐵 & \dots & 𝑎_{1 𝑚} 𝐵 \\ 𝑎_{21} 𝐵 & 𝑎_{22} 𝐵 & \dots & 𝑎_{2 𝑚} 𝐵 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 𝑎_{𝑛 1} 𝐵 & 𝑎_{𝑛 2} 𝐵 & \dots & 𝑎_{𝑛 𝑚} 𝐵 \end{matrix}]

可以发现这种运算对两个矩阵的行数列数是没有特殊要求的。张量积具有很多优秀的性质。除交换律不成立即 $𝐴 \otimes 𝐵 \neq 𝐵 \otimes 𝐴$ 外，它符合下列运算：

命题 1.（张量积的性质）

\begin{aligned} (𝐴 \otimes 𝐵) \otimes 𝐶 & = 𝐴 \otimes (𝐵 \otimes 𝐶) \\ (𝐴 \otimes 𝐵) (𝐶 \otimes 𝐷) & = (𝐴 𝐶) \otimes (𝐵 𝐷) \\ 𝐴 \otimes (𝐵 + 𝐶) & = 𝐴 \otimes 𝐵 + 𝐴 \otimes 𝐶 \\ (𝐴 + 𝐵) \otimes 𝐶 & = 𝐴 \otimes 𝐶 + 𝐵 \otimes 𝐶 \\ (𝛼 𝐴) \otimes 𝐵 & = 𝐴 \otimes (𝛼 𝐵) = 𝛼 (𝐴 \otimes 𝐵) \end{aligned}

因此对于上述例中的二位概率向量有 $𝑣 = 𝑣_{1} \otimes 𝑣_{2}$ 。但是，张量积输出的矩阵体积会随着 $𝐵$ 的大小成倍增长，这给手写手算带来极大不便。为此引入狄拉克符号(Dirac Notation)。我们发现，对于一个位，在测量后必定会坍塌为两种对立确定的状态，即：

[\begin{matrix} 1 \\ 0 \end{matrix}] or [\begin{matrix} 0 \\ 1 \end{matrix}]

若是两个位，必然会坍塌为四种对立确定的状态，即：

[\begin{matrix} 1 \\ 0 \\ 0 \\ 0 \end{matrix}] or [\begin{matrix} 0 \\ 1 \\ 0 \\ 0 \end{matrix}] or [\begin{matrix} 0 \\ 0 \\ 1 \\ 0 \end{matrix}] or [\begin{matrix} 0 \\ 0 \\ 0 \\ 1 \end{matrix}]

从而发现规律：测量对象有 $𝑛$ 个位，概率向量中就有 $2^{𝑛}$ 个元素，被测量后就会落入 $2^{𝑛}$ 种对立确定的状态，每一种对立确定的状态中只有一个元素为 $1$ 、其余为 $0$ 。在只有一位的情况下，定义：

| 0 ⟩ = [\begin{matrix} 1 \\ 0 \end{matrix}], | 1 ⟩ = [\begin{matrix} 0 \\ 1 \end{matrix}]

并且，再做简记 $| 𝑎 ⟩ \otimes | 𝑏 ⟩ = | 𝑎 ⟩ | 𝑏 ⟩$ ，若 $𝑎, 𝑏 \in {0, 1}$ 还能进一步简记为 $| 𝑎 𝑏 ⟩$ 。这样上述的二位四种对立确定状态能分别用狄拉克符号表示为 $| 00 ⟩, | 01 ⟩, | 10 ⟩, | 11 ⟩$ 。因此在狄拉克符号中，有几位数字就说明测试对象是几位的，其中的二进制码指明了是第几行(从 $0$ 开始！)的元素为 $1$ 。这样，一开始给出的一位概率向量：

𝑣 = [\begin{matrix} 𝑝_{0} \\ 𝑝_{1} \end{matrix}]

就能简单方便地表示为 $𝑣 = 𝑝_{0} | 0 ⟩ + 𝑝_{1} | 1 ⟩$ 。

注 1.

事实上狄拉克符号应用在经典情况下并不太适合，但是我们需要提前引入这种记号来辅助推进接下来对量子情况下的说明。

三、量子力学基础

为了更清楚地说明量子位(Qubit)的概念，我们引入一些量子力学的内容。首先会说明态叠加原理，而这是量子算法得以成立的物理基础，是量子位与经典位的本质区别。之后说明狄拉克符号、即态矢的概念，这是我们描述量子算法的数学基础。

1.态叠加原理

在经典光电学中，我们将偏振现象归结于光的波动性。由波的性质可以推导出我们熟悉的马吕斯定律，即如果一束线偏振光的振幅为 $𝐴_{0}$ 、光强为 $𝐼_{0}$ ，而其偏振方向与偏振片的透振方向的夹角是 $𝛼$ ，那么穿过偏振片后振幅将变为 $𝐴_{0} cos (𝛼)$ 、光强变为 $𝐼_{0} {cos}^{2} (𝛼)$ 。

然而实验指出，不同方向的偏振光激发的光电子的方向亦有偏向性，这说明偏振现象与光粒子也具有紧密的联系。因此我们也能将一束线偏振光看做由一群按相同方向偏振的光子所组成，并称这些光子处于偏振态。现在考虑多束只含单个光子的光分别通过偏振片的实验。在两种简单的情形下：当光子的偏振方向与透振方向相同时，我们总能在偏振片后得到这些光子；当两个方向垂直时，则会完全无法得到光子。

而当光子的偏振方向与透振方向具有夹角 $𝛼$ 时，事情就变得有趣了起来。在偏振片后，我们有时能够得到与入射光子能量完全相同的光子、并且偏振方向与透振方向相同，而有时则得不到光子——仅此两种情况。但统计发现，偏振片后能得到光子的概率差不多正是 ${cos}^{2} (𝛼)$ ，这正好对应马吕斯定律中光强的透射率！

这个结果自然并非巧合。从实验结果出发，我们有理由认为：单个光子的偏振态可以表示为与透振方向平行和垂直的两个偏振态的叠加。这便是态叠加原理的一种简单体现。通过偏振片这一行为，其本质是与光子发生了相互作用，而这种产生作用的过程则称为观察或者测量，它使得光子由这种部分偏振态的叠加落入到确定的偏振态。 ¹¹ 从上面这段您应当注意到：观察或者测量并不一定由人引发，亦可能来源于仪器。而偏振态的分解，却是由偏振片的透振方向决定的——也就是说，即便对于同一个光子，它也有无数种可能的偏振态叠加方法，但参与叠加的偏振态双方之间的偏振方向应当是垂直的。

2.态矢

接下来我们用数学语言来描述态叠加原理。还是继续刚才的例子，不妨将两个偏振态分别记为 $| ∥ ⟩, | ⟂ ⟩$ ，也就是偏振方向与透振方向平行的偏振态、以及垂直的偏振态。那么使用之前的经典概率模型，可以将光子表示为：

{cos}^{2} (𝛼) | ∥ ⟩ + {sin}^{2} (𝛼) | ⟂ ⟩

但这个表示是从结果出发的，一开始并不一定知道平行与垂直偏振态出现的概率，在物理学中我们不喜欢这种突兀的写法。事实上，像经典光电学那样，将振幅分解到平行与垂直方向上会是更加自然的选择，这时光子的偏振态则表示为：

cos (𝛼) | ∥ ⟩ + sin (𝛼) | ⟂ ⟩

应当注意，原光子的振幅大小是被包括在 $| \begin{matrix} \end{matrix} ⟩$ 符号中的，因此不会显式地将其写出。 $cos (𝛼), sin (𝛼)$ 分别称为态 $| ∥ ⟩, | ⟂ ⟩$ 的振幅。 ²² 注意态的振幅与光子的振幅有联系但亦有区别，但在这个线偏振光子的例子中，它们确实只是相差一个系数的关系。注意到相应偏振态出现的概率，就是其振幅的平方，而这个规律则是普适性的。因此，态的振幅一般更正式地称为概率幅。今后我们说量子的振幅时，指的就是概率幅。 ³³ 在量子力学中，概率幅是复数，不一定只取实数。这是因为诸如不确定性原理与干涉现象等，只有用复数才能表示与解释清楚。因此，要从概率幅计算出概率并非简单地平方即可，而是取其模之后再平方。

从引入概率幅开始，我们已经从经典情形过渡到量子情形中了。上述提到的狄拉克符号，即 $| \begin{matrix} \end{matrix} ⟩$ / $⟨ \begin{matrix} \end{matrix} |$ 记号，更具体的名称是右矢(Ket)。与之对应的是左矢(Bra)，两者都可称作态矢(State Vector)。左矢都是行向量，右矢都是列向量，它们之间的关系是： ⁴⁴ 若有一个矩阵 $𝐴$ ，那么 $𝐴^{†}$ 就是 $𝐴$ 的共轭转置矩阵。

⟨ 𝜓 | = {| 𝜓 ⟩}^{†}

同维左矢右矢之间可以做矩阵乘法。例如，当 $| 𝜑 ⟩, | 𝜓 ⟩$ 同维时， $⟨ 𝜓 | | 𝜑 ⟩$ 是一个数，而 $| 𝜑 ⟩ ⟨ 𝜓 |$ 是一个矩阵。

四、量子位(Quantum Bit, Qubit)

1.计算基态与叠加态

在量子情境下，我们也规定单个量子位的取值集合为 $Σ = {0, 1}$ ，也即右矢总取为 $| 0 ⟩, | 1 ⟩$ 。这样，对于 $𝑛$ 位的量子位，它们一定能表示 $| 𝑥 ⟩, 𝑥 \in [0, 2^{𝑛} - 1]$ 这 $2^{𝑛}$ 个态，对于这些可以只用 $| 𝑥 ⟩$ 表示的态，我们称之为计算基态(Computational Basis States)。

现在我们用叠加态(Superposition)来取代上文经典情境下的概率模型。例如单个量子位的叠加态被正交分解为两个一位计算基态的叠加：

| 𝜓 ⟩ = 𝛼 | 0 ⟩ + 𝛽 | 1 ⟩

⁵⁵ 由于选定计算基作为基底，此时量子位在被测量后只能落入计算基态。

因此，描述一个量子位的叠加态的“概率”向量具有两个元素：

| 𝜓 ⟩ = [\begin{matrix} 𝛼 \\ 𝛽 \end{matrix}]

这两个元素并非真正的概率，而是振幅(Amplitude)。根据上述的量子力学的基本内容，其概率之和应恒为 $1$ ：

{| 𝛼 |}^{2} + {| 𝛽 |}^{2} = 1

这在量子力学中称为归一化条件。上述内容亦可推广至多个量子位的情形，例如叠加态 ${[\begin{matrix} 𝛼 & 𝛽 & 𝜑 & 𝜙 \end{matrix}]}^{𝑇}$ 具有四个元素，就表示了一个 ${log}_{2} (4) = 2$ 位的量子系统：

𝛼 | 00 ⟩ + 𝛽 | 01 ⟩ + 𝜑 | 10 ⟩ + 𝜙 | 11 ⟩

根据归一化条件，下式恒成立：

{| 𝛼 |}^{2} + {| 𝛽 |}^{2} + {| 𝜑 |}^{2} + {| 𝜙 |}^{2} = 1

⁶⁶ 按照定义，叠加态中包含计算基态，只是这种特殊的叠加态中某组分的概率幅的模长恰为 $1$ 而其他组分均为 $0$ 。但当我们提起“叠加态”时，会更侧重于说明它确实是叠加而来的。叠加态与计算基态都是量子态(Quantum State)的形式，但量子态还包含其他形式，会在之后的文章中说明。

2.酉矩阵

在量子情境下，我们用酉矩阵(Unitary Matrix)来取代经典情境下的随机矩阵。在单个量子位的情况下，一些比较基本的酉矩阵如下：

\begin{aligned} 𝐻 = \frac{1}{\sqrt{2}} [\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix}], 𝐼 = [\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}], \\ NOT = [\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}], 𝑅_{𝜃} = [\begin{matrix} cos (𝜃) & - sin (𝜃) \\ sin (𝜃) & cos (𝜃) \end{matrix}] \end{aligned}

其中矩阵 $𝐻$ 执行的操作被称为哈达玛变换(Hadamard Transform)，这个操作是可逆的，即在操作之后还能使量子位回到作用前的状态——实际上，将这个变换连续两次作用于一个量子位，就能使其回到原先的状态，因为：

\begin{aligned} 𝐻 \cdot 𝐻 & = \frac{1}{\sqrt{2}} [\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix}] \cdot \frac{1}{\sqrt{2}} [\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix}] \\ = \frac{1}{2} [\begin{matrix} 2 & 0 \\ 0 & 2 \end{matrix}] \\ = [\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}] = 𝐼 \end{aligned}

而单位矩阵 $𝐼$ 相当于不对量子位做操作。事实上，所有酉变换都是可逆的。这是因为酉矩阵的性质：若矩阵 $𝑈$ 是酉矩阵，那么 $𝑈 𝑈^{†} = 𝐼$ 是总是成立的。

由于狄拉克符号是对矩阵的简便表示，酉矩阵自然也可以对狄拉克符号作用，这样可以减少书写量。例如对于哈达玛变换，在作用于量子位时使用矩阵则写为：

𝐻 | 𝜓 ⟩ = \frac{1}{\sqrt{2}} [\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix}] [\begin{matrix} 𝛼 \\ 𝛽 \end{matrix}] = \frac{1}{\sqrt{2}} [\begin{matrix} 𝛼 + 𝛽 \\ 𝛼 - 𝛽 \end{matrix}]

而当使用狄拉克符号时写为：

𝐻 | 𝜓 ⟩ = 𝐻 (𝛼 | 0 ⟩ + 𝛽 | 1 ⟩) = 𝛼 𝐻 | 0 ⟩ + 𝛽 𝐻 | 1 ⟩

其中：

𝐻 | 0 ⟩ = \frac{1}{\sqrt{2}} | 0 ⟩ + \frac{1}{\sqrt{2}} | 1 ⟩

𝐻 | 1 ⟩ = \frac{1}{\sqrt{2}} | 0 ⟩ - \frac{1}{\sqrt{2}} | 1 ⟩

从而：

\begin{aligned} 𝐻 | 𝜓 ⟩ & = 𝛼 (\frac{1}{\sqrt{2}} | 0 ⟩ + \frac{1}{\sqrt{2}} | 1 ⟩) + 𝛽 (\frac{1}{\sqrt{2}} | 0 ⟩ - \frac{1}{\sqrt{2}} | 1 ⟩) \\ = \frac{𝛼 + 𝛽}{\sqrt{2}} | 0 ⟩ + \frac{𝛼 - 𝛽}{\sqrt{2}} | 1 ⟩ \end{aligned}

两者的结果是相同的。