量子逻辑门是幺正的,所以量子计算应该是可逆的。经典计算机之所以不可逆,
是因为存在能量耗散[26 ,27 ]
量子计算与量子逻辑门_百度文库
wenku.baidu.com/view/6dd5bc63caaedd3383c4d350.html
轉為繁體網頁
轉為繁體網頁
[PDF]
量子算法与量子计算实验 - 物理学进展
pip.nju.edu.cn/Home/DownloadPDF/538
轉為繁體網頁
轉為繁體網頁
phymath999: irreversible processes are path dependent ...
phymath999.blogspot.com/2013/04/irreversible-processes-are-path.html
[PDF]
能量不滅. 宇宙總能量不變. 能量既不消失也不能創造. 各種能量可經物理或化學變化互相轉換 ..... 可逆擴張. 無線多步. -1.39. 1.39. 可逆壓縮. 0. -1. -2. 1. 0 q/P. 1. V. 1. 0. 循環. 1. 循環. 2 ... 原狀. ❖ 所有真實過程都是不可逆(不可能操作無限多步) ...
熵變化
ocw.aca.ntu.edu.tw/ocw_files/099S125/ch10.pdf
缺少字詞： 幺
[PDF]
目前，量子计算机方面的. 研究工作非常活跃，而关于酉变换的量子线路实现复杂性是一个重要的研究方 ..... 大概消耗的能量为500 ln 2. B k T. ，远远大于 ... 在量子计算中，由于操作是幺正变换，所以量子逻辑门都是可逆的，进而. 量子计算机也是可逆的 ...
北京大学 - 清华大学
www.tsinghua.edu.cn/publish/.../Bachelor%20thesis.pdf
轉為繁體網頁
轉為繁體網頁
第21 卷 第2 期物 理 学 进 展Vol. 21 ,No. 2
2001 年6 月PROGRESS IN PHYSICS J un. ,2001
文章编号:1000O0542 (2001) 02O0183O33
收稿日期:2000O09O23 ;修收日期:2001O02O23
基金项目:国家自然科学基金、中国科学院和国家科技部基础性研究特别资助
量子算法与量子计算实验
赵志 冯芒 詹明生
(中国科学院武汉物理与数学研究所
波谱与原子分子物理国家重点实验室,武汉 430071)
摘 要: 从量子体系的基本特性出发,介绍了量子计算的基本概念和物理背景,系统阐述
了几种主要的量子算法以及量子计算在实验方面的发展现状。对比经典计算机,讨论了量子
计算机的优越性、实现量子计算的困难和以期克服的途径。
关键词: 量子算法;量子计算;纠缠;相干
中图分类号: O365 文献标识码: A
1 引 言
当代计算机的理论基础是Turing[1 ] 、Church[2 ]等人在三十年代提出的关于可计算函
数和不可计算函数之区分的一些纯数学的命题。其核心是通用Turing 机理论,即用
Turing 机可模拟任何计算过程。尽管这些数学命题与物理毫不相干,但当人类第一台计
算机建成之时,计算便成了通过计算机这种物理装置完成的一个实实在在的物理过程。
物理学的发展使计算机日新月异,而物理学的规律同时也给了计算机以本质上的约束。
统计表明,近五十年来,尽管计算机的速度平均每两年翻一番,但其元件尺寸却平均每两
年缩小一倍。这种微型化的趋势正使得计算机发展逐渐逼近经典物理学的极限。当人们
终将面对尺寸仅为纳米量级的超微型电脑元器件时,计算机信息的储存、传输和处理都将
在原子层面上按照量子力学的原理进行。另一方面,对比用宏观客体状态表示数和按照
经典物理定律运行的现有的经典计算机,人们自然联想到用微观体系状态表示数和按照
量子力学定律运行的新型计算机。由此引申出近年来科学前沿的一个热门课题:量子计
算与量子计算机[3 ] 。
早在半个世纪之前,量子力学的先驱者们就试图通过研究简单的量子门操作和数个
量子位的纠缠( Entanglement) 过程,弄清经典与量子世界的界限。八十年代初,美国阿贡
国家实验室的Benioff 证明[4 ] ,一台计算机原则上可以纯粹的量子力学方式运行。随后,
英、美及以色列的科学家们开始对量子计算机进行研究,以期弄清它们同人们正广泛使用
的经典计算机的区别。著名物理学家、诺贝尔物理学奖得主Feynman 教授曾对这一问题
表现出极大的关注,并就此作了一次精采的专题演讲[5 ] 。到目前为止,尽管我们还不敢
肯定量子计算机在解决所有问题时一定都比经典计算机快,但它所具备的以下特性,却是
经典计算机不能比拟的: (1) 量子计算能真正模拟一个量子系统的演化,因为它本身的运
算方式就是严格依照量子力学的原理进行; (2) 量子计算的操作对象是量子迭加态和纠缠
态。如果以纯态表示数,迭加态则表示多个数。对量子迭加态的操作,意味着对多个数同
时多路操作运算,即所谓“量子并行计算”。因此,它能快速有效地解决许多特殊问题。
正是有了这些特性,量子计算与经典计算有了很大的不同。在本文中,我们将介绍各
种量子算法。通过了解这些算法,我们将能体会到量子计算的巨大威力。
1. 1 纠缠,EPR 佯谬与Bell 不等式
纠缠是量子力学最重要的特征之一,同时也是进行量子计算最有效的资源。1935
年,SchrÊdinger[6 ]首先给出了纠缠态的定义:由空间分离的两个子系统构成的纯态,如果
系统波函数不能分解为两个子系统波函数的乘积,那么这样的波函数表示的态称作两个
粒子的纠缠量子态。
1935 年,Einstein ,Podolsky 和Rosen[7 ] [简称EPR]首先讨论了一个具体的两粒子纠
缠量子态。在这个著名的思想实验中,两粒子的纠缠量子态为:
Ψ > = Σa , b
δ( a + b - c0) a > b > (1)
其中a , b 分别为粒子1 和粒子2 的位置或动量, C0 为常数。这个纠缠态的一个最明显
的特征是:其中任何一个子系统的物理量的观测值(位置或动量) 都是不确定的。但是,如
果其中的一个子系统的物理量的观测值处于一个确定的值,那么我们可以百分之百地确
定另外一个子系统的相应物理量的观测值。
EPR 的思想实验本质上可以约化为自旋为1/ 2 的粒子1 和自旋为1/ 2 的粒子2 构成
的量子系统。| ↑> 代表自旋向上,而| ↓> 代表自旋向下。初始时刻两粒子处于单重态,
然后向相反的方向自由地传播。
ψ( t = 0) > = ( ↑ >1 ↓ >2 > - ↓ >1 ↑ >2) / 2 (2)
这个量子态的一个明显特性就是它是纠缠的。如果我们应用SternOGerlach 装置分
别在^n1 和^n2 方向对粒子1 和粒子2 进行测量,那么,根据量子力学,测量结果乘积的期
望值为
Eψ( ^n1 , ^n2) ≡< ψ (^σ1 ·^n1) (^σ2 ·^n2) ψ > = - ^n1 ·^n2 (3)
其中, ^n1 = ^n2 代表两粒子完全关联,其它情况代表统计关联。在完全关联的情况下,如果
粒子1 的自旋向上,那么粒子2 的自旋向下;反之亦然。然而, EPR 认为,量子力学对这
两个粒子纠缠态的描述是不完备的。根据EPR 的观点,有四个前提可以推导出量子力学
的不完备。其中第一个来源于量子力学,其它三个则是关于局域性,现实性和完备性的合
理假设。
(A) 完全关联:如果对粒子1 和粒子2 沿着相同的方向进行测量,那么粒子1 和粒子
2 的自旋方向完全相反。
184 物理学进展21 卷
(B) 局域性:“由于在测量过程中没有相互作用的发生,因此,对其中一个粒子的测量
不会引起另外一个粒子的任何改变。”
(C) 实在性:“假如在没有干扰一个系统的条件下,我们能够准确地预言这个系统物
理量的期望值(几率为1) ,那么必然存在一个客观的实在与这个物理量相对应。”
(D) 完备性:“在一个完备的物理理论中,客观现实的每一个元素都存在一个相应的
描述。”
EPR 的结论可以推导如下:由于完全的关联(A) ,因此,对粒子1 的测量可以准确地
知道粒子2 的自旋;而由(B) 可以知道,对粒子1 的测量没有对粒子2 产生任何影响;再由
(C) 可以知道,粒子2 的自旋分量是一个客观的实在元素。由于对粒子1 的测量可以在
任意方向,因而,粒子2 的任意自旋分量也是一个客观的实在元素。然而,在量子力学中,
是否不存在这样一个描述自旋为1 和2 系统的量子态,所有的自旋分量都有确定的值。
因此,由(D) 可以知道,量子力学的描述是不完备的。至少对这样的纠缠态的描述是不完
备的。单个量子系统可以有其本身的特性,但是对于一个系综来说,系综的量子态仅仅能
给出它们的统计描述。因而,量子力学需要其它的“隐变量”来对量子系综给予完全的描
述。
随后,人们也一直试图发现一个隐变量理论[8 ,9 ]来描述量子力学。但是,在1964 年,
Bell[10 ]发现,在某些条件下,隐变量理论与量子力学给出不同的预言。在考虑隐变量的条
件下,Bell[10 ]提出了一个著名的不等式,这个不等式可以用来检验隐含变量理论和量子力
学统计预言的正确性。应用这个不等式,Bell 指出,对于两粒子纠缠态的统计关联, EPR
的观点和量子力学的解释存在一个矛盾,量子力学的统计预言将与这一不等式相违背。
在Bell 的理论中,假设存在描述这一对粒子的完备态,用λ表示所有的客观实在的
元素。那么,根据EPR 的四个前提, ^n1 和λ确定了粒子1 的测量结果Aλ( ^n1) ,同样^n2
和λ确定了粒子2 的测量结果Aλ( ^n2) ,并且Aλ( ^n1) = ±1 和Aλ( ^n2) = ±1 。
假设ρ表示λ的几率分布,则测量结果^σ1·^n1 和^σ2·^n2 乘积的期待值为
Eρ( ^n1 , ^n2) =∫Aλ( ^n1) Aλ( ^n2) dρ (4)
Bell 特别强调指出, Aλ( ^n1) 与^n2 无关,而Aλ( ^n2 ) 与^n1 无关。这与EPR 要求的前
提(B) 相一致。
Bell 证明,在任意三个方向^n1 , ^n2 , ^n3 对粒子1 和粒子2 进行测量,上面方程的期待
值存在一个简单的数学公式:
Eρ( ^n1 , ^n2) - Eρ( ^n1 , ^n3) - Eρ( ^n2 , ^n3) - 1 ≤0 (5)
这个不等式称作Bell 不等式。
然而,根据量子力学,存在某些方向^n1 , ^n2 , ^n3 ,方程(3) 给出的期待值与这一不等式
相违背。例如,假设^n1 , ^n2 , ^n3 处于x - z 平面,与z 方向的夹角分别为0 ,π/ 3 和2π/ 3 ,
那么,根据前面的公式,
Eρ( ^n1 , ^n2) - Eρ( ^n1 , ^n3) - Eρ( ^n2 , ^n3) - 1 =
1
2
(6)
这一等式与前面的Bell 不等式相违背。因此,隐变量理论描述的“完备态”给出的统
1 期赵志等:量子算法与量子计算实验185
计测量结果与量子力学给出的测量结果相矛盾。已有大量的实验[11～14 ]来对不等式(5)
进行了检验,所有的实验结果都支持了量子力学的解释。
延伸两粒子纠缠态到三粒子的纠缠态(称作GHZ 态[15 ] ) , Greenberger[16 ,17 ]等发现,
即使在纠缠态完全关联的情况下,EPR 观点与量子力学的预言也存在一个矛盾。GHZ 态
的实验实现[18 ]及GHZ 态量子非局域的测试[19 ]都说明了量子力学的正确性。
最近,特别是进入九十年代,人们不仅研究纠缠的奇妙性质,而且还把它当作有用的
资源用来进行量子通讯[20 ,21 ]和量子计算[22～24 ] 。EPR 的思想实验以及后来的Bell 理论
已经被看作现代量子信息理论的开端[23 ] 。
1. 2 量子比特与量子逻辑操作
经典比特(bit ,位) 是由宏观体系的物理量表征的。一个经典比特只有0 和1 两个值。
它可以由一些分离变量或连续参数(如电压) 的两个不同区域来表示。2n 个逻辑态的n
个比特的内存由00 ⋯0 至11 ⋯1 标记。除了储存二进制数据外,经典计算机通过一系列
布尔操作对各比特进行操纵,实现各种状态间的决定性变换。
量子比特(quantum bit ,or qubit ,量子位) 则由微观体系表征,如原子、核自旋或光子
等。| 1 > 和| 0 > 可以由原子的两个能级来表示,也可以由核自旋或光子的不同极化方向
来表征。与经典比特显著不同的是,量子比特| 1 > 和| 0 > 之间存在着许多中间态,即| 1 >
和| 0 > 的不同迭加态,例如1
2
(| 0 > + | 1 > ) 表示一个两子比特同时存储着0 和1 。因此,
对于位数相同的n 个比特,量子比特可以存储2 n 倍的经典比特所能存储的信息。
对于两个量子比特的体系,其完备基由四个布尔态| 00 > 、| 01 > 、| 10 > 和| 11 > 组成。
考虑它们之间的迭加,我们可以发现,| 10 > + | 11 > = | 1 > á (| 0 > + | 1 > ) ,这是由两个
量子比特构成的直积空间。而| 11 > + | 00 > 或| 01 > + | 10 > 则不能再写成直积形式。后
面这种情况就是前面提到的纠缠。对于一个处于纠缠状态的体系,我们不能确切地指出
其中某一个量子比特是处于| 1 > 还是| 0 > 。更一般的纠缠态是处于2n 个布尔态的n 个
经典比特组成的迭加态。
Ψ > = Σ
11 ⋯1
x = 00 ⋯0
Cx x > (7)
其中Cx 可以是复数并且满足Σ
x
| Cx | 2 = 1 。当Cx =
1
2 n
时,称为等幅迭加态。这种等幅
迭加态在以下要介绍的各量子算法中经常被用作初态。从上式也能看出,| Ψ > 是一个
2 n 维的Hilbert 空间中的一个单位矢量。它所在空间的维数是随n 呈指数型增长,这明
显区别于经典体系中随n 呈线性增长的态空间[24 ] 。
在一个孤立的量子体系中,对态的操作应是幺正的、可逆的。因此,我们构造的量子
逻辑门也应满足这个特征[25 ] 。
因为量子逻辑门是幺正的,所以量子计算应该是可逆的。经典计算机之所以不可逆,
是因为存在能量耗散[26 ,27 ] 。随着近年来经典计算机主频的不断提升,其集成化芯片上由
于逻辑操作而产生的热量也不断增加。巨大的热量不仅损坏计算机元器件,也限制了计
186 物理学进展21 卷
算机的进一步发展。而这种现象在量子计算机中不应出现。因为量子相干性要求量子态
应尽可能地与环境隔离开,所以体系不应有能量耗散。这也意味着量子计算在理论上是
无能耗的[28 ] 。
图1 几种常见的量子逻辑门与它们的符号表示及图示
1. 3 量子计算的基本要求[29 ]
要利用某物理体系实施量子计算,该物理体系必须满足以下基本要求:
①体系必须有好的相干保持性。体系要尽可能地与周围环境隔离,保证量子态在其
内部的演化是幺正的。环境对量子相干性的干扰称为消相干。它使量子态逐渐丧失相干
性,成为混合态。这将使量子计算出现误差,甚至不能进行。一般说来,在实际操作中,消
相干的影响是不可避免的。有定量分析表明[30 ] ,由于消相干的影响,量子体系中的相干
性一般呈指数型衰减。因此人们能做的是尽可能地减小这一不良影响,使消相干过程远
远长于量子计算的过程,这样将对量子计算不构成明显的破坏。另外,必要的补救措施也
不可缺少,如用量子纠错的办法来排除误差。
②体系内部用作量子比特的各部分之间必须存在适当的相互作用。这种相互作用使
各个量子比特相互关联,共同完成计算任务。
③能方便地从体系之外对各个量子比特作精确操纵。这种操纵包括:量子初态的制
备、计算过程中态的演化以及最后体系的状态的有效测量。
按以上标准,我们可以在原子、分子、半导体等量子体系中发现不少适合作量子计算
的系统。表1 中给出了部分物理体系的特性,其中开关时间表示一次典型的量子逻辑操
作所需的时间。可以看出,这些体系在量子态的相干性能得到保持的时间内可以进行足
够多次的量子逻辑操作。原则上能保证量子计算的有效进行。
另一个问题是需要多少种逻辑操作才能保证量子计算的有效进行。有证明显示[31 ] ,
所有用来作量子计算的操作都可以最终分解为两种基本操作:一种是单量子比特的旋转
操作,例如前面提到的Hadamard 门等,它们的作用是使量子比特在| 1 > 、| 0 > 两态间随
意变化。另一种是两量子比特的操作,例如受控非门等。下面我们以量子离散傅立叶变
1 期赵志等:量子算法与量子计算实验187
换(Quantum Discrete Fourier Transform) 为例来说明这个问题。
量子离散傅立叶变换在下面将要介绍的各种量子算法中起着十分重要的作用,它的
数学表达式为
UQFT α > =
1
q Σ
q- 1
c = 0
ei2παc/ q c > ( q = 2 l) (8)
可见它的作用是将一个单态转换为一个迭加态。不难发现,α= 0 时,通过量子离散傅立
叶变换,能得到一个等幅迭加态。这种等幅迭加态在后面要介绍的各量子算法中有重要
的用途。一般情况下,
UQFTΣa
f (α)α α > = Σc
.f
( c) c > (9)
系数.f ( c) 即f (α) 的量子离散傅立叶变换。比较以上各式,可知
.f
( c) =
1
q Σa
exp (2πiac/ q) f ( a) (10)
按照Shor 的理论[32 ] ,实现量子离散傅立叶变换包含两个步骤:首先用Hadamard 门和一
个受控旋转门来构造一系列操作;然后用交换操作来进行反向读数。作用在第j 个量子
比特上的Hadamard 门和作用在第j 、第k 个量子比特上的受控旋转门分别表示为
Hj =
1
2
1 1
1 - 1
A jk =
1
2
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 eiθk - j
(11)
其中θk - j =π/ 2 k - j 。对于l 个量子比特的情况,即N = 2 l ,有
X > = Xl - 1 > á Xi - 2 > á ⋯á X0 > , 其中X = Σ
l - 1
i = 0
Xi2 i , Xi = 0 , 1 。作操作
H0 A 01 A 02 ⋯A 0 , l - 1 H1 ⋯Hl - 3 A l - 3 , l - 2 A l - 3 , l - 1 Hl - 2 A l - 2 , l - 1 Hl - 1 (见图2) ,我们可以得
到态b > = bl - 1 , bl - 2 , ⋯, b0 > , ( b = Σ
l - 1
i = 0
bi2 i ) 。而这个态与(8) 式中| c > 的关系为: |
bl - 1 , bl - 2 , ⋯, b0 > = | c0 , c1 , ⋯, cl - 1 > ,即我们从上面网络的输出端反向读数,便可得到
量子离散傅立叶变换的正确结果。但是,当以上量子离散傅立叶变换仅仅是某量子算法
的中间过程时,我们不能简单地采用反向读数的方式。因为读数是一种测量过程,它将破
坏原来的量子系统,使量子计算就此终止。为了实现一个完整的量子离散傅立叶变换,除
了上面提到的Hj 和A ij组成的操作系列之外,我们还须引入一个交换操作S ij 。这是一个
两量子比特的操作,它的功能是S ij | i > | j > = | j > | i > 。通过量子比特两两间的交换位
置,我们就能使以上的| b > 变为| c > 。S ij的数学表达式为
S ij =
1 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
=
1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0
1 0 0 0
0 0 0 1
0 0 1 0
0 1 0 0
1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0
其中第一项和第三项为上面定义过的受控非门。第二项其实也是一个受控非门,不同的
188 物理学进展21 卷
是它的控制比特是后面的比特,前面的比特为目标比特,即| a > | b > →| a á b > | b > 。
当然,量子计算的有效性和实用性在于在多个量子比特上进行运算。因而从未来实
现量子计算机的目标考虑,除了以上的几个要求之外,衡量一个物理体系是否适宜作量子
计算还要看它能否方便地拓展至多个量子比特。
图2 量子离散傅立叶变换网络。左为输入,右为输出
信道由下往上标记为0 ,1 , ⋯, l - 1
表1 部分物理体系的特性
量子体系开关时间(s) 相干时间(s) 相干时间内可开关次数
Mossbaur 核10 - 19 10 - 10 109
GaAs 中的电子10 - 13 10 - 10 103
Au 中的电子10 - 14 10 - 8 106
囚禁离子10 - 14 10 - 1 1013
光学微腔10 - 14 105 109
电子自旋10 - 7 10 - 3 104
电子量子点10 - 6 10 - 3 103
核自旋10 - 3 104 107
1. 4 量子纠错编码与容错的量子计算
从上面几节的叙述,我们已经知道,由于量子态的相干性,量子计算机可以比经典计
算机更迅速地解决某些问题,如大数质因子分解,量子搜索等。但是,要实现这些算法,如
大数质因子分解,需要相当数量的量子位和量子逻辑门。目前从实验上,要保持这些量子
位的相干性,同时又准确地实现这些量子门的操作几乎是不可能的。其中一个重要的原
因就是消相干的存在。由于消相干效应,多量子位中的一个或多个量子位与环境作用而
产生纠缠,从而破坏了存储器中量子态的相干性;而且在量子逻辑门的操作过程中,导致
错误在不同量子位之间传播。为了保持量子态的相干性和量子计算的正确性,人们提出
了量子纠错编码与容错量子计算来克服消相干对量子信息存储和量子计算的消极影响。
量子编码首先是P. W. Shor 于1995 年提出[33 ] 。随后, Calderbank , Shor[34 ] 和
Steane[35 ]分别提出了用七量子位编码一位量子信息的CSS 编码;Laflamme 等[36 ]发现编
码一位量子信息最少只需要五个量子比特; Gott sman 等[37～39 ]用群论给出了量子编码另
一种理论形式。
量子纠错编码的基本思想是: (a) 编码:将量子信息编码到更大的Hilbert 空间; (b) 错
1 期赵志等:量子算法与量子计算实验189
误校验:对编码的量子系统进行量子非破坏测量; (c) 解码:进行合适的量子操作,纠正错
误的量子信息。
假设一位量子比特信息| <
0 > = a| 0 > + b| 1 > 与环境发生作用而产生消相干:
ei > ( a 0 > + b 1 >) → a ( c00 e00 > 0 > + c01 e01 > 1 >) +
b ( c01 e01 > 1 > + c11 e11 > 0 >) (12)
其中,| ei , j > 表示环境的量子态, ci , j依赖于具体的环境噪音( i , j = 0 ,1) 。这个相互作用
可以改写为:
ei > <
0 > →( eI > I + eX > X + eY > Y + eZ > Z) <
0 > (13)
其中| eI > ,| eX > , | e Y > , | eZ > 表示环境的量子态, I 为单位1 , X , Y , Z 为通常的Pauli
算符。I 表示量子信息不变, X 表示量子信息发生比特反演, Y 表示量子信息发生相位
反演, Y = ZX 表示量子信息同时出现相位反演和比特反演。
假设计算机需要操纵k 位量子比特信息,设k 位量子态为| < > 。引入另外n - k 个
量子位,初态处于| 0 > 。编码操作就是完成:
E( < > 0 >) = <
E > (14)
编码操作也可以看作从k 位量子比特到n 位量子比特的映射。| <
E > 为编码以后的
n 位量子态。
经过编码以后,量子态与环境发生相互作用,此时消相干可以表示为:
ΣS
eS > MS
<
E > (15)
其中MS 称作纠错算符, 为n 个Pauli 算符的张量积。如对于n = 7 , M =
I1 X2 I3 Y4 Z5 X6 I7 ,所有的MS 构成纠错算符集合S 。
进一步引入另外n - k 个辅助量子位,初态为| 0 > 。可以证明,存在一个对编码量子
态和辅助量子位的校验操作:
A ( MS
<
E > 0 > a) = ( MS
<
E >) S > a PMS ∈ S (16)
经过校验操作,然后对辅助量子位进行测量,我们可以发现原来编码系统的错误,然后施
加M - 1操作,从而纠正原来编码量子态的错误。
量子编码理论的任务就是找到合适编码E 和校验操作A ,同时使纠错算符集合S 包
含尽可能出现的错误。量子编码理论的另一个重要任务就是利用最少的编码量子位实现
纠正编码量子系统中尽可能多的错误。
最简单的量子纠错编码是CSS 编码[34 ,35 ] 。这种编码用七个量子位存储一位量子信
息。存储量子信息的两个正交态为:
| 0 E > ≡| 0000000 > + | 1010101 > + | 0110011 > + | 1101001 >
+ | 0001111 > + | 1011010 > + | 0111100 > + | 1101001 >
| 1 E > ≡| 1111111 > + | 0101010 > + | 1001100 > + | 001101 >
+ | 1110000 > + | 0100101 > + | 1000011 > + | 0010110 > (17)
应用这两个正交态,原来的一位量子态a| 0 > + b| 1 > 转变为七量子位量子态a| 0 E >
+ b| 1 E > 。这个量子态有一个明显的特性:如果其中的任意一位出现错误,我们仍然能够
知道原来的一位量子态a| 0 > + b| 1 > 。Steane 七量子位编码的编码电路图如下所示。
190 物理学进展21 卷
图3 七量子位编码的编码电路图
由于Steane 量子编码是由经典Hamming[23 ]代码所组成,所以应用Hamming 检验矩
阵容易发现量子编码中出现的比特反演错误。Steane 七量子位编码的校验电路图如下所
示:
图4 七量子位编码的比特反演校验电路图
在校验电路中,附加了另外三个| 0 > 态量子位。Hamming 编码量子态和附加的三个
量子态的作用可以表示为:
| ΨE > á | 0 >anc →| ΨE > á | HΨ
E
>anc (18)
在这个操作过程中, H 就是上面所说的检验操作。操作产生的辅助量子位的结果只与编
码量子态中出现的错误有关,而与编码量子态无关;由于校验电路是由XOR 所组成,因
而,这个电路只能检验比特反演错误,而不能检验相位反演错误;发现错误以后,加一个相
应的幺正变换,可以纠正原编码系统中的比特反演错误。
为了纠正编码系统中的相位反演错误,我们可以对编码系统作一个Hadamard 变换。
由于Z = HX H ,因此,纠正相位反演错误可以等效为对编码系统每个量子位作一个
Hadamard 变换,纠正比特反演错误,再对编码系统每个量子位作一个Hadamard 变换。
由于Y = ZX ,因此,经过以上两个步骤,也就自然地纠正了编码系统中的Y 错误。
有了量子纠错编码,可以保证在噪音通道中实现高保真度的量子通讯,但是它并不能
保证量子计算的正确性。由于量子逻辑门如CNOT 门连接着不同的量子位,如果量子计
算中出现错误,就会导致错误在整个计算机中传播。容错的量子计算就是考虑每一个逻
1 期赵志等:量子算法与量子计算实验191
辑操作或每一步演化都处在噪音的环境下对量子信息的处理。
量子容错一个简单的办法就是反复地应用量子纠错编码。由于每一次校验操作都可
以减少环境引入的噪声(包括校验操作过程中引入的噪声) ,因此多次地应用量子纠错编
码,从而可以达到容错的目的[40 ]
另外一种办法是采用Shor[41 ]法。它的核心思想就是在网络中尽可能多的地方对量
子位进行验证,重复校验操作,从而限制错误在网络中的传播。下图是一个校验容错的量
子网络,它可以用来限制错误在网络中的传播。值得注意的是,在进行校验操作之前,对
每一个辅助位进行了验证,并且,每一位编码位仅仅与一位辅助位发生作用。
图5 校验容错的CSS 量子纠错编码
上面七个量子比特是编码量子位,下面的是辅助量子位。所有的量子门,测量及其演
化都存在噪音。这里仅仅使用H 和两位的XOR。七个H 变换之前的网络制备量子态
| 0 E > ,然后对其进行验证:小方块代表单量子位测量。如果测量结果为1 ,那么重新进行
制备。H 变换为| 0 E > 为| 0 E > + | 1 E > 。后面的七个XOR 表示在编码量子比特与辅助
量子比特之间进行XOR 操作。这个操作使编码量子比特中的X 错误传播到辅助量子比
特,而辅助量子比特中的Z 错误传播到编码量子比特。从辅助量子比特的测量结果可以
推导出编码量子比特中的X 错误。一个类似的网络可以纠正编码量子比特中的Z 错误,
而且后面的网络可以纠正前面出现的所有错误。值得注意的是,在进行校验操作之前,对
每一个辅助位进行了验证,并且,每一位编码位仅仅与一位辅助位发生作用。
为了实现容错的量子计算而不仅仅是量子信息的存储,我们可以编码,逻辑操作,然
后再解码。另外一种更有效的办法是建立容错的量子逻辑来实现量子态的演化。
应用Steane 七量子位编码,容易建立容错的NOT 门,Hardamard 门,相位门,CNOT
门和通用的Toffoli 门。有了通用的Toffoli 门[42 ] ,人们期望构造无数的其它量子逻辑门,
从而实现更广泛的容错量子计算。
到目前为止,基于量子纠错编码的容错量子计算仍然是最理想的,但是它要求的量子
位和量子逻辑操作却非常之多。Preskill[42 ]和Steane[43 ]对它进行估计发现,超过目前最
192 物理学进展21 卷
好经典计算机的量子计算机将需要1000 个量子位和1010个量子门。如果不采用量子纠
错编码,每个量子位和每个量子门的噪音要求低于10 - 13 。而如果应用量子纠错编码,却
又要求几十甚至数百倍的量子门,但是,对每个量子位和量子门的噪音的要求可以放宽至
10 - 5 。最近,Steane[44 ,45 ]对Shor 的方法作了很大的改进,但是,对量子门数量的要求仍然
是非常之多。人们期待建立更有效的容错量子计算方法。
2 量子算法
2. 1 量子体系的模拟[22 ,46 ,47 ]
在前面我们已提到,量子比特除了经典比特的| 0 > 和| 1 > 之外,还有| 0 > 与| 1 > 的迭
加态。在迭加态上进行量子并行计算使量子计算机能完成许多经典计算机做不了的事
情。经典计算机处理问题是利用一些非经典装置如晶体管等来实施基本逻辑操作。量子
计算机处理问题也是用类似的方式,即两个量子变量之间的非线性作用来实施基本的量
子逻辑操作。这些量子逻辑操作除了经典逻辑操作中已有的AND、NOT 等之外,还有产
生迭加态和纠缠态的操作。这些特性使量子计算机有可能用来模拟其它量子体系的行
为[48 ] 。
Feynman 首先注意到用经典计算机模拟量子体系十分困难[49 ] 。在过去的五十年中,
人们不断探索使用各种半经典方法以及Monte Carlo 方法等来模拟量子体系[50 ] 。但这些
方法在处理实际问题时,对计算机资源的要求非常高,所耗机时和内存空间随着被模拟体
系的规模呈指数型增长。Feynman 曾指出,用经典计算机来模拟一个任意量子态的完全
时间演化是不可能的。因为量子态的波函数所在矢量空间的维数随体系规模呈指数型增
长。如描述40 个自旋为1/ 2 的粒子,用经典计算机需占用内存240≈1012个数空间;而计
算其时间演化需240 ×240的矩阵。但用量子计算机来做这个事情只需40 个量子比特演
化一段时间即可。这是因为量子计算机本身就是一个量子体系。用一个量子体系去模拟
另一个量子体系的关键在于能精确操纵模拟者,使其与被模拟者的演化完全一致。另外,
防止环境对量子体系的消相干影响也是须注意的问题。模拟一个封闭的量子体系时,保
持体系相干性的难度可能不大。但要模拟一个开放的量子体系时,如何防止消相干效应
的干扰则是一个须认真对付的问题。好在一个开放的量子体系与环境所构成的整体仍是
一个孤立体系。这样一个孤立体系的演化仍可用幺正算子表示。不过对于一个开放体系
的模拟,没有必要将整个环境都考虑在内,只需考虑对量子体系起作用的那部分环境即
可。
还有一个值得注意的问题。如上面所述,用N 个量子比特便能模拟N 个自旋1/ 2
的粒子组成的体系。但是,在这N 个量子比特上进行的幺正操作仍是在2 N ×2 N 维
Hilbert 空间中进行。也就是说,量子计算机在模拟一个量子体系时只是压缩了所需内存
的规模。但在门操作方面的要求与经典计算机并无区别。然而如果被模拟的量子体系中
存在局域相互作用,如范得瓦尔斯气体或Ising 模型等,量子计算机的门操作步数将是N
1 期赵志等:量子算法与量子计算实验193
的多项式形式,因而它对量子体系的模拟比用经典计算机来做同样的事要有效得多。总
之,用量子计算机来模拟量子体系可以极大地节约计算机资源,以数十个量子比特、用数
十步便能完成经典计算机需用1023数量级的内存空间和机时才做得了的事情。
2. 2 Deut schOJ
ozsa 算法
Deut schOJ
ozsa (DJ ) 算法是九十年代初提出的一种量子算法[51 ] 。算法的提出者企图
通过这样一种算法来显示量子算法比经典算法优越。DJ 算法考虑的是N 个比特的函数
的整体性质。对于N 个比特组成的集合XN = { x N x N - 1 ⋯x1 x0 | x m = 0 , 1} ,如果函数f
使集合XN 中一半元素为0 ,另一半为1 ,则f 称为平衡型函数;如果函数f 的作用是使集
合XN 中的元素全为0 或全为1 ,则f 称为常数型函数。DJ 算法要处理的是,如何以快于
经典算法的办法判断一个已知函数是平衡型的还是常数型的。
用g 和h 分别标记平衡型函数和常数型函数,| x > 为| 1 > 或| 0 > 。存在以下性质
h1| x > = | 0 > ; h2| x > = | 1 > ; g1 | x > = | x > ; g2 | x > = | 1 - x > 。利用这些性质,对
于一个两比特的体系,经典算法需要至少两次运算方能确定函数是h 还是g 。而运用量
子算法,可以先制备态。| Ψ > =
1
2
( | 0 > + | 1 > ) 1 ( | 0 > - | 1 > ) 2 。设存在操作V ,使
| x > 1| y > 2 →| x > 1| y Ý w ( x) > 2 ,其中Ý表示二进制求和, W ( x ) 表示f 函数或g 函数
的作用(例如当W = h1 时, W ( x) = 0) 。不难发现,用V 作用在| Ψ > 上,当W 的效果分
别对应于h1 、h2 、g1 、g2 时,| Ψ > 最终变为1
2
(| 0 > + | 1 > ) 1 (| 0 > - | 1 > ) 2 ,
1
2
(| 0 > +
| 1 > ) 1 (| 1 > - | 0 > ) 2 ,
1
2
(| 0 > - | 1 > ) 1 ( | 0 > - | 1 > ) 2 , -
1
2
( | 0 > - | 1 > ) 1 ( | 0 > -
| 1 > ) 2 。即一次操作便能从表达式上区分开h 类和g 类函数。当然,涉及到量子态的最终
测量读出时,DJ 算法的操作步数并不少于经典算法。
不过这一算法推广至多量子比特时,优越性便得到显示。对于一个N + 1 量子比特
的体系| Ψ > = | 00 ⋯0 > á | 1 > ,通过操作UQFT| 00 ⋯0 > á H| 1 > 得到
1
N Σ
N
i - 1
i > á 1
2
( 0 > - 1 >) (19)
将上面提到的操作V 作用以上态,可得
1
N Σ
N
i - 1
( - 1) W ( i) i > á 1
2
( 0 > - 1 >) (20)
其中W ( i) 可以是0 ,也可以是1 。对前面N 个量子比特作逆向量子傅立叶变换,有
Φ > á 1
2
( 0 > - 1 >) (21)
利用波包随机塌缩的特性,测量前N 个量子比特。若| Φ> = | 00 ⋯0 > ,则f 为常数型函
数,否则f 为平衡型函数。因为只有当f 为常数型函数时,才有可能使( - 1) W ( i) 成为公
共相因子。于是作逆向傅立叶变换之后,能回到原来的态| 00 ⋯0 > 。显然在这种情况下,
DJ 算法远远优于经典算法。不过,DJ 算法仅能处理以上简单的问题。若f 除了平衡型
和常数型,还可能是其它类型的函数的话,则该算法无能为力。另外,通过DJ 算法也不
194 物理学进展21 卷
能知道函数的值具体是多少。因此,在人们的印象中,DJ 算法只不过是个游戏。量子计
算并未因此受到重视。直到1994 年,P. W. Shor 提出关于大数质因子分解的方法[32 ]后,
量子计算的研究才广泛地引起人们的重视。
2. 3 Shor 算法———大数质因子分解的量子算法
如果我们已知两个数A 和B ,我们能很快算出A ×B = C。但是,如果我们事先知道
的只是C ,那么要将C 分解为A 和B 就不会太容易,尤其是随着C 的值的增大,求出A
和B 的难度也将不断增加。例如,对于一个大数N ,如果我们通过用N 除以1 ,2 , ⋯N
的办法来寻找其质因子的话,那么我们最多需尝试N 次。用算法语言讲,需用0 ( N )
步。用经典计算机来做这样一件事,至少需log2 N 个比特。由于N = 2
12
log2 N ,所以如果
用经典计算机来进行大数质因子分解,随着N 的增大,所需比特数(即内存) 是呈指数倍
的增长。按照组合数学理论[52 ] ,当计算规模随着问题的难度呈多项式型增长时,该问题
为P(Polynomial) 问题。对于P 问题,我们在有限的时间内总能找到办法求得它的解。对
于我们在有限的时间内不可能找到办法求得解的问题称之为NP (NonOPolynomial) 问题。
象大数质因子分解这类问题就是公认的NP 问题。正因为如此,目前世界上应用最广也
是最成功的加密方法O公开密钥RSA(Rivest ,Shamir ,Adleman) 系统[53 ,54 ]的核心思想就是
利用大数在有限时间内不可有效质因子化这一结论。将一个大数作为加密密钥可以加以
公开,要想解密必须知道其质因子。由于大数质因子化问题是个NP 问题,所以RSA 系
统能成功抗击密钥攻击。1995 年,P. W. Shor 提出一种量子算法[32 ] ,能将这一著名的NP
问题化为P 问题,矛头直指RSA 方法,从而在全球掀起了量子计算的研究热浪。
在Shor 算法中,寻找一个大数的质因子问题被转化为寻找其余因子函数的周期。只
要该周期被找到,并且为一个偶数,那么利用我国古代著名军事家孙武发现的孙子定理
(也称作剩余定理) [55 ] ,就能得到该大数的质因子。
给定整数N ,选取一个与N 互质的数a ( a < N) ,我们能得到余因子函数f a , N ( x ) =
ax mod ( N) ,其中x = 0 ,1 ,2 , ⋯, f a , N ( x ) 是ax / N 的余数。我们首先需要知道f a , N ( x )
的变化周期。例如N = 15 , a = 7 ,有
x 0 1 2 3 4 5 6 ⋯7 x 1 7 49 343 2401 16807 117649 ⋯f a , N ( x) 1 7 4 13 1 7 4 ⋯不难看出, f a , N ( x ) 的变化是有规律的,其变化周期为r = 4 。知道了这个周期,就可以利
用孙子定理:设A = ar/ 2 + 1 , B = ar/ 2 - 1 ,其中r 必须为偶数,且ar/ 2mod ( N ) ≠1 。求出
A、B 之后,再分别求A 、N 和B 、N 的最大公约数(gcd) 。设C = gcd ( A , N ) , D = gcd ( B ,
N) ,那么一定有C ×D = N ,即N 被成功地质因子化。以上面的例子来说明。已知N =
15 , a = 7 , r = 4 ,则不难求得A = 50 ,B = 48 , C = gcd (50 ,15) = 5 , D = gcd (48 ,15) = 3 ,则5
×3 正好为15 。
对于一个具体的量子计算过程,需先设置二个寄存器| 0 > | 0 > ,分别用作输入和输出
(简单记为第一和第二寄存器) ,其中第一寄存器取2L 位( L = log2 N ,即量子比特的数
1 期赵志等:量子算法与量子计算实验195
目) ,第二寄存器可比第一寄存器多取几位。首先我们通过量子离散傅立叶变换的操作使
第一寄存器处于等幅迭加态,第二寄存器仍置零。即
Ψ1 > =
1
q Σ
q- 1
a = 0
a > 0 > ( q = 22 L ) (22)
接着,利用量子态的迭加性质作量子并行计算| x > | y > →| x > | y Ý W ( x) > ,得
Ψ2 > =
1
q Σ a > x a (mod n) > (23)
第三步是对第一寄存器再次作量子离散傅立叶变换a > →=
1
q
Σ
q - 1
c = 0
exp (2πiac/ q) c > ,
有
Ψ3 > =
1
q Σ
q- 1
a =0 Σ
q- 1
c = 0
exp (2πiac/ q) c > x a (mod n) > (24)
然后测量第二寄存器,则第一寄存器将塌缩至
Ψ4 > =
1
c Σ
c- 1
j =0
j r + l > ( c = 22 L / r ) (25)
仍以上面的例子来说明。已知N = 15 , L = 4 , q = 256 ,则(23) 式应为
1
16〔| 0 > | 1 > + | 1 > | 7 > + | 2 > | 4 > + | 3 > | 3 > + | 4 > | 1 > | 5 > | 7 > + | 6 > | 4 > +
| 7 > | 13 > + | 8 > | 1 > + | 9 > | 7 > + | 19 > | 4 > + | 11 > | 13 > + | 12 > | 1 > + ⋯〕测量第二
寄存器,例如对态| 7 > 作投影测量,则系统塌缩至1
8
(| 1 > + | 5 > + | 9 > + ⋯) ,即(25) 式。
不过(25) 式中的周期r 无法用量子方法测得。因而我们需要作另一次量子离散傅立叶
变换,将r 换成另一个可测的周期。于是(25) 式变为
1
cq Σ
c- 1
j = 0 Σ
q- 1
b = 0
e2πi ( j r+ l) b/ q b > (26)
其中q 仍为22L 。假设b = mq/ r ,那么(26) 式将简化为
1
cq Σ
r - 1
m =0
e2πilm/ r mq/ r > (27)
多次重复以上过程,比较每次测出的mq/ r 。取最小的一个值,即q/ r 。由于q 已知,故
r 可求得。这一过程最多需log2 N 步。
当然,一般说来, b 不一定刚好等于mq/ r ,那么问题将变得稍微复杂一些。对于(26)
式,我们能得到| b > 的几率为1
cq
| Σ
c - 1
j = 0
e2πi ( j r + l) b/ q| 2 。由于2πilb/ q 这一项与j 无关,它只
是一个公共相角,所以以下我们只需讨论2πijlb/ q 这一项。由于e2πij rb/ q = e2πij ( rbmod q) / q ,
故可令| rbmod q| ≤ r
2
,则有| rb - qb′| ≤ r
2
,即| b
q
- b′
r
| ≤1
2 q
≤ 1
2 N2 ≤ 1
2 r2 。根据数学定
理[56 ] :当m 、n 互质,且满足|
m
n
- x | <
1
2 n2 ,则m/ n 是x 的连分数的一个渐近数。所以
b′/ r 可由b/ q 的连分数求得。由于0 ≤b′≤r - 1 ,所以应有r 个不同的b′,其中b′与r
互质的几率大于4/ π2log2 N 。因此我们以最多log2 N 步便能近似地估算出r 的值。
在估算r 的过程中,仍有一些技巧可言。例如,第一次测得| b > 之后,在以后几次重
196 物理学进展21 卷
复进行的过程中可尝试测量| b ±1 > , | b ±2 > , ⋯等。因为这将有较大的机会逼近mq/ r
的某一值。另外,如果b
q
≈ b′
r
,且b′与r 不互为质数,而我们在得到r 值后却发现算出的
质因子不对时,可尝试2 r ,3 r , ⋯等值。还有,如果在估算中得到了两个可能的r 值,那么
这两个值的最小公倍数就是正确的r 值。当然,如果反复进行Shor 算法之后,仍未得到
正确的质因子,我们可认为该大数本身为质数,不可质因子化。
总之,Shor 算法的关键在于求出大数N 的余因子函数的周期r 。剩下的步骤都可以
用经典计算机来完成,其中孙子定理中要用到的最大公约数可用Euclid 算法来有效求
得[55 ] 。不过,由于余因子函数的周期r 不能在量子计算中被有效测出,因此在Shor 算法
中需借助量子离散傅立叶变换,将余因子函数的周期换成另一个可测的周期。这是该算
法中一个十分巧妙的地方。
2. 4 Grover 搜索O无序数据库的搜索
先让我们设想做这样一件事:从一本电话号码簿上寻找一个号码。由于号码簿是按
照姓氏笔划的顺序排列的,因而号码的分布完全没有规律可循。如果用经典方法来搜索,
例如用试探法,需要逐一检查每项数据是否满足要求。若答案是‘否’,则继续搜索,并保
持这项数据的记录以便不再查询它;若答案为‘是’,则读出数据,并停止搜索。也就是说,
用这种试探法来搜索一个有N 项数据的数据库,最多需做N - 1 次努力。可以证明:对
于N 项无序排列的数据,用任何经典的方法来搜索其中某一项,平均需0. 5 N 次。例如,
如果有5 个号码,你用经典的试探法来搜索其中某一项,可能的搜索次数分别有:1 、2 、3
和4 ,即平均2. 5 次。当N 很大时,用经典方法自然很不划算。于是人们想到能否运用
量子计算更快地来做这样一件事情。
答案是肯定的。Grover 提出了一种算法[57 ] ,利用量子态的纠缠特性和量子并行计算
原理,可以用最多N 步的搜索寻找到所需项。Grover 算法的思想极为简单,可用一句话
‘振幅平均后翻转’来概括。具体说来是以下几个基本步骤:
图6 Grover 算法各步骤
①初态的制备。运用Hadamard 门将处于态| 0 > 和| 1 > 的各量子比特转化为等幅迭
加态。
②设数据库为T [ 1 ,2 , ⋯, N ] ,共N 项。设其中满足我们要求的那一项标记为A 。
于是在T 中搜索A 类似于求解一个单调函数的根。运用量子并行计算可以将A 所在态
的相位旋转180°,其余各态保持不变。即当T [ i ]
= A 时,增加一个相位eiπ。
③相对各态的振幅的平均值作翻转。这一操
作由幺正矩阵D 完成,其表达式为Dij =
2
N
, Dij =
- 1 +
2
N
。
④以上②③两步可以反复进行,每进行一次,
称为一次搜索。可以证明,最多只需搜索N 次,
便能以大于0. 5 的几率找到我们要找的数据项。
1 期赵志等:量子算法与量子计算实验197
图6 将以上①②③步形象地表现了出来。不难看出,仅仅经过一步的翻转, A 态的
振幅已明显高于其它各态。如果此时对整个体系作测量,那么A 态将以较大的几率塌缩
到测量仪器的本征态上。下面,我们以二量子比特和三量子比特为例,说明Grover 搜索
的过程。
对于一个由两个量子比特组成的体系,其初态为
Ψ0 > =
1
0
á 1
0
=
1
0
0
0
(28)
对此态作一个Hadamard 门操作可得一个等几率幅的态
Ψ1 > =
1
2
1
1
1
1
(29)
假设| 11 > 态是我们要找的态,则可利用量子并行算法使| 11 > 态翻转180°,即
Ψ2 > =
1
2
1
1
1
- 1
(30)
将平均值翻转操作施加在这个态上可得
Ψ3 > = Dij Ψ2 >
1
2
- 1 1 1 1
1 - 1 1 1
1 1 - 1 1
1 1 1 - 1
Ψ2 > =
0
0
0
1
(31)
显然,此时测量| ψ> 态,系统将自然塌缩至| 11 > 态,即| 11 > 态被我们找到。如果继续进
行搜索,则不难发现,每搜索三次,| 11 > 态的振幅最大的情况就重现一次。
对于由三个以上的量子比特组成的体系,情况要复杂一些。例如在三个量子比特组
成的体系中,如果我们想搜索| 111 > 态,搜索结果依次为
2
8
1
1
1
1
1
1
1
5
,
2
16
1
1
1
1
1
1
1
- 11
,
1
502
- 7
- 7
- 7
- 7
- 7
- 7
- 7
13
,
1
134
17
17
17
17
17
17
17
5
,
2
128
23
23
23
23
23
23
23
67
,
2
1024
1
1
1
1
1
1
1
181
,
2
512
89
89
89
89
89
89
89
- 275
可以看出,经过几次搜索,我们要找的| 111 > 态的几率先由小变大,再由大变小,然后再次
变大。在这七次搜索过程中,以第六次的效果最好,第四次的效果最差。不过,不管是搜
198 物理学进展21 卷
索多少次,最终的测量是导致系统以一定几率而不是100 %地塌缩至| 111 > 态上。由此
我们能看出Grover 算法的缺陷:只告诉我们以大于0. 5 的几率找到所需结果的搜索次数
的上限,并没有告诉我们最佳的搜索次数是多少。
为了弥补这一不足,Boyer 等人给出了Grover 算法的严格数学表达式[58 ] 。设数据库
T 中T [ i0 ] = A 。对于初始等幅迭加态Ψ0 > = Σ
N - 1
i = 0
1
N
i > ,经过j 次Grover 搜索之
后,系统的状态将是
Ψj > = Ψ( kj , lj) > = , Ψ( N - 2
N
kj - 1 +
2 ( N - 1)
N
lj - 1 ,
N - 2
N
lj - 1 -
2
N
kj - 1) > (32)
其中kj 表示态| i0 > 经过j 次搜索后的振幅。在搜索了m 次之后,若km 最大,则表明用
Grover 算法搜索成功。此时测量| Ψm > ,便能获得A 。为了方便对该过程的物理图象的
认识,我们可令sin2θ= 1/ N ,则上式可重写为
kj = sin[ (2 j + 1)θ] l j =
1
N - 1
cos[ (2 j + 1)θ] (33)
很容易看出, kj 和l j 的变化恰好相差90°,即当我们要找的那项数据所在量子态的振幅为
最大时,其余各项的态振幅为最小。因而我们总能以较大的几率获取答案。例如,当(2 j
+ 1)θ=π/ 2 时, kj = 1 。也就是说,当搜索次数为j = (π- 2θ) / 4θ时, Grover 搜索成功。
对于两个量子比特情况, N = 4 ,则θ=π/ 6 , j = 1 ,即一次搜索成功。这与上面分析的完全
一样。而当N →∞时, j →∞。所以经典搜索无法完成的工作,用Grover 搜索也同样无法
完成。可见Grover 搜索方法仅仅是加快了搜索的速度,但并没有也不可能解决NP 问
题。
如果数据库中有t 个满足要求的项,那么按照以上数学方法能够很直接地得到
Ψ( kj , l j) > = Ψ( 1
t
sin[ (2 j + 1)θ] ,
1
N - t
cos[ (2 j + 1)θ]) > (34)
其中sin2θ= t/ N 。于是,有了这种数学描述后,我们在某种意义上能事先了解Grover 搜
索的最佳搜索次数。不过,在大多数情况下,我们不一定事先知道数据库中的总项数,更
不可能事先知道有多少项能满足我们的要求。因此,Grover 算法依旧未能告诉我们搜索
多少步才是最佳。为此,Boyer 等人提出了在实施Grover 搜索之前利用Shor 算法来近似
估计数据库中有多少项能满足我们的要求的办法[58 ] 。利用这一方法,只要我们事先知道
数据库中的总项数,原则上能在实施Grover 搜索之前知道搜索多少步是最佳。
Grover 算法提出之后,引起了众人极大的兴趣。有人提出量子态不必翻转[59 ,60 ] ,只
要旋转一个适当的角度便能完成与Grover 算法等同的工作。但不久这一想法便被证明
是不正确的[61 ] 。Grover 算法中的翻转方法不仅被证明是最优化的搜索方式[62 ] ,而且也
是抗干扰能力极强的方法[63 ] 。Grover 算法的提出对现行的计算方法也有一定促进作用。
有人运用Grover 算法的思想讨论了量子态振幅的演化动力学,其结果是可编成一段计算
机程序,作为子程序在现有计算机或今后的量子计算机上使用[64 ] 。
2. 5 Hogg 搜索O高度结构化搜索
前面介绍过的NP 问题中有一类名为可满足性问题(Satisfiability Problem ,简称SAT
1 期赵志等:量子算法与量子计算实验199
问题) [65 ] 。一个典型的SAT 问题是包括有n 个变量的一个逻辑公式,要求给予其中每个
变量一个赋值使逻辑公式为真。由于每个逻辑变量的赋值为二个,即‘真’或‘假’,或者用
二进制数字表示为‘1’或‘0’,所以SAT 问题有2 n 种可能赋值。这使得SAT 问题成为
NP 问题中最难的一类问题。有证明显示,一个有效的处理SAT 问题的方法可以很容易
地转化为处理其它NP 问题的方法;而反过来,可以有效地处理其它NP 问题的方法却不
一定能有效地处理SAT 问题。
一个逻辑公式可以有许多种等价的形式。利用摩尔根对偶定律,各形式之间能实现
转化。下面我们选取其中一种进行讨论,即各逻辑子句之间以逻辑与相联系,而每个逻辑
子句之间为各变量的逻辑或。用数学公式可表达为
F = ( x 1 ∨ x2 ∨ ⋯∨ x k1
) ∧( y1 ∨ y2 ∨ ⋯∨ yk2
) ∧ ⋯∧( z 1 ∨
No comments:
Post a Comment