量子算法Deutsch–Jozsa algorithm | 中科院理论物理所

蔻享学术

The following article is from 中国科学院理论物理研究所 Author 周鹏飞

理论物理所科研动态和综合新闻的发布；理论物理及其交叉学科的科学传播

作者简介

周鹏飞理论物理所18级在读博士生，导师为张潘研究员，研究方向为统计物理，对量子计算感兴趣。

量子计算凭借其并行计算的特性渐渐成为研究和发展的热点，量子算法的设计自然是必不可少的环节。这里我们介绍一个著名的量子算法：Deutsch–Jozsa algorithm，它最早由David Deutsch和Richard Jozsa在1992年提出[1]，后来由Richard Cleve,Artur Ekert, Chiara Macchiavello和Michele Mosca于1998年改进[2]。尽管这个量子算法是针对于一个几乎没有实用价值的问题，但是它是第一个向我们展示量子计算相比经典计算拥有指数加速性能的量子算法，是一个非常优美的工作，能够帮助我们理解量子算法，而且这个算法也启发了其他量子算法的发明。学会这个算法不需要非常高深的数学和物理知识，只需要简单的线性代数知识和量子力学的基础概念。

Deutsch–Jozsa algorithm想要解决的问题是这样描述的：对于一个布尔函数 $f$ ，它的定义域是 $x \in \{0,1\}^n$ ， $x$ 可以看成一个长度为 $n$ 的向量，其中向量的每个元素可以取0或者1, 我们也叫 $x$ 为一个长度为 $n$ 的比特串；值域是 $f(x)\in \{0,1\}$ ; $f(x)$ 的形式有两种选择，它可以是一个常函数，就是对于任意的输入 $x \in \{0,1\}^n$ , $f(x)$ 都是0或者1；也可以是一个平衡函数，就是在 $x$ 的 $2^n$ 的所有可能取值中，有一半 $x$ 的函数值为 $1$ ,一半 $x$ 的函数值为 $0$ ，问什么样的算法可以最快知道 $f(x)$ 是一个常函数还是一个平衡函数？显然的对于经典计算来说，我们可以喂给 $f(x)$ $2^n/2+1$ 个不同的 $x$ 就能知道 $f(x)$ 是一个常函数还是一个平衡函数，当然我们可以利用并行计算同时计算这 $2^n/2+1$ 个 $x$ 的函数值，但是会需要更多的计算资源，而Deutsch–Jozsa algorithm通过利用量子叠加态的性质可以巧妙的判断 $f(x)$ 是一个常函数还是一个平衡函数，有兴趣的童靴可以先自己尝试想出一个量子算法解决这个问题，如果想出好的算法给自己一个大大的奖励哦！

对于一个经典的比特，一般会用电路中的高低电平表示，高电平表示 $1$ 态，低电平表示 $0$ 态，显然的一个经典比特要么处于高电平表示 $1$ 态，要么处于低电平表示 $0$ 态；但是在量子世界中，奇怪的性质出现了，假如在量子世界中我们用一个电子表示一个量子的比特，相应的电子自旋向下表示 $\Ket{1}$ 态(这里是狄拉克表示，它是量子力学中的一个标准表示)，自旋向上表示 $\Ket{0}$ 态，那么这个量子比特不仅仅可以处于 $\Ket{1}$ 或者 $\Ket{0}$ 态，还可以处于它们俩的叠加态比如 $\alpha \Ket{0} + \beta \Ket{1}$ ,其中的 $|\alpha|^2+|\beta|^2=1$ $\Ket{0}$ 是为了满足量子态的归一化性质，可以解释为当我们测量这个量子比特时，它处于态的概率是 $|\alpha|^2$ ,处于 $\Ket{1}$ 态的概率是 $|\beta|^2$ ;可以将 $\Ket{1}$ 态视为列向量 $(0,1)^T$ ( $T$ 代表转置),将 $\Ket{0}$ 态视为列向量 $(1,0)^T$ ,对应的叠加态 $\alpha \Ket{0} + \beta \Ket{1}=(\alpha, \beta)^T$ 。正是因为叠加态的性质，量子计算可以实现并行计算，进而实现指数加速。我们先引入量子门的概念，当然了，量子门和经典的逻辑门有相似的性质，但有本质的区别，这里暂不讨论，我们先介绍一个与经典的非门相对应的单比特的量子非门，它就是泡利矩阵 $\sigma_x$ ,这里用 $X$ 标记。 $\begin{equation} \left( \begin{array}{ccc} 0 & 1\\ 1 & 0\\ \end{array} \right) \end{equation}$ 假如我们把它作用到前面讨论的叠加态 $\alpha \Ket{0} + \beta \Ket{1}$ ，用数学公式表示就是 $X(\alpha \Ket{0} + \beta \Ket{1})=\alpha X \Ket{0} + \beta X \Ket{1}$ 会得到这样一个叠加态 $\alpha\Ket{1}+\beta \Ket{0}$ ，可以看到我们的量子非门同时把 $\Ket{1}$ 态变成了 $\Ket{0}$ 态， $\Ket{0}$ 态变成了 $\Ket{1}$ 态，完成了非门的功能，更要注意到的是，我们的这个量子门是线性可逆的(可以思考经典的逻辑门是线性可逆的吗？)，这其实是所有量子门的特性，当然量子力学的过程都是幺正的，所以一个合理的量子门也应该是幺正的，即 $X^{\dagger}X=I$ 。

我们再介绍两个后面我们会用到的量子门，一个是单比特Hadamard门，一个是多比特控制非门。单比特Hadamard门很简单，它的数学表达式为： $\begin{equation} \frac{1}{\sqrt{2}}\left( \begin{array}{ccc} 1& 1\\ 1 & -1\\ \end{array} \right) \tag{2} \end{equation}$ 可以验证Hadamard门有这样的性质，它可以将 $\Ket{0}$ 态变成 $\frac{1}{\sqrt{2}}(\Ket{0}+\Ket{1})$ 态,将 $\Ket{1}$ 态变成 $\frac{1}{\sqrt{2}}(\Ket{0}-\Ket{1})$ 态；反过来也可以使 $\frac{1}{\sqrt{2}}(\Ket{0}+\Ket{1})$ 态变成 $\Ket{0}$ 态， $\frac{1}{\sqrt{2}}(\Ket{0}-\Ket{1})$ 态变成 $\Ket{1}$ 态。我们记 $n$ 个Hadamard门的张量直积为 $H^{\otimes n}$ ,它作用在n个处于 $\Ket{0}$ 的量子比特的图示为图1,

$\bullet$ 图1 $H^{\otimes n}$ 作用在 $n$ 个处于 $\Ket{0}$ 的量子比特上，其中 $/^{n}$ 代表 $n$ 个量子比特的简化

我们也叫类似这样的量子门作用在量子比特上的结构叫做量子电路； $H^{\otimes n}$ 作用在 $n$ 个处于 $\Ket{0}$ 态的量子比特上( $\Ket{0}^{\otimes n}$ )本质上就是每一个Hadamard门分别作用在每一个量子比特上，相应的得到 $n$ 个处于 $\frac{1}{\sqrt{2}}(\Ket{0}+\Ket{1})$ 态的量子比特，当然也可以写为直积态 $\frac{1}{\sqrt{2^n}}\big(\Ket{0}+\Ket{1}\big)^{\otimes n}$ ; 我们也可以把直积态 $\frac{1}{\sqrt{2^n}}\big(\Ket{0}+\Ket{1}\big)^{\otimes n}$ 写为 $\sum\limits_{x\in \{0,1\}^n}\frac{\Ket{x}}{\sqrt{2^n}}$ ， $x$ 代表了 $n$ 个经典比特可能的比特串， $\Ket{x}$ 是对应的量子态，比如 $\Ket{0}^{\otimes n}$ 和 $\Ket{1}^{\otimes n}$ 是其中的两种，显然 $\sum\limits_{x\in \{0,1\}^n}\frac{\Ket{x}}{\sqrt{2^n}}$ 是一个等权重的量子叠加态，即 $\Ket{x}$ 的每一种可能的取值都是等概率的；我们称 $\Ket{x}$ 叫做这 $n$ 个量子比特空间(希尔伯特空间)的基，任意一个量子态都可以由这些基构成。

$\bullet$ 图2：多比特控制非门

多比特控制非门的结构如图2，这个量子门我们记为 $U_f$ ,如果这个门作用在一个 $n$ 量子比特态 $\Ket{x}$ 和一个单量子比特态 $\Ket{y}$ 的直积态 $\Ket{x}\otimes \Ket{y}$ 上，它会得到一个 $n$ 量子比特态 $\Ket{x}$ 和一个单量子比特态 $\Ket{y \oplus f(x)}$ 的直积态 $\Ket{x}\otimes\Ket{y \oplus f(x)}$ 上，这里的 $f(x)$ 就是我们前面提到的布尔函数，而 $\oplus$ 代表求和并取模，显然如果固定 $y$ 取 $1$ , 那么 $f(x)=0$ , $y \oplus f(x)$ 为 $1$ ， $f(x)=1$ , $y \oplus f(x)$ 为 $0$ ,可以看到这个多比特控制非门实现了对多比特 $x$ 的函数值的非门控制，因此我们叫它多比特控制非门，同时我们称 $y$ 量子比特为辅助控制比特。

如果你阅读到这里，那么恭喜你已经接近尾声了，我们已经将Deutsch–Jozsa algorithm 所用到的两个门都介绍了，只需要把这两个门作用在量子态上，我们马上就能看到Deutsch–Jozsa algorithm 的威力了。下面直接给出Deutsch–Jozsa algorithm 对应的量子电路如图3, 量子电路从初态 $\Ket{\psi_0}=\Ket{0}^{\otimes n}\otimes \Ket{1}$ 开始，用 $n$ 个Hadamard门作用在 $\Ket{0}^{\otimes n}$ 和一个Hadamard门作用在 $\Ket{1}$ 上，得到中间量子态 $\Ket{\psi_1}$ ，然后利用上面介绍的多比特控制非门 $U_f$ 作用在 $\Ket{\psi_1}$ 态上，可以得到量子态 $\Ket{\psi_2}$ ,最后再用 $H^{\otimes n}$ 作用在 $\Ket{\psi_2}$ 的前 $n$ 个量子比特上，得到最终的末态 $\Ket{\psi_3}$ ,矩阵的运算过程这里我们不给出，可详细参考[3], 我们直接给出末态的形式为： $\begin{equation} \Ket{\psi_3}=\sum\limits_{z}\sum\limits_{x}\frac{(-1)^{x \cdot z+f(x)}\Ket{z}}{2^n}\otimes \big(\frac{\Ket{0}-\Ket{1}}{\sqrt{2}}\big)\tag{3} \end{equation}$ 这里 $z$ 和 $x$ 一样，都是长度为 $n$ 的比特串的可能的取值， $\Ket{z}$ 是 $n$ 个量子比特空间的基， $x \cdot z=x_1z_1+x_2z_2+\cdot \cdot \cdot+x_nz_n$ ， $\sum\limits_{z}\sum\limits_{x}\frac{(-1)^{x \cdot z+f(x)}\Ket{z}}{2^n}$ 对应上面 $n$ 个量子比特的量子态， $\frac{\Ket{0}-\Ket{1}}{\sqrt{2}}$ 代表下面那个量子比特的量子态，它们是直积态，没有纠缠，我们只需要关注上面 $n$ 个量子比特的量子态就行。现在我们仔细看一下基 $\Ket{z}=\Ket{0}^{\otimes n}$ 的系数，因为基 $\Ket{z}=\Ket{0}^{\otimes n}$ ，所以 $x\cdot z=0$ ,那么基 $\Ket{z}=\Ket{0}^{\otimes n}$ 的系数就等于 $\sum_x (-1)^{f(x)}/2^n$ 。我们看一下这个系数在 $f(x)$ 分别为常函数和平衡函数的取值情况，如果 $f(x)$ 是常函数，那么系数 $\sum_x (-1)^{f(x)}/2^n$ 为 $+1$ 或者 $-1$ ，因为量子态要求是归一化的，所以其他的基的系数一定是 $0$ ，这表明这 $n$ 个量子比特是处在基 $\Ket{0}^{\otimes n}$ 上，如果我们测量这个量子态，我们会以百分之百的概率观测到所有的量子比特都处于 $\Ket{0}$ 态；如果 $f(x)$ 是一个平衡函数，那么我们可以计算出 $\sum_x (-1)^{f(x)}/2^n=0$ ，也就是说，如果我们测量这个量子态，会有百分之百的概率观测到至少有一个量子比特处于 $\Ket{1}$ 态上，因此这个量子算法可以容易地判断 $f(x)$ 是一个常函数还是一个平衡函数。

$\bullet$ 图3：Deutsch–Jozsa algorithm的量子电路

对于一个布尔函数 $f(x)$ 是一个常函数还是一个平衡函数的问题，我们只需要 $n+1$ 个量子比特以及三个量子门的的量子资源再加上一次观测就能够判断，相信童靴们感受到量子算法的威力了，当然 Deutsch–Jozsa algorithm 针对的这个问题是一个没有任何实用价值的问题，后来就有了著名的Shor算法和Grover算法，当然需要更多仁人志士投入到量子计算中，创造出更能解决有用问题的算法！

参考文献

[1] David Deutsch and Richard Jozsa. Rapid solution of problems by quantum computation. Proceedings

of the Royal Society of London. Series A: Mathematical and Physical Sciences, 439(1907):553–558,

1992.

[2] Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca. Quantum algorithms revisited.

Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences,

454(1969):339–354, 1998.

[3] Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002.

编辑：黄琦

——往期回顾——

为满足更多科研工作者的需求，蔻享平台开通了各科研领域的微信交流群。进群请添加微信18019902656（备注您的科研方向）小编拉您入群哟！
蔻享网站www.koushare.com已开通自主上传功能，期待您的分享！
欢迎大家提供各类学术会议或学术报告信息，以便广大科研人员参与交流学习。
联系人：李盼 18005575053（微信同号）

量子算法Deutsch–Jozsa algorithm | 中科院理论物理所

发送到看一看