量子Deutsch算法过程推导（Qantum Deutsch Algorithm）

Deutsch算法过程的推导

本文中的内容参考的是 Micheal A.Nielsen与Isaac L.Chuang合著的《Quantum Computation and Quantum Information》有兴趣的同学可以去阅读原文。

Deutsch算法背景介绍

假设，我们有函数$f(x)$, 对于一个输入x∈{0,1}x\in\{0,1\}x∈{ 0,1}，有$f(x)$或者为一个常值函数f(0)=f(1)∈{0,1}f(0)=f(1)\in\{0,1\}f(0)=f(1)∈{ 0,1}, 或者为一个平衡函数$f(x)=1?x$ 满足 x∈{0,1}x\in\{0,1\}x∈{ 0,1}。现在的问题是我们应该如何判断$f(x)$是属于哪一个类别。对于经典计算机来说，我们需要两次计算即，计算$f(0)$与$f(1)$, 再比较。而对于量子计算机我们只需要一次计算即可进行判断。

Deutsch算法电路图¹

上图中的 $U_f$模块的作用效果可以写成$U_f:|x?|y?\to |x?|y?f(x)?$,容易说明$U_f$是酉的。

Deutsch算法推导过程

初始状态我们可以简单写出 $|{\psi }_0?=|0?|1?$,在这里我们省略的张量积符号。
第一步，我们在上下两个比特上分别作用两个Hadamard门，于是我们可以得到
$|{\psi }_1?=[\frac{|0?+|1?}{\sqrt{2}}][\frac{|0??|1?}{\sqrt{2}}]$
第二步，我们作用构造的$U_f$门可以得到
$|{\psi }_2?=U_f|{\psi }_1?=\frac{1}{2}[|0,f(0)??|0,1?f(0)?+|1,f(1)??|1,1?f(1)?]$
$=\frac{1}{2}[|0?(|f(0)??|1?f(0)?)+|1?(|f(1)??|1?f(1)?)]$
此时，我们根据背景里面提到的两种情况进行讨论。
第一种情况，$f(0)=f(1)$:
此时，$|{\psi }_2?$可以重新写成
$|{\psi }_2?=\frac{1}{2}[|0?(|f(0)??|1?f(0)?)+|1?(|f(0)??|1?f(0)?)]=\frac{1}{2}[|0?+|1?][|f(0)??|1?f(0)?]$
第二种情况，$f(0)?=f(1)$,此时，满足$f(1)=1?f(0),1?f(1)=f(0)$:
$|{\psi }_2?=\frac{1}{2}[|0?(|f(0)??|1?f(0)?)+|1?(|1?f(0)??|f(0)?)]=\frac{1}{2}[|0??|1?][|f(0)??|1?f(0)?]$
此时，我们对第一个qubit作用一个Hadamard门，可以看到
对于第一种情况，我们有
$|{\psi }_3?=\frac{1}{\sqrt{2}}|0?[|f(0)??|1?f(0)?]$
对于第二种情况我们有
$|{\psi }_3?=\frac{1}{\sqrt{2}}|1?[|f(0)??|1?f(0)?]$
所以，当我们对第一个qubit进行测量。通过测量结果，我们就可以知道关于$f(x)$的特性了。