以下是网学网为您推荐的其他类别-傅里叶变换在量子计算中的作用，希望本篇文章对您学习有所帮助。
第三章 Shor算法 3.1 Shor算法的步骤 大数因子分解的shor量子算法的主要步骤，大数因子分解问题为：N为已知大奇数，N=n1n2，求n1和n2。 shor算法的主要步骤如下： 步骤１、随机取正数a,a<N，且与N互质，即gcd(a,N)=1，这可由辗转相除法得出。 步骤２、定义f(x)=axmodN，可看出f(x)是一个周期函数，若周期为r,则axmodN=ax+rmodN，故ar=1modN，求f(x)的周期r,r应为偶数，如果r为奇数，重新取a、并重新求r，直到r为偶数为止。 步骤３，求n1和n2,(ar/2)2-1=0modN, (ar/2+1)(ar/2-1)=0modN,用辗转相除法求ar/2+1和N的最大公约数，此数即为n1。 3.2 Shor算法的例子 下面看一个简单的例子，令N=15,a=7,计算出7xmod15的值如表所示。 x 5xmod9 0 1 1 7 2 4 3 13 4 1 5 7 6 4 7 13 8 1 9 7 10 4 11 13 12 1 、 、 、 、 、 、 从表中可以看出r=4。 ar/2+1=50,n1=gcd(50,15)=5,ar/2-1=48,n2=gcd(48,15)=3, 3*5=15。 如果r不为偶数则重新选择a值。Gcd函数是求最大公约数。 3.3Shor算法的时间 上面各步中的主要计算是辗转相除。如果数字大并且复杂的话，就不能用辗转相除法。因为计算f(x)和求f(x)的周期、辗转相除的时间复杂为O(n2),计算f(x)的时间复杂度为O（n2(lgn)(lglgn)）。所以，Shor量子算法的时间复杂度为O(n2(lgn)(lglgn))。 我们用傅里叶变换来求周期，接下来我将重点讲述怎样求f(x)的周期，因为是用傅里叶变换来求f(x)的周期，在求周期的同时，我也将着重讲述一下量子傅里叶变换。 第四章 量子傅里叶变换 4.1离散傅里叶变换 离散傅里叶变换（DET）的表达式可以是 2m-1 F（k）= (1/2)m/2∑ f(n)Wnk,k=0,1,…,2m-1,式中W=e-2Ωi/2m, n=0 上式可写下面的形式 F（0） f(0) [ F（1） ]=T[ f(1) ] 式中 … … F（2m-1） f(2m-1) 1 1 1 … 1 1 W W2 … W2m-1 1 W2 W4 … W2(2m-1) T=1/2m/2 [ … … … … … ] 1 W2m-1 W2(2m-1) … W(2m-1)2 T是幺正变换。 4.2离散傅里叶变换的例子 现在看一个例子，令x=011，则 7 QFT：|011>→(1/8)1/2∑ e6Ωci/8|c>=(1/8)1/2 (|000>+ e6Ωi/8|001>+ e12Ω C=0 i/8|010>+ e18Ωi/8|011>+ e24Ωi/8|100>+ e30Ωi/8|101>+ e36Ωi/8|110>+ e42Ωi/8|111>= (1/8)1/2 (|000>+ e3Ωi/4|001>- e1Ωi/2|010>+ eΩi/4|011>- |100>- e3Ωi/4|101>+ eΩi/2|110>- eΩi/4|111>). QFT可由两种量子门实现，所用的门的数量为m(m+1)/2.这两种门中的一种是H门，另一种是2个量子位的相移门。 |
| 本站发布的计算机毕业设计均是完整无错的全套作品，包含开题报告+程序+论文+源代码+翻译+答辩稿PPT |
本文选自计算机毕业设计http://myeducs.cn
|
