量子计算「演算法」4. Deutsch Jozsa 演算法

多伊奇-乔萨演算法（英语：Deutsch–Jozsa algorithm）是戴维·多伊奇和里查德·乔萨于1992年提出的一种确定性量子演算法。1998年，理察·克利夫、阿图尔·埃克特、基娅拉·马基亚韦洛（Chiara Macchiavello）与米凯莱·莫斯卡对其进行了改进。儘管该演算法目前在现实中基本没有用途，但可以证明它比任何可能的确定性古典演算法都快指数级，是最早提出的有此特性的量子演算法之一。

4.1 问题背景

4.1.1 问题描述

我们有一个函数 ，该函数以n位元值作为输入，输出结果则为0或1。规定该函数要么是常函数（即对任何输入都输出恆定值0或1），要么是平衡（balanced）函数（即对一半的输入返回1，另一半则返回0）。问题要求通过计算确定 是常函数还是平衡函数。

4.1.2 古典演算法

对于传统的确定性演算法而言，假设n是位元数，则在最坏情况下需要 次对 的求值。为了证明 是常函数，必须对超过一半的输入进行计算并且发现它们有相同的输出。最好情况是 为平衡函数且恰好选择的前两个输入值对应不同的输出值。对于传统的随机演算法，k次求值足以产生高机率的正确答案（对 错误机率为 ）。然而，如果想保证获得正确答案的话，仍需要 次求值。

4.2 Deutsch Jozsa 演算法

4.2.1 预言机

Deutsch Jozsa 演算法依赖一个被称作「预言机」的量子闸模组，它能够根据输入的值 返回需要证明的函数 对应的值 。在Deutsch Jozsa 演算法中会使用「预言机」进行数据标记。

4.2.2 初始化量子位元

我们总共需要n+1个量子位元来实现 Deutsch Jozsa 演算法，头前n个量子位元我们初始化爲0，记作 ，最后一个则初始化爲1，即 ，联合起来写成 。

4.2.3 第一次哈达马操作

我们对初始化后的每一个量子位元分别作用一个哈达马闸以产生如下变换：

4.2.4 数据标记与相位反冲

对变换 中的结果进行数据标记，我们将头前n个位元作爲「预言机」的输入，然后根据预言机的输出结果 对末尾的量子位元 进行取反：

虽然我们是对末尾的量子位元 进行取反，但造成的影响可以视爲对头前的n个位元进行正负符号的反转，这被称作「相位反冲」。

4.2.5 第二次哈达马操作

接下来，我们忽略末尾的 ，对前n个量子位元进行哈达马操作：

4.2.6 分析测量结果

最后，我们对前n个量子位元进行测量，我们分析一下测量结果爲0（即 ）的机率：

当 爲常函数时，机率 则等于1；当 爲平衡函数时，由于各项抵消机率 将等于0。于是有如下结论：