多伊奇-乔萨算法

多伊奇-乔萨算法（）是戴维·多伊奇和理查德·喬薩于1992年提出的一种确定性量子算法。1998年，、、基娅拉·马基亚韦洛（Chiara Macchiavello）与对其进行了改进。尽管该算法目前在现实中基本没有用途，但可以证明它比任何可能的确定性经典算法都快指数级，是最早提出的有此特性的量子算法之一。

问题描述
在多伊奇-乔萨问题中，我们有一个被称为预言机的黑盒量子计算机，它能实现某一函数 f\colon\{0,1\}^n\rightarrow \{0,1\}。该函数以n比特值作为输入，输出结果则为0或1。问题承诺该函数要么是常函数（即对任何输入都输出恒定值0或1），要么是平衡（balanced）函数（即对一半的输入返回1，另一半则返回0）。问题的任务是通过预言机确定f是常函数还是平衡函数。

问题背景
多伊奇-乔萨问题是专门为量子计算设计的一个问题，该问题对于量子算法而言相对容易，但对任何确定性经典算法来说都是十分困难的。其提出的动机是展示可以由量子计算机有效并且正确解决的一个黑盒问题，而同时确定性经典计算机则需要进行大量计算才能解决该问题。更准确地说，该问题表明了复杂度类（即可以由量子计算机在多项式时间内精确地解决）与P之间的预言分离（oracle separation）。

由于该问题在概率经典计算机上也很容易解决，因此它不会产生与复杂度类BPP（即在概率经典计算机上以多项式时间解决且误差有界）之间的预言分离。则是一个证明BQP和BPP之间产生预言分离的例子。

经典算法
对于传统的确定性算法而言，假设n是比特数，则在最坏情况下需要2^{n-1} + 1次对f的求值。为了证明f是常函数，必须对超过一半的输入进行计算并且发现它们有相同的输出。最好情况是f为平衡函数且恰好选择的前两个输入值对应不同的输出值。对于传统的随机算法，k次求值足以产生高概率的正确答案（对k \geq 1 错误概率为\epsilon \leq 1/2^{k}）。然而，如果想保证获得正确答案的话，仍需要k=2^{n-1} + 1次求值。多伊奇-乔萨量子算法则仅需一次对f的求值就能获得准确的答案。

历史
多伊奇-乔萨问题是戴维·多伊奇早期工作（1985年）的推广。当时他提出的算法针对的是 n = 1 的简单情形，即有一个输入为1比特的布尔函数f: \{0,1\} \rightarrow \{0,1\}，需要确定该函数是否是常函数。

多伊奇最早提出的算法实际上并不是确定性的。1992年，多伊奇与乔萨共同提出了一种确定性算法，并将该算法推广到n比特的输入值。与多伊奇的算法不同，该算法需要进行两次而非一次函数求值。

后来克利夫等人又对多伊奇-乔萨算法进行了改进，提出了一种既具有确定性又仅需一次f求值的算法。不过为了纪念多伊奇和乔萨两人开创性的贡献，该算法仍被称为多伊奇-乔萨算法。

算法
多伊奇-乔萨算法成立的前提之一是由x计算f(x)的预言机必须是一个不会将x退相干的量子预言机。此外，它也不能在算法结束后留下任何x的拷贝。
]]
假设我们有n+1比特量子态|0\rangle^{\otimes n} |1\rangle ，即前n比特分别处于|0\rangle 而最后一比特则是|1\rangle 。对每个比特应用阿达马变换可以得到

: \frac{1}{\sqrt{2^{n+1}}}\sum_{x=0}^{2^n-1} |x\rangle (|0\rangle - |1\rangle ) .

f是由量子预言机实现的函数。预言机将量子态 |x\rangle|y\rangle 映射到 |x\rangle|y\oplus f(x) \rangle ，其中\oplus是模2加法（由受控非门实现，可以看作是量子版异或门）。于是该量子预言机可以将上述量子态转换为

: \frac{1}{\sqrt{2^{n+1}}}\sum_{x=0}^{2^n-1} |x\rangle (|f(x)\rangle - |1\oplus f(x)\rangle ) .

对于每个x, f(x)的结果为0或1。为了检验这两种可能性，我们注意到上面的量子态等价于

: \frac{1}{\sqrt{2^{n+1}}}\sum_{x=0}^{2^n-1} (-1)^{f(x)} |x\rangle (|0\rangle - |1\rangle ) .

此时可以忽略最后一个量子比特\frac{|0\rangle - |1\rangle}{\sqrt{2}}，剩余部分为：

: \frac{1}{\sqrt{2^{n}}}\sum_{x=0}^{2^n-1} (-1)^{f(x)} |x\rangle .

再对每一量子比特进行阿达马变换，得到

: \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}(-1)^{f(x)} \left[ \frac{1}{\sqrt{2^n}} \sum_{y=0}^{2^n-1}(-1)^{x\cdot y} |y\rangle \right] =
\frac{1}{2^n}\sum_{y=0}^{2^n-1} \left[\sum_{x=0}^{2^n-1}(-1)^{f(x)} (-1)^{x\cdot y}\right] |y\rangle

其中x\cdot y=x_0 y_0\oplus x_1 y_1\oplus\cdots\oplus x_{n-1} y_{n-1} 是每一比特相应乘积之和。

最后，我们可以检验测量得到|0\rangle^{\otimes n} 的概率

: \bigg|\frac{1}{2^n}\sum_{x=0}^{2^n-1}(-1)^{f(x)}\bigg|^2

当f(x)是常函数（相长干涉）时此概率为1，当f(x)是平衡函数（相消干涉）时此概率为0。换句话说，如果f(x)是常函数的话测量结果为|0\rangle^{\otimes n} （即所有量子比特全为零），其他结果则表明f(x)是平衡函数。

多伊奇算法
多伊奇算法是一般多伊奇-乔萨算法的特例。此时我们需要检查f(0)=f(1)是否成立。这相当于检查f(0)\oplus f(1)，当结果为零时表明f是常函数，否则则不是常函数。

我们从两比特量子态|0\rangle |1\rangle开始，对每一量子比特应用阿达马变换，结果为

: \frac{1}{2}(|0\rangle + |1\rangle)(|0\rangle - |1\rangle).

函数f可以将|x\rangle |y\rangle映射为|x\rangle |f(x)\oplus y\rangle，将此函数应用于当前的量子态，可以得到

: \frac{1}{2}(|0\rangle(|f(0)\oplus 0\rangle - |f(0)\oplus 1\rangle) + |1\rangle(|f(1)\oplus 0\rangle - |f(1)\oplus 1\rangle))
: =\frac{1}{2}((-1)^{f(0)}|0\rangle(|0\rangle - |1\rangle) + (-1)^{f(1)}|1\rangle(|0\rangle - |1\rangle))
: =(-1)^{f(0)}\frac{1}{2}\left(|0\rangle + (-1)^{f(0)\oplus f(1)}|1\rangle\right)(|0\rangle - |1\rangle).

忽略最后一个比特与全局相位因子，可以得到量子态

: \frac{1}{\sqrt 2}(|0\rangle + (-1)^{f(0)\oplus f(1)}|1\rangle).

再次应用阿达马变换，得到

: \frac{1}{2}(|0\rangle + |1\rangle + (-1)^{f(0)\oplus f(1)}|0\rangle - (-1)^{f(0)\oplus f(1)}|1\rangle)
: =\frac{1}{2}((1 +(-1)^{f(0)\oplus f(1)})|0\rangle + (1-(-1)^{f(0)\oplus f(1)})|1\rangle).

当且仅当测量结果为|0\rangle时有f(0)\oplus f(1)=0。反之，当且仅当测量结果为|1\rangle时有f(0)\oplus f(1)=1。因此我们可以肯定地知道f(x)是否为常函数。

参考文献