上一篇文章介绍了Deutsh-Jozsa算法，虽说Deutsh-Jozsa算法的应用不广泛，但是我们还是来尝试实现这个算法。一方面，为了是进一步熟悉Qiskit；另一方面，上一篇文章中我们做了一个假设：默认可以把任意函数f，通过量子电路转化为 U_f ，其中 U_f 可以完成转换 (x，y) \rightarrow (x,y\oplus f(x) ， \oplus 是模二加。现在我们来讨论下，为什么这个假设是成立的。

1 量子计算机实现经典计算机功能

我们首先要回答的问题是：量子计算机能否实现经典计算机的功能？答案是可以的。为解答这个问题。我们要明白经典计算机逻辑电路的逻辑门中的与非门（NAND）和或非门都是通用逻辑门，即任何逻辑门都可以用与非门或者或非门实现。因此，如果我们可以用量子逻辑门实现与非门的功能，那么就说明量子计算机可以完全实现经典计算机的功能。

为此，我们介绍两个多量子比特逻辑门，Toffoli门和Fredkin门。

1.1 Toffoli门

Toffoli门，是一个三量子比特逻辑门，他有两个控制比特，一个目标比特，其矩阵表示为：

Toffoli门的矩阵表示

Toffoli门的功能为，如果两个控制比特都为1，则将目标比特翻转。

即输入（a,b,c），输出 (a,b,c\oplus ab)

同时可以看出，Toffoli门的逆就是其本身，对任何输入执行两次Toffoli门状态保持不变。

Toffoli门真值表与电路表示

1.2 利用Toffoli门模拟与非门

使用Toffoli门实现与非门：只需要令目标比特c取为1，则当a=b=1时，目标比特的输出就为0；若a和b中存在0，则目标比特的输出为1。同时，可以看出Toffoli门可以执行扇出功能，只需要取b=1,c=0。

Toffoli门模拟与非门

因此，Toffoli门的存在，使得量子计算机有能力完成经典计算机可以完成的任何任务。

1.3 Fredkin门

Fredkin门输入为三个量子比特 （a,b,c） ，输出也是三个量子比特 (a^{'},b^{'},c^{'}) ，其中c为控制比特，它的值不发生变化，即 c^{'}=c 。当 c=1 时，剩下两个比特的值互换 a^{''}=b,b^{'}=a 。 c=0 时，其余两个比特值保持不变 a^{''}=a,b^{'}=b 。

易知，Fredkin门可逆，且逆为其本身。

Fredkin门真值表及电路表示

下图说明了如何用Fredkin组成 与门，非门。

使用FredKin门组成与门（左），非门（右）

其中第二个门，也同时具有扇出的功能。因此，Fredkin门可以通过级联模拟任何经典电路。

1.4 实现 U_f

注意经典逻辑门和量子逻辑门的一个很大区别：与门，与非门等部分经典逻辑门是不可逆的，即无法从输出推出输入，而量子门都是可逆（所有的量子门都可以表示为酉矩阵，而酉矩阵无疑是可逆的）。

为了使用可逆的量子门模拟不可逆的经典门，我们需要允许：

（a）：允许我们使用辅助量子比特输入到量子门（如Fredkin 门）中。在上面的介绍中，我们已经使用了一些辅助比特来实现经典逻辑门的功能。

（b）：量子门（如Fredkin 门）的输出包含一些“垃圾”比特，

这两类比特对于计算来说并不重要，他们都重要性体现在使得计算是可逆的。

至此，对于任意给定的计算 f(x) 的经典电路，我们都可以构建一个完全由Fredkin门组成的可逆的量子电路，使得当该量子电路的输入为 (x,a) 时，输出为 (f(x),g(x)) 。这里的a表示辅助量子比特， g(x) 为输出的“垃圾”比特。

虽然我们可以实现 f(x) ，但是不幸的是，这种计算会产生我们不想要的垃圾比特。在经典计算中，这无关紧要，我们只需要舍弃这些我们用不到的比特就好了。但对于量子计算机，取值依赖于x的垃圾比特通常会破坏对量子计算至关重要的干扰特性（我们在未来会再讨论这个话题）。好在，我们可以通过对电路的修改，使在计算过程中产生的垃圾比特处于一个标准态，以规避这种破坏。

首先，因为后续可以通过把X门（类似于经典非门）把辅助比特调整（如从0→1）到我们想要的状态，我们先把所有辅助比特的初始值都设为0。此时对这 （x,0) 两个比特使用CNOT门将会得到 (x,0)\rightarrow (x,x) ，这是一种扇出或者复制操作。但是注意，量子计算中是没有无法复制量子比特的，我们会在1.5节讨论CNOT门与复制的问题。

我们之前已经讨论了量子计算机可以实现 (x,t) \rightarrow (f(x),g(x)) ，其中t为辅助比特。由于有X门，所以上述式子调整为 (x,0)\rightarrow (f(x),g(x)) 。又我们可以通过CNOT非门复制一个x，因此式子可以变为 (x,0,0)\rightarrow (x,f(x),g(x)) 。

注意，上式是一种非常有效的来操作可逆电路的方式，因为实际上它提出了一种“非计算”的方式让我们以很小的代价去摆脱垃圾比特。我们来看看接下来要怎么操作。

首先，我们创建一个四个量子比特的寄存器 （x,0,0,y) ，其中第二个寄存器用来存储计算结果，第三个寄存器为计算提供计算空间。我们假设一开始第四个寄存器中是一个任意的状态y。

应用计算 f 的可逆电路，我们得到 （x,f(x),g(x),y) 。接下来我们使用CNOT门，将 f(x) 加到第四个寄存器上（注意CNOT门的操作可以表示为 (a,b)\rightarrow (a,a\oplus b) ），得到 (x,f(x),g(x),y\oplus f(x)) 。此时，由于所有的计算都是可逆的，这也就是说，通过f的逆电路我们得到 (x,0,0,y\oplus f(x)) 。通常，我们在函数求值的描述中省略辅助比特0，只将电路的动作写成 (x,y)\rightarrow (x,y\oplus f(x)) 。

一般情况下，我们把通过这种修改的计算f的电路称为计算f的可逆电路，尽管可能存在许多别的可逆电路也可以计算 f 。

到这里我们就回答了篇首提出的问题——如何构建 U_f 。

练习：构造一个可逆电路，当输入x、y两位时，输出 (x, y, c, x⊕y) ，其中c为x、y相加时的进位。

欢迎大家把自己的想法写在评论区。

1.5 CNOT门与复制操作

我们曾强调过：量子计算机中没有复制操作，这也是量子计算机与经典计算机的一个非常重大的差异。那么这种不可复制性的本质是什么？

量子不可克隆定理（No-Cloning Theorem）：是指量子力学中对任意一个未知的量子态进行完全相同的复制的过程是不可实现的。

证明：假设存在 U ，可以完成克隆任务。即 U|\psi>\otimes |0> = |\psi>\otimes |\psi> 。即将状态 |\psi> 克隆并存储到一个寄存器内，我们这里假设这个寄存器初态为0。即 U|\psi>\otimes |0>=|\psi>\otimes |\psi> 。现假设 |\psi> = a|0>+b|1> ，那么有 U|\psi>\otimes |0>=U(a|0>\otimes |0>+b|1>\otimes |0>)=aU|0>\otimes |0>+bU|0>\otimes |1>

既然U是克隆算符，那么应该有 U|0>\otimes|0> = |0>\otimes |0> ， U|1>\otimes |0> = |1>\otimes|1>

于是有 U|\psi>\otimes |0> = a|0>\otimes |0> + b|1>\otimes |1> 。

但另一方面， U|\psi>\otimes|0>=|\psi>\otimes|\psi>=a^2|0>\otimes|0>+b^2|1>\otimes|1>+ab|0>\otimes|1>+ab|1>\otimes|0>

除非a，b之中一个为0一个为1，否则显然上面两个式子是矛盾的。

而当a,b分别是0和1时，我们很显然可以直接制备出相同的态。即我们无法对一个未知的量子态进行完全相同的复制。

直观的理解，我们想知道一个未知态的信息，那么只能对其进行测量，但是对量子态进行测量会导致其坍缩到其某一个本征态，从而导致失去部分信息，也就是说我们没法知道这个量子态的全部信息，也就无法对其进行复制。

现在我们回来看CNOT门

从CNOT的变换 |A,B>\rightarrow |A,A\oplus B> 可以看出，当A=0或者1，B=0时，输出为 |A,A> 即实现了对A的复制。

但是若A取态 |A>=|\psi>=a|0>+b|1> 则此时态为 a|00>+b|10> ，运用CNOT门后态为 a|00>+b|11> 。

而 |\psi>|\psi> = a^2|00>+ab|01>+ab|10>+b^2|11>

也就是说，除非ab=0，否则我们并没有复制出 |\psi> 。

2 Deutsh-Jozsa算法实现

我们先来实现1比特的D-J算法。

2.1 一比特的常数函数以及 U_f 的实现

一比特的平衡函数f(x)=1，对于输入的|0>或者|1>都输出1。接下来给出如何实现$U_f$。

首先引入需要的包

import numpy as np
from qiskit import QuantumCircuit,assemble,Aer
from qiskit.quantum_info import Statevector
from qiskit.visualization import array_to_latex
from qiskit import transpile
from qiskit.providers.aer import QasmSimulator

构建 U_f ，实现 (x,y) \rightarrow (x,y\oplus f(x))

# 一比特常数函数 f(x) = 1
def U_f(circ,x,y):
circ.initialize(x,0) # q_0 代表 x
circ.initialize(y,3) # q_3 代表 y,此时状态为（x,0,0,y）
circ.cx(0,1) # （x,x,0,y)

circ.x(2) # (x,x,1,y) <- (x,g(x),f(x),y)
circ.cx(2,3) # (x,x,1,1⊕y) <- (x,g(x),f(x),y⊕f(x))
circ.swap(1,2) # (x,1,x,1⊕y) <- (x,f(x),g(x),y⊕f(x))
#到这里我们就得到了文中提到的(x,f(x),g(x),y⊕f(x)) ，接下来我们来设计逆电路

circ.swap(1,2) #（x,x,1,1⊕y) <- (x,g(x),f(x),y⊕f(x))
circ.x(2) # （x,x,0,1⊕y) <- (x,g(x),0,y⊕f(x))
circ.cx(0,1) #(x,0,0,1⊕y) <- (x,0,0,y⊕f(x))
#到这里，我们得到目标的（x,0,0,y⊕f(x))
return circ

# (x,0) -> (x,1)

x = [0,1] #设置初态 x = |1>
y = [1,0] #设置初态 y = |0>
Circ = QuantumCircuit(4,4)
Circ = U_f(Circ,x,y)
Circ.barrier()
Circ.measure(range(0,4),range(0,4))
Circ.draw('mpl')

注意这里是严格按照文中给出的流程去实现 U_f 。否则，可以看到其实第二个量子比特是无用的，因此可以对电路做出简化，这里留个读者去完成。

U_f

对电路进行模拟。

# 模拟
Sim = QasmSimulator()
complied_circuit = transpile(Circ,Sim)
job = Sim.run(complied_circuit,shots=100)
result = job.result()
counts = result.get_counts(Circ)

print(counts)

结果

{'1001': 100} # 中间两个0是辅助（垃圾)量子比特。从左到右，最后一个1 是x的状态，第一个1是 y⊕f(x)

如果我们设置 x = [1,0] 即态|0>，则输出为：

{'1000': 100}

这里实现的是 f(x) = 1 相应的电路。另外， f(x) = 0 的电路也应该很好实现了，只需要去掉 q_2 的X门。平衡函数的话，只需要对x执行一次X门，或者干脆什么都不操作，直接输出就行了，这里就不一一实现了，有兴趣的读者可以自己试一下。

2.2 一比特输入的Deutsh-Jozsa算法实现

有了 U_f ，剩下的部分我们就很好实现了。首先我们再来看看Deutsh-Jozsa算法的流程。

1比特Deutsh-Jozsa算法

也就是说只需要在 U_f 前后加一些H门就好了。

完整代码：

# 一比特常数函数 f(x) = 1
import numpy as np
from qiskit import QuantumCircuit,assemble,Aer
from qiskit.quantum_info import Statevector
from qiskit.visualization import array_to_latex
from qiskit import transpile
from qiskit.providers.aer import QasmSimulator

def U_f(circ):
#circ.initialize(x,0) # q_0 代表 x
#circ.initialize(y,3) # q_3 代表 y,此时状态为（x,0,0,y）
circ.cx(0,1) # （x,x,0,y)

circ.x(2) # (x,x,1,y) <- (x,g(x),f(x),y)
circ.cx(2,3) # (x,x,1,1⊕y) <- (x,g(x),f(x),y⊕f(x))
circ.swap(1,2) # (x,1,x,1⊕y) <- (x,f(x),g(x),y⊕f(x))
#到这里我们就得到了文中提到的(x,f(x),g(x),y⊕f(x)) ，接下来我们来设计逆电路
#事我们得到目标的（x,0,0,y⊕f(x))
circ.swap(1,2) #（x,x,1,1⊕y) <- (x,g(x),f(x),y⊕f(x))
circ.x(2) # （x,x,0,1⊕y) <- (x,g(x),0,y⊕f(x))
circ.cx(0,1) #(x,0,0,1⊕y) <- (x,0,0,y⊕f(x))
return circ

# (x,0) -> (x,1)

def OneBit_Deutsh_Jozsa():
Circ = QuantumCircuit(4,4)
Circ.h(0)
Circ.x(3)
Circ.h(3)
Circ = U_f(Circ)
Circ.h(0)
Circ.barrier()
return Circ

Circ = OneBit_Deutsh_Jozsa()
Circ.measure(range(0,4),range(0,4))
Circ.draw('mpl')

根据我们在上一篇推导的结果

系统的末态为：

由于常数函数为 f(x)=1 ，结果应该为 |\psi_3>= - |0>[\frac{|0>-|1>}{\sqrt{2}}] 。其中负号是根据上一篇中的 |\psi_2> 的公式计算出来的。

可以看出，如果是常数函数，那么测量的结果应为|10>，|00>，概率分别为50%。在这里考虑到两个辅助量子比特那么结果应该为|1000>，|0000>，概率分别为50%。我们对电路进行模拟：

# 模拟
Sim = QasmSimulator()
complied_circuit = transpile(Circ,Sim)
job = Sim.run(complied_circuit,shots=100000)
result = job.result()
counts = result.get_counts(Circ)
print(counts)

结果为:

{'1000': 50017, '0000': 49983}

此外，我们来看一下Qiskit推导出来的系统末态：

注意：在Qiskit中使用state需要删除measure。

state = Statevector.from_int(0,2**4)
state = state.evolve(Circ)

state.draw('latex')

输出为：

符合我们推导的结果。

2.2 四比特输入的Deutsh-Jozsa算法实现

我们接下来实现一个四比特输入的平衡函数的D-J算法。

考虑平衡函数奇数偶数判断函数，如果输入为偶数则输出1，输入为奇数则输出0。现在我们首先分析如何在经典电路中实现这个函数。

考虑到转化为二进制后，最低位为0时，那么一定为偶数，最低为1时，一定为奇数，那么电路就很好实现了，只需要在最低位添加一个非门就OK了。所以实际上，这可以转化为一个1bit电路。为了普遍考虑，我们还是实现下这个四比特输入的电路。

import numpy as np
from qiskit import QuantumCircuit
def U_F(Circ):
Circ.barrier()
Circ.cx(0,4) # 0是低位， 4用于存 f(x)，先复制一份x
Circ.x(4) # f(x) , 根据低位判断是否为偶数

Circ.cx(4,5) # f(x),y⊕f(x)
#此时状态为 x(0),x(1),x(2),x(3),f(x),y⊕f(x)
#逆电路
Circ.x(4)
Circ.cx(0,4)
#此时状态为 x(0),x(1),x(2),x(3),0,y⊕f(x)
Circ.barrier()
return Circ

def D_J_4():
Circ = QuantumCircuit(6,6)
Circ.h(0)
Circ.h(1)
Circ.h(2)
Circ.h(3) #输入经过H门
#用于存f(x)，
Circ.h(5) #用于存y
Circ = U_F(Circ)

Circ.h(range(0,4))
Circ.barrier()
return Circ


Circ = D_J_4()
Circ.draw('mpl')

系统末态：

from qiskit.quantum_info import Statevector
state = Statevector.from_int(0,2**6)
state = state.evolve(Circ)
state.draw('latex')

结果为：

根据前一篇文章的分析，我们知道当输出的前n个比特至少存在一个处于|1>，那么为平衡函数，否则为常数函数。观察这个系统末态得知前n个比特这里是前四个比特为|0001>。因此这是一个平衡函数。符合我们的做出的设置（奇数偶数判断函数）。

3 总结与问题

本篇文章为大家介绍了Toffoli门和Fredin门，以及他们可以模拟任何经典电路的能力。介绍了如何构建”计算f的可逆电路“。同时带大家实现了一比特和四比特的Deutsh-Jozsa算法。在实现过程中我们发现，Deutsh-Jozsa算法本身并不难实现，难点在于如何使用量子电路去模拟经典电路，以及处理其中出现的辅助比特以及垃圾比特，这也是量子计算机和经典计算机的一个很大区别，表现为经典电路基本上是不可逆的，而量子电路都是可逆的。

接下来给大家带来一个思考题：

我们再次观察上文四比特的D-J电路，发现 q_0 似乎只经过了两次H门，并参当两次CNOT门的控制比特。那么作出简单的推断，输出的 q_0应该为0呀，为什么结果却是1？

欢迎大家在评论区讨论。

PS：如有错误，欢迎指正。