Deutsch 算法

已知函数 \(f:\{0, 1\}\to \{0,1\}\) ，问是否满足 \(f(0)=f(1)\) 。

问题等价于询问 \(f(0)\odot f(1)=\overline{f(0)\oplus f(1)}\) 的值

假定量子电路输入为 \(\left|x,y\right>\) ，输出为 \(\left|x,y\oplus f(x)\right>\)

先考虑一个最简单的情况：\(f(x)=1-x\)

当输入 \(\left|x,y\right>=\left|0,0\right>\) 时，输出 \(\left|x,y\oplus f(x)\right>=\left|0,1\right>\)

当输入 \(\left|x,y\right>=\left|0,1\right>\) 时，输出 \(\left|x,y\oplus f(x)\right>=\left|0,0\right>\)

当输入 \(\left|x,y\right>=\left|1,0\right>\) 时，输出 \(\left|x,y\oplus f(x)\right>=\left|1,0\right>\)

当输入 \(\left|x,y\right>=\left|1,1\right>\) 时，输出 \(\left|x,y\oplus f(x)\right>=\left|1,1\right>\)

现在我们将 \(\left|x\right>\) 处于叠加态，令 \(\left|x\right>={1\over \sqrt 2}(\left|0\right>-\left|1\right>)=\left|+\right>\)

此时，\(f(\left|x\right>)={1\over \sqrt 2}[f(\left|0\right>)+f(\left|1\right>)]={1\over \sqrt 2}(\left|1\right>+\left|0\right>)=\left|+\right>\)

故当 \(\left|y\right>=\left|0\right>\) 时 \(\left|x,y\oplus f(x)\right>=\left|+\right>\oplus {1\over \sqrt 2}(\left|1\right>+\left|0\right>)=\left|+,+\right>\)

当 \(\left|y\right>=\left|1\right>\) 时 \(\left|x,y\oplus f(x)\right>=\left|+\right>\oplus {1\over \sqrt 2}(\left|0\right>+\left|1\right>)=\left|+,+\right>\)

我们令 \(\left|y\right>\) 也处于叠加态 \(\left|y\right>={1\over \sqrt 2}(\left|0\right>-\left|1\right>)=\left|-\right>\)