量子计算的理论发展（四）-阿里云开发者社区

量子计算的理论发展（四）

2018-05-17 1604

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

Grover搜索算法和Shor质因数分解算法是量子计算中最为经典且重要的两个算法。Shor算法利用了量子傅里叶变换和一些数论的理论，非常令人震撼，其在破解银行等领域的密钥方面的作用一直被视为量子计算机的重要应用之一。不过笔者认为Grover算法的意义可能来的更为广泛，首先它的算法复杂度被证明是最优的搜索算法，其次Grover算法可以加速一切NP问题。

算法复杂度理论认为解决问题的范围大概是这样：

P problem指的是可以多项式时间解决的问题，NP problem是可以多项式时间验证的问题，NP包括P，但是为了方便，接下来提到的NP问题特指能够多项式时间验证但不能多项式时间解决的问题；NP complete是NP中最难解决的问题，如果它们被多项式时间内解决，那么所有NP问题都可以被多项式时间解决。BQP是量子计算机可以在多项式时间内解决的问题，一般认为BQP大于P但小于NP，比如质因数分解暂时可以认为是一个NP问题（学术界没有定论），那么Shor算法解决的就是BQP中不在P problem那个范围内的问题了。

Grover算法并没有达到多项式时间的复杂度，经典算法的复杂度是 $O\left( N \right)$ ，它的时间复杂度是 $O\left(\sqrt N \right)$ ，但是它可以加速一切NP问题（这是因为所有NP问题都可以归并为多项式时间验证的搜索问题），它的应用范围就更加广泛了，像现在云计算和大数据处理，这种根号级别的提速也是非常可观的。

Grover算法逻辑门如图：

前面和DJ算法类似，经过Hadamard变换和Quantum Oracle (Uw)，得到

$U_{w} : |x>\rightarrow (-1)^{f(x)}|x>$

代入f(x)，得到

按照如图电路，接下来我们定义

$U_{s} =H^{(n)}(2|0><0|-I)H^{(n)}=2|s><s|-I$

其中 $|s>=H^{(n)}|0>=\frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n-1}{|x>}$

整个过程可以通过一个几何图像了解

$sin\theta =<s|w>=\frac{1}{\sqrt{2^n}}$

我们将这一步骤重复T次，最终我们希望 $(2T+1)\theta =\pi/2$ ，这样就搜索到了想要的|w>，根据计算，当T= $\frac{\pi}{4} \sqrt{2^n}$ 时，搜索到|w>的概率为 $P=|<w|\psi _T>|^2=sin^2(2T+1)\theta=1-O(\frac{1}{2^n} )$ ，所以量子搜索的次数为 $\frac{\pi}{4} \sqrt{2^n}$ 次，而经典搜索是 2^n 次，相比之下量子搜索实现了根号级别的加速。

如果要同时有r项满足搜索条件，我们只需要记 $|\varpi >=\frac{1}{\sqrt{r}} \sum_{i=1}^{r}{|w_i>}$ ,这是只需要搜索 $\frac{\pi}{4} \sqrt{\frac{2^n}{r} }$ 次，但搜索的前提是我们知道r是多少，不然搜索次数不对的话搜索到要找的对象的概率可能是0，一般还会使用量子计数算法先得到求解的数目。

最终电路的实现，主要考虑 $U_{s} =H^{(n)}(2|0><0|-I)H^{(n)}$ ，我们知道 I-2|0><0| 表示的意义是当输入比特都为|0>时做相位翻转，这个可以通过n比特相位控制门（n-1个比特都为1时最后一个比特相位翻转，实际上也是整个比特串相位翻转）外加非门实现，而相位控制门可以通过控制非门和Hadamard门实现。对于两比特的搜索，最终完整的电路如图所示：