​Deutsch-Josza算法

量子算法是量子计算落地实用的最大驱动力，好的量子算法设计将更快速推动量子计算的发展。

Deutsch-Jozsa量子算法，简称D-J算法，DavidDeutsch和RichardJozsa早在1992年提出了该算法，这是第一个展示了量子计算和经典计算在解决具体问题时所具有明显差异性的算法。

D-J算法是这样描述的：给定两个不同类型的函数，通过计算，判断该函数是属于哪一类型的函数，其可用来演示说明量子计算如何在计算能力上远超经典计算。

D-J算法所闻述的问题是：考虑一个函数f(x)，它将n个字符串x作为输入并返回0或1。注意，n个字符串也是由0和1组成，函数形式如下图所示

​

这个函数称为常数函数。如果对任意f(x)都等于0或者f(x)都等于1：

而如果f(x)=0的个数等于f(x)=1的个数，则称这个函数为平衡函数：

f(x)=0的个数等于f(x)=1的个数

下面考虑一下最简单的情况：当n=1的时候，常数函数的类型是这样的：f(0)，f(1)都指向0；或者f(0)，f(1)都指向1，而平衡函数则是各占一半。回顾问题，要解决的是给定输入和输出，如何快捷地判断f(x）是属于常数函数，或是平衡函数。

如下图所示，在经典算法中，给定了输入之后，第一步是需要判断f(0)，F(x)有两种情况，f(0)=0或者f(0)=1；当确定f(0)之后，再判断f(1)，确定了f(1)的值之后，就可以确定该函数的类型；整个过程需要两次，才可以判断函数的类型。按照这样的方式对于经典算法n个输入，在最槽糕的情况下f必须要2-1+1次才能判断出函数属于哪一类，即，最槽糕情形需要验证一半多一个数据；而如果使用量子算法，仅需一次就可以判断出结果。

通过下图所示的量子线路图来理解该算法是如何解决问题的。首先，对所有的比特都执行Hadamard门操作，然后经过黑盒子Uf，再对工作比特添加Hadamard门，然后测量。

按照实施步骤，表达形式：

1、初始化 2、使用Hadamard门来构建叠加态

3、使用Uf来计算函数f

4、在工作位上添加Hadamard门

5、测量工作位，输出结果，一次性就可以判断出结果