量子那些事儿 关注
手机版

量子计算的理论发展(四)

  1. 云栖社区>
  2. 量子那些事儿>
  3. 博客>
  4. 正文

量子计算的理论发展(四)

雪花又一年 2018-05-17 15:26:34 浏览501 评论0

摘要: Grover搜索算法和Shor质因数分解算法是量子计算中最为经典且重要的两个算法。Shor算法利用了量子傅里叶变换和一些数论的理论,非常令人震撼,其在破解银行等领域的密钥方面的作用一直被视为量子计算机的重要应用之一。

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

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

zFAAAAAElFTkSuQmCC

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算法逻辑门如图:

wMPZRLE2QpcawAAAABJRU5ErkJggg==

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

8PrfE7qLkpq9EAAAAASUVORK5CYII=

这里的f(x)是Uw引入的函数,当|x>是我们要搜索的对象|w>时,f(x)的值为1;当|x>不是我们要搜索的对象|w>时,f(x)的值为0;我们舍弃辅助比特(|0>-|1>)来观察f(x)的作用,得到


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

代入f(x),得到

4YQAAAABJRU5ErkJggg==

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

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>}

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

AAAAABJRU5ErkJggg==

|s'>是和待搜索量|w>正交的2^n-1维超平面,经过Hadamard变换得到的|s>经过Uw变换相当于对|s'>做轴对称,然后在经过Us变换,相当于对|s>做轴对称,这样每次完成这个循环,|s>向|w>前进theta角,而theta角满足:

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门实现。对于两比特的搜索,最终完整的电路如图所示:

x8TWODEXCBSIQAAAABJRU5ErkJggg==

大家可以自己演算一下两比特的搜索需要几步完成。


原文发布时间为:2017.02.01
本文作者:Golden Horqin
本文来源:知乎,如需转载请联系原作者。

【云栖快讯】你想见的Java技术专家都在这了,向大佬提问,有问题必答  详情请点击

网友评论

雪花又一年
文章1321篇 | 关注43
关注
快速、完全托管的TB/PB级数据仓库解决方案,向用户提供了完善的数据导入方案以及多种经典的分... 查看详情
阿里云流计算(Aliyun StreamCompute)是运行在阿里云平台上的流式大数据分析... 查看详情
提供一种性能卓越、稳定、安全、便捷的计算服务,帮助您快速构建处理能力出色的应用,解放计算给服... 查看详情
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
阿里云总监课正式启航

阿里云总监课正式启航