最近研究了一下Deutsch-Jozsa算法。

看了很多资料，基本上是在讲数学推导，没有回答「为什么要这样做」的问题。经过思考，我觉得我可以来回答一下这个问题。

在经典计算机中，我们解决Deutsch问题的方法很简单，只需要询问 f(x)f(x) 所有的输出，就可以解决这一个问题。

为了数学上的严谨，我们计算这个式子的值：

请自行理解它的含义。

在量子计算机中，情况不同。

这是电子双缝干涉的实验。

1.每个电子在（a）之前可以看作是一个superposition的状态，即被Hadamard门处理过的量子比特。

2.为了探究电子的行为，一次只发射一个电子，避免了电子的相互作用。

3.结果发现电子在（b）的分布仍然符合波函数的描述。

我们会怎么解释这个现象？

难道电子会同时通过两个狭缝吗？是的。我们需要这样解释。电子就像一坨浆糊，像流体一样，同时通过两个狭缝。然后，在屏幕上被观测到。一旦被观测到，这个电子的波函数就会塌缩。然后我们重复实验，得到的图样是这样的。

所以，我们认为电子同时穿过了两个狭缝。

这就是Deutsch-Jozsa算法的核心。

如果把函数f(x)看作一块隔板，那么f(x)上的两个狭缝就像f(x)的每一个映射（mapping）。

如果我们输入一个混合量子比特进入f(x)会不会同时得到两个映射呢？

两个狭缝就像函数的两个不同的路径，因此，一个superposition的量子比特在输入后可以进入两个不同的路径，也就是，遍历整个函数！这就为我们的工作提供了可能性。

因此，量子计算机可以遍历整个函数，而只用到一个输入。

为了得到像电子一样的混合态量子比特，我们把纯净量子比特通过Hadamard门，得到混合态量子比特。

然后把混合态量子比特输入执行f(x)的黑箱。

黑箱需要输出什么？这不是我们关心的问题。anyway，我们现在已经遍历了整个函数，并且，只运行了f(x)一次。

那么，我们下一步是什么？当然是数学定量表述。

我们用到了f-CNOT门，这是一种可以把f(x)做成(-1)^f(x)的门。

然后这样一个门的功能是：

以n=1的D-J算法为例：

=(|0>-|1>)/\sqrt{2}">in:|x>=(|0>−|1>)/2in: |x>=(|0>-|1>)/\sqrt{2}

=(|0>-|1>)/\sqrt{2}">in:|y>=(|0>−|1>)/2in: |y>=(|0>-|1>)/\sqrt{2}

a.若 f(x)==0:f(x)==0:

-|1⊕0>)/\sqrt{2}=(|0>-|1>)/\sqrt{2}">out:(|0⊕0>−|1⊕0>)/2=(|0>−|1>)/2out:(|0⊕0>-|1⊕0>)/\sqrt{2}=(|0>-|1>)/\sqrt{2}

b.若 f(x)==1:f(x)==1:

-|1⊕1>)/\sqrt{2}=(|1>-|0>)/\sqrt{2}=-(|1>-|0>)/\sqrt{2}">out:(|0⊕1>−|1⊕1>)/2=(|1>−|0>)/2=−(|1>−|0>)/2out:(|0⊕1>-|1⊕1>)/\sqrt{2}=(|1>-|0>)/\sqrt{2}=-(|1>-|0>)/\sqrt{2}

汇总结果：

-|1>)/\sqrt{2}">out=(−1)f(x)(|0>−|1>)/2out=(-1)^{f(x)}(|0>-|1>)/\sqrt{2} （这就是（-1）^f(x)的来历，不需要用到复数～）

...一波操作（纯数学）

然后我们就得到了类似于

的结果。

我不提供具体的数学表述，因为其他人已经有很完备的回答了：

Golden Horqin：量子计算的理论发展（三）47 赞同 · 6 评论文章