量子计算中 Deutsch-Jozsa 算法的本质是什么？
最近研究了一下Deutsch-Jozsa算法。
看了很多资料，基本上是在讲数学推导，没有回答「为什么要这样做」的问题。经过思考，我觉得我可以来回答一下这个问题。
在经典计算机中，我们解决Deutsch问题的方法很简单，只需要询问 所有的输出，就可以解决这一个问题。
为了数学上的严谨，我们计算这个式子的值：
desired formula
请自行理解它的含义。
在量子计算机中，情况不同。
电子双缝干涉
这是电子双缝干涉的实验。
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)的门。
这是f-CNOT门，这里的⊕是XOR门，是很经典的门
然后这样一个门的功能是：
以n=1的D-J算法为例：
a.若
b.若
汇总结果：
（这就是（-1）^f(x)的来历，不需要用到复数～）
...一波操作（纯数学）
然后我们就得到了类似于
的结果。
我不提供具体的数学表述，因为其他人已经有很完备的回答了：
下一篇：量子计算简史