量子算法一瞥——量子计算机简介

几年前曾一时兴起,在图书馆借了本《量子计算机研究(上)——原理和物理实现》研究,肝了几天算是把 Shor 算法——也就是那个大整数分解质因数的量子算法——搞明白了。然而我作为一条咸鱼大学的咸鱼本科生,自然不太可能接触得到这些东西。直到最近看到一些相关知识的时候,发现自己早就把算法得具体内容忘得一干二净。既然闲着也是闲着,不如全书重刷一遍吧。

量子计算机简介

量子计算机,乍一听,和量子物理学有关,净是一些高大上的东西,脑袋里立刻就会蹦出什么薛定谔的猫啊,什么多世界诠释啊,什么鬼魅般的超距作用啊。别被没营养的科普文唬得一惊一乍的,以为量子力学是什么出神入化的唯心主义伪科学。自然科学是什么,自然科学是一门学科,它通过对世界的观察,总结下来的一套数学公式、规律,并利用这个公式去改造世界。所以,不要想太多,

Shut up and calculate! –N. David Mermin

所以量子计算机是什么?和经典计算机(也就是我们现在所面对的计算机)有什么差别?

量子计算机和经典计算机相同,都是遵循物理规律,将输入经过一系列运算转换为输出的机器。和经典计算机不同的是,经典计算机的状态由电平高低决定,量子计算机的状态由量子比特的量子态决定;经典计算机的运算规则遵循经典力学,量子计算机的运算规则遵循量子力学。如果不去考虑其背后的物理诠释,它就是一系列的数学运算罢了。

量子态和经典态有什么区别呢?没错,就是多了量子叠加态和纠缠态,这两个特性将量子计算机和经典计算机区分开来。

叠加态

众所周知,经典计算机的一个位只有两种可能值: 01 ,而量子计算机不同,它的一个位——我们称之为量子位——有着近乎无穷的可能取值,当然和其它普通的量子一般,只要观测,就会坍缩到经典态 01 上。

叠加态赋予了量子计算机超乎经典计算机的运算能力,也是后文提到的各个算法的基础。

纠缠态

经常听到量子纠缠的所谓“鬼魅般的超距作用”,讲的是一对纠缠的量子之间不随距离变化的某种联系,这也导致了 Einstein 对于量子力学中主流的 Copenhagen 诠释的质疑,提出了 EPR 悖论。(不过这和本文关系不是很大,我只是瞎掰一下欸嘿嘿)。

量子纠缠在量子计算机中的作用一般是构建一对纠缠的量子,那么对第二个量子观测会同时导致第一个量子态坍缩,于是便可以求出逆函数的某个解(这是 Shor 算法的一部分)。

不过纠缠态可以用来进行 Shor 算法攻克 RSA 加密之外,它也是量子密码的一部分,稍后再讲。

数学表示

我们用更加“量子力学”的表示来重写上文中出现过的两个量子位经典态 : |0\rangle|1\rangle

\langle|\rangle 是一种被用来描述量子态的记号,是 Dirac 于 1939 年在他的一篇论文中提出来的。[1]它只是描述了一个状态,如活猫可以用 Dirac 记号描述为 |\mathrm{live}\rangle ,死猫可以记为 |\mathrm{dead}\rangle (原谅我博客的公式处理插件搞不定🐱)。

我们知道(不知道也当知道好了)量子力学系统的状态由态矢量来描述。其实 Dirac 记号所表示就是一个向量,表示的是取到某个本征态的概率 |0\rangle=\begin{bmatrix}1\\0\end{bmatrix},|1\rangle=\begin{bmatrix}0\\1\end{bmatrix} ,对于一个量子位则有 |\psi\rangle=\alpha|0\rangle+\beta|1\rangle=\begin{bmatrix}\alpha\\\beta\end{bmatrix}\begin{matrix}\Rightarrow0\\\Rightarrow1\end{matrix} 。式子中的 \alpha,\beta 分别表示观测之后坍缩为 |0\rangle,|1\rangle 的概率为 \|\alpha\|^2,\|\beta\|^2 ,注意这里的 \alpha,\beta\in\mathbb C

Dirac 记号的右矢 |\psi\rangle表示的是列向量 \begin{bmatrix}\alpha\\\beta\end{bmatrix} ,与之相对的左矢表示的是行向量 \langle\psi|=\begin{bmatrix}\alpha&\beta\end{bmatrix}

注意到 \alpha^2+\beta^2=1 ,再加上量子态存在的相位差作为第二自由度,量子位所有的可能状态覆盖了一个半径为 1 的球面,换句话说,我们可以用一个球面上的一点来表示量子的状态,称之为 Bloch 球面。(图源 Wikimedia

于是有 \,\displaystyle\alpha=\cos\frac\theta2,\beta=\mathrm e^{\mathrm i\varphi}\sin\frac\theta2\, 。容易看出来 |0\rangle 处于球顶, |1\rangle 处于球底 。

量子门

和经典计算机类似,量子计算机的基础部件也是门,但是由于量子系统的幺正性,每个门的输入和输出的数量是相同的,可以认为每个门都是一个矩阵,乘上态量子位位矢就是对量子位的操作。正是由这些最基础的门组成了复杂的量子算法。

量子一位门

Pauli-X 门

Pauli-X 门 \operatorname X 作用于两个经典态上时表现为非门,即在 Bloch 球面上绕 x 轴旋转 \pi 。可以用矩阵表示为 \operatorname X=\begin{bmatrix}0&1\\1&0\end{bmatrix}

Pauli-Y 门

Pauli-Y 门 \operatorname Y 类似于非门,它将 |0\rangle 映射到 \mathrm i|1\rangle ,将 |1\rangle 映射到 -\mathrm i|0\rangle ,相当于在 Bloch 球面上绕 y 轴旋转 \pi。用矩阵表示为 \operatorname Y=\begin{bmatrix}0&-\mathrm i\\\mathrm i&0\end{bmatrix}

Pauli-Z 门

Pauli-Z 门 \operatorname Z 不改变量子态坍缩后表现的概率,它不改变 |0\rangle 的状态,但是将 |1\rangle 映射到 -|1\rangle ,相当于在 Bloch 球面上绕 z 轴旋转 \pi 。用矩阵表示为 \operatorname Z=\begin{bmatrix}1&0\\0&-1\end{bmatrix}

Hadamard 门

\operatorname H=\frac1{\sqrt2}\begin{bmatrix}1&1\\1&-1\end{bmatrix}

Hadamard 门 H 的作用是使量子绕 Bloch 球面 x=z 轴旋转 \pi 。也就是说 \,\displaystyle\operatorname H|0\rangle=\frac1{\sqrt2}(|0\rangle+|1\rangle),\,\displaystyle\operatorname H|1\rangle=\frac1{\sqrt2}(|0\rangle-|1\rangle)\, ,显然,对它们两个状态进行观测得到 |0\rangle|1\rangle 的概率各为一半,其中一个落在 x 轴正向,另一个落在 x 负向。我们将这两个状态分别记为 |+\rangle|-\rangle 。有 \begin{aligned}|+\rangle=&\frac1{\sqrt2}\begin{bmatrix}1\\1\end{bmatrix}\\|-\rangle=&\frac1{\sqrt2}\begin{bmatrix}1\\-1\end{bmatrix}\end{aligned}

量子二位门

两位的量子表示比一位量子表示高了一个维度,一般用直积 \otimes 来表示。

\begin{aligned}|00\rangle=|0\rangle\otimes|0\rangle=\begin{bmatrix}1\\0\\0\\0\end{bmatrix}\qquad|01\rangle=|0\rangle\otimes|1\rangle=\begin{bmatrix}0\\1\\0\\0\end{bmatrix}\\|10\rangle=|1\rangle\otimes|0\rangle=\begin{bmatrix}0\\0\\1\\0\end{bmatrix}\qquad|11\rangle=|1\rangle\otimes|1\rangle=\begin{bmatrix}0\\0\\0\\1\end{bmatrix}\end{aligned}

量子二位门就是针对输入的二位量子进行相应的操作并给出输出的量子门。

交换门

顾名思义,交换两个量子位的状态。表示为 \operatorname{SWAP}=\begin{bmatrix}1&0&0&0\\0&0&1&0\\0&1&0&0\\0&0&0&1\end{bmatrix}

控制 NOT 门

控制 NOT 门 \operatorname{CNOT} 和经典计算机的 \operatorname{XOR} 门很像,对于经典输入,其第一个量子位保持不变,第二个量子位变为和第一个量子位的异或值: \operatorname{CNOT}=\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{bmatrix}

控制 Z 门

控制 Z 门又称为控制相位门 \operatorname{CZ} ,其表现和 \operatorname{CNOT} 类似,均为视第一个量子位为 1 则进行相位变换,否则不变: \operatorname{CZ}=\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&-1\end{bmatrix}

量子三位门

Toffoli 门

\begin{bmatrix}1&0&0&0&0&0&0&0\\0&1&0&0&0&0&0&0\\0&0&1&0&0&0&0&0\\0&0&0&1&0&0&0&0\\0&0&0&0&1&0&0&0\\0&0&0&0&0&1&0&0\\0&0&0&0&0&0&0&1\\0&0&0&0&0&0&1&0\end{bmatrix}

Toffoli 门也被称为 CCNOT 门,这是一个完备的可逆的三位门。所谓完备,就是说该门可以实现逻辑完备,它可以实现所有的 Boolean 逻辑操作。所谓的可逆,是指可以从输出推导出输入,也就是信息没有减少,熵没有变化,这意味着不会产生热量。

Fredkin 门

\begin{bmatrix}1&0&0&0&0&0&0&0\\0&1&0&0&0&0&0&0\\0&0&1&0&0&0&0&0\\0&0&0&1&0&0&0&0\\0&0&0&0&1&0&0&0\\0&0&0&0&0&0&1&0\\0&0&0&0&0&1&0&0\\0&0&0&0&0&0&0&1\end{bmatrix}

Fredkin 门也被称为 CSWAP 门,这也是一个完备的三位门。

上面所有的量子门组成了量子计算机的基础,下一篇文章会从几个简单的问题的量子算法指数级优化开始,展示量子算法相较于经典算法的优势。

参考资料

  1. Dirac, P. (1939). A new notation for quantum mechanics. Mathematical Proceedings of the Cambridge Philosophical Society, 35(3), 416-418. doi:10.1017/S0305004100021162

发表评论

电子邮件地址不会被公开。 必填项已用*标注