D-J算法的学习与介绍，量子算法中快速分辨平衡函数和常数函数的算法。

Deutsch-Jozsa 算法

1.Deutsch问题

首先我们使用 $x \in \{0,1\}^n$表示$x$是由0或1组成的任意n位二进制数，比如n=3的011,n=7的1010011

对于一个比特的四种操作可以分为两类

• 常数操作constant: 恒等0或恒等1
• 平衡操作balanced: 不变, 翻转

由此我们可以描述$\forall x \in {0,1}^n$，对于0和1组成的任意n位长度二进制数的量子操作：

• Constant:

$$ f(x) = 0 或 f(x) = 0 $$

• Balanced:

$$ 50%情况f(x) = 0 另外50%情况f(x) = 1 $$

Deutsch问题就是，如果有一个符合以上条件的未知函数，如何尝试最少且足够的次数，来确定它是Constant操作还是Balanced操作

2.经典计算机解法

n位2进制最多表示$2^n$个数字， ，即8位可以表示的种类有$2^8 = 256$

所以，对于经典计算机来说，需要尝试$2^n * \frac{1}{2}+1$次，即一般多一次才能确保属于哪一种。

3.量子计算解法

而在量子计算机中只需要一次尝试就可以做出准确的判断

图中符号$\psi$读作psaɪ

首先我们需要设计一个电路$U$,它包含我们需要进行判断的函数$f(x)$，可以说是我们在$f(x)$的基础上又增加一些处理使其成为函数$U$。

$U$的作用就是可以传入一些量子比特，然后输出为另一些量子比特，并且可以让我们输出的量子比特中一眼就可以看出其中$f(x)$是Constant操作还是Balanced操作

这个量子门并不难实现， 它只要满足能够把$|x\rang |y\rang$映射为$|x \rang |y \oplus f(x) \rang $

就可以了： $$ U: |x \rang |y\rang => |x\rang|y\oplus f(x)\rang $$

这里 $\oplus$的意思是异或， 即 $0 \oplus 0=0$, $1 \oplus 1 = 1$, $1 \oplus 0$ = 1, $0 \oplus 1=0$, 异或有些有趣的规律

• 异或看起来和CNOT门很像， 第一位是0的结果和第二位相同， 第一位是1的结果和第二位相反

根据上面的式子，我们只需要根据输出的$|x\rang$就可以判断出$f(x)$属于Constant还是Balanced操作

4. Deutsch-Jozsa算法解析

4.1单比特推导

我们对$n=1$即一个比特位的情况进行推演，初始量子比特位为$|0\rang$, 我们还需要一个初始量子比特状态为$|1\rang$的辅助比特。如下图所示，输出两个量子比特， 1个0，1个1， 即$\psi_0 = |0\rang |1\rang$

关于H门，即Handamard门，相当于乘以一个特殊矩阵 $H = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \\ \end{pmatrix}$ ， 即 $|0\rang$变为$\frac{|0\rang+|1\rang}{\sqrt{2}}$, 即 $|1\rang$变为$\frac{|0\rang-|1\rang}{\sqrt{2}}$

经过H门计算之后的结果为 $$ \psi_1 = H|0\rang \oplus H|1\rang = (\frac{|0\rang+|1\rang}{\sqrt{2}})\oplus(\frac{|0\rang-|1\rang}{\sqrt{2}}) = \frac{1}{2}(|0\rang+|1\rang)(|0\rang-|1\rang) $$ 计算U之后的结果

对于函数$U$， 由于我们有： $$ U: |x\rang |y\rang => |x\rang |y\oplus f(x)\rang $$ 所以经过$U$之后 $$ \psi_1 = \frac{1}{2}(|0\rang + |1\rang)(|0\rang-|1\rang) = \frac{1}{2}(|0\rang|0\rang)-|0\rang|1\rang + |1\rang|0\rang-|1\rang|1\rang) $$ 我们注意到 $f(0)$只能取0或1，

那么当$f(0) = 0$时， $(-1)^{f(0)}=1$, 并且有：

$|0\oplus f(0)\rang-|1\oplus f(0)\rang=|0\oplus0\rang-|1\oplus0\rang=|0\rang-|1\rang=(-1)^{f(0)}(|0\rang-|1\rang)$

当$f(0)=1$时， $(-1)^{f(0)}=-1$，并且有：

$|0\rang\oplus f(0)\rang - |1\oplus f(0)\rang = |0\oplus1\rang-|1\oplus1\rang = |1\rang-|0\rang = (-1)^{f(0)}(|0\rang-|1\rang)$

结合这种情况，一定有： $$ |0 \oplus f(0) \rang - |1 \oplus f(0)\rang = (-1)^{f(0)}(|0\rang-|1\rang) $$ 同样的道理， $f(1)$也可以等于0或1,所以也会有： $$ |0 \oplus f(1)\rang - |1\oplus f(1)\rang = (-1)^{f(1)}(|0\rang-|1\rang) $$ 把这两个式子带入$\psi_2$得到 $$ \psi_2 = \frac{1}{2}(|0\rang(|0\oplus f(0)\rang - |1\oplus f(0)\rang) + |1\rang(|0 \oplus f(1)\rang - |1\oplus f(1)\rang)) \\ =\frac{1}{2}((-1)^{f(0)}|0\rang(|0\rang-|1\rang)+(-1)^{f(1)}|1\rang(|0\rang-|1\rang))\\ =\frac{1}{2}((-1)^{f(0)}|0\rang+(-1)^{f(1)}|1\rang)(|0\rang-|1\rang) $$

注意上面的括号范围

再次经过H门后的结果

对 $\psi_2$乘以Hadmard矩阵，即 $|0\rang$变为$\frac{|0\rang+|1\rang}{\sqrt{2}}$, $|1\rang$变为$\frac{|0\rang-|1\rang}{\sqrt{2}}$这就得到$\psi_3$.注意如图所示，是对整体进行H门操作，而不是每一位分别进行H门操作 $$ \psi_3 = \frac{1}{2}((-1)^{f(0)}|0\rang+(-1)^{f(1)}|1\rang)(|0\rang-|1\rang) \\ = \frac{1}{2}((-1)^{f(0)}\frac{|0\rang+|1\rang}{\sqrt{2}}+(-1)^{f(1)}\frac{|0\rang-|1\rang}{\sqrt{2}})(|0\rang-|1\rang) \\ = ((-1)^{f(0)}\frac{|0\rang+|1\rang}{2}+(-1)^{f(1)}\frac{|0\rang-|1\rang}{2})(\frac{|0\rang-|1\rang}{\sqrt{2}}) \\ = (\frac{(-1)^{f(0)}+(-1)^{f(1)}}{2}|0\rang+\frac{(-1)^{f(0)}-(-1)^{f(1)}}{2}|1\rang)(\frac{|0\rang-|1\rang}{\sqrt{2}}) $$ 测量结果

由上面可以知道，我们只需测量$|x\rang$的值即可判断属于那种函数， 也就是$\psi_3$要被$M$测量的部分为 $$ \frac{(-1)^{f(0)}+(-1)^{f(1)}}{2}|0\rang+\frac{(-1)^{f(0)}-(-1)^{f(1)}}{2}|1\rang $$ 假设$f(x)$是Constant即$f(0)=f(1)=1$，那么这个结果是 $$ \frac{(-1)^{f(0)}+(-1)^{f(1)}}{2}|0\rang+\frac{(-1)^{f(0)}-(-1)^{f(1)}}{2}|1\rang \\ = \frac{(-1)^1+(-1)^1}{2}|0\rang +\frac{(-1)^1-(-1)^1}{2}|1\rang \\ = \frac{-2}{2}|0\rang+\frac{0}{2}|1\rang = -|0\rang $$ 同理$f(0)=f(1)=0$的结果也是类似的 $$ \frac{(-1)^{f(0)}+(-1)^{f(1)}}{2}|0\rang+\frac{(-1)^{f(0)}-(-1)^{f(1)}}{2}|1\rang \\ = \frac{(-1)^0+(-1)^0}{2}|0\rang + \frac{(-1)^0-(-1)^0}{2}|1\rang \\ = |0\rang $$

对于$M$测量操作求平方计算结果来说， $|0\rang$和$-|0\rang$都是0

如果$f(x)$是Balance操作，即$f(0) = 1-f(1)$

若$f(0)=1, f(1)=0$，那么 $$ \frac{(-1)^{f(0)}+(-1)^{f(1)}}{2}|0\rang+\frac{(-1)^{f(0)}-(-1)^{f(1)}}{2}|1\rang \\ = \frac{-1+1}{2}|0\rang + \frac{-1-1}{2}|1\rang =-|1\rang $$ 若$f(0) = 0, f(1) = 1$, 那么： $$ \frac{(-1)^{f(0)}+(-1)^{f(1)}}{2}|0\rang+\frac{(-1)^{f(0)}-(-1)^{f(1)}}{2}|1\rang \\ = \frac{1-1}{2}|0\rang + \frac{1-(-1)}{2}|1\rang = |1\rang $$ 综上，如果最后$M$的测量结果为0， 那么$f(x)$一定是Constant操作，最后的结果为1，一定是Balance操作

4.2多位电路分析

输入$n$个$|0\rang$和1个辅助测量比特$|1\rang$，即: $$ \psi_0 = \overbrace{|0\rang\oplus|0\rang\oplus \cdot\cdot\cdot|0\rang}^{n}\oplus |1\rang \\ = |0\rang^{\oplus n}|1\rang $$