量子计算的新特点

量子计算的新特点

1光子计算机的应用计算方程的过程是算子系统的量化子态的演化过程。由于量子态具有量子干涉和量子纠缠性质,使量子计算有许多不同于经典计算的新特点。经典上不同的物理态可以干涉叠加形式存在于量子计算机中,量子位之间的纠缠建立了量子“信道”,使量子计算可以沿着经典上许多不同的路径并行进行。巧妙地利用量子计算机的这些性质,可以做出经典计算机不可能做到的事。旅行售货员问题(TSP问题)一个典型的、易于描述的却难以处理的NP完全问题。假定有N个城市,旅行推销员希望找出一条行遍所有城市的路线,使总旅程最小。解这个问题的一个方法是列出连结N个城市的所有路线,从中挑出最短的一条。这种做法在当N比较小时还可行得通。事实上,对N个城市,可以有N!条旅行路线,由于,列出所有可能的路线就导致一个指数时间算法。2．态分布的意义在数学上TSP问题可用一个函数g=min(N,E)表示,其中N代表城市,E为路径,g代表所求的最短旅程。ei为第i条边的值,共有m条边,将每一边的值转换成因此,。假设一个量子系统由N个粒子组成,分别由许多不同的态矢|φi>,i=1,2,3Λ,m描写的子系统构成,每个子系统在该系统中以确定的概率出现,因此这个系统可以通过指定各子系统的态矢|φi>,以及这个子系统在系统中出现的概率描述(|φ1>,p1)、(|φ2>,P2)…(|φi>,pi)…(|φm<,pm)其中,概率pi对应于边的值,这m个态矢{|φi>,}构成正交归一集,由它们可以构成一个叠加态Ci为展开系数。TSP问题变成在所有可能的叠加态|ψ>中搜索一个特定的叠加态|g>的过程。下面论证这种变换的合理性。求解TSP问题是将m维输入表象A与n维的输出表象B的变换。A表象基矢为{|am>},B表象基矢为{|bn>},由上面的处理可知A表象中满足的完备性条件,现考虑任意态矢|Φ>在这两个表象中的联系。上式也可写为Φ(B)=SΦ(A),其中Ф(B)、Ф(A)分别是|Φ>在A表象、B表象中的表示,S是L行N列的矩阵,矩阵元Smn=<bn|am>,由于,所以这表明态矢在不同表象之间的变换是通过么正变换进行的,且维数可以不同。假设每一种可能的态矢为|x>。给出一个量子黑盒,当找到这个态g时,g=1,当结果不是g时,g=0。假设黑盒是量子的,它可以接受叠加形式的输入态,并做出响应。这个黑盒执行么正变换Ug其中|x>是n位态,|y>是单量子态。我们可以选择单量子位态,从而量子黑盒的作用是可以得出Ug|x>=(-1)g|x>,所以Ug的作用是改变态g的位相π,但对任何与|g>正交的态不作用。这一变换可用投影算子记为Ug=1-2|g><g|,这一变换有简单几何解释,Ug作用到2n维Hilbert空间中的任一矢量|x>上,就是相对与|g>垂直的超平面反射这一矢量,即态|x>在超平面上的分量保持不变,但改变沿|g>的分量符号。我们只知道黑盒对某一特殊的计算基|g>执行这一反射,但对|g>的值并不知道,我们的任务就是以最少的运算次数求出g的值。3gro经营迭代算法为求得g值,从第1步对初始态为|0…0>的n量子们施用H(n)=H⊗H⊗Λ⊗H(共n个),得到所有计算基的等权重叠加态。我们虽然不知道|g>态的值,但确实知道|g>是一个计算基态。所以这表明,如果这时将|s>投影到计算基上,得到态|g>的概率仅为。Grover迭代算法就是通过反复迭代放大要找的态|g>的概率幅,同时抑制|x≠g>态的概率幅。由于态|s>已知,利用|s>可以构造一个反射Us=2|s><s|-1,它保持态|s>不变,但反转任何与|s>正交态的符号。在几何上它保持态|s>的分量不变,但改变与|s>垂直的超平面上的分量符号。结合Ug和Us可构造一个么正变换考虑这个变换对|g>、|s>张开的平面上任一矢量的作用。由于|s>可以看做是由平面上与|g>垂直的矢量|g⊥>转过θ角。平面上的输入态|s>经T次迭代后,将被转动到与|g⊥>轴成θ+2Tθ角位置上,为了在最后测量时以高的概率得到|g>态,这个角度应接近90°,即对于足够大的N,,代入上式得经过T次迭代后,向计算基投影测得所求态|g>的概率是因此得出结论,只需大约次迭代,就可找到最短路径。可以得到指数级的加速。4法的未来研究展望综上所述可知,TSP问题的核心就是把传统的找最短路径转化为量子环境下找特定态矢的问题,从而可以利用量子环境下特殊性质把时间复杂度由传统的降低到,这仅仅是量子算法在TSP问题上的一个应用,但它带来的卓越性能和超常规的运算速度已经使人兴奋不已。虽然真正的量子计算机还没有出现,但通过上面的讨论,已经可以看到其美好的前景。目前量子算法的研究正处于一个重大突破的前夜,因为量子计算机的研制在技术上还存在很大障碍。但是,可以预测,由于传