基于Grover硬币算子的量子行走在商图上的演化算子

薛希玲，李文骞，2，陈汉武，3，刘志昊,3

(1.东南大学计算机科学与工程学院，江苏南京 210096； 2.南京森林警察学院信息技术系，江苏南京 210023；

3.东南大学计算机网络和信息集成教育部重点实验室，江苏南京 211189)



基于Grover硬币算子的量子行走在商图上的演化算子

薛希玲1，李文骞1，2，陈汉武1，3，刘志昊1,3

(1.东南大学计算机科学与工程学院，江苏南京 210096； 2.南京森林警察学院信息技术系，江苏南京 210023；

3.东南大学计算机网络和信息集成教育部重点实验室，江苏南京 211189)

摘要：商图是利用图的对称性分析量子行走算法的一种重要数学工具.量子行走在商图上的演化算子由移位算子和硬币算子构成.本文以构造的方式给出了Grover硬币算子在超立方体的商图上对应的矩阵形式，并给出了其正确性证明.由于商图上的移位算子可由原图上的移位算子直接导出，从而确定了使用Grover算子作为硬币的量子行走在商图上的演化算子.

关键词:硬币算子;商图;量子行走

1引言

作为设计随机算法的一个有力的数学工具，经典随机行走为因式分解、k-SAT、图同构等问题提供了一系列最广为人知的算法.而量子行走提供了加速经典行走的可能性[1]，近年来设计基于量子行走的算法成为量子计算领域的研究热点.

另一方面，Grover利用搜索空间中的一个不变二维子空间，给出了搜索无结构数据的最优算法[2]，证明了将一个搜索问题限制在整个搜索空间的一个不变子空间中的思想是富有成效的.在基于量子行走的算法中，超立方体上的搜索算法SKW[3]通过搜索一个包含解的更小的空间以同等规模的时间复杂度给出了问题的解；Ambainis从商图空间上的演化算子入手求解其特征值和特征向量以近似分析演化过程,设计算法求解元素独立性问题[4].

在有关量子行走对称性的研究中[5,6]，Krovi利用图的自同构群产生了行走的演化算子U的对称群，这个对称群决定了行走的不变子空间.文中证明如果初始状态在该子空间中，量子行走将局限于这个子空间，即在比原图小很多的商图上演化.本文在上述工作的基础上，主要探讨基于Grover硬币的量子行走的演化算子在商图上的形式.以n维超立方体为例，我们推导出商图上硬币算子的形式，并给出了其正确性证明，从而确定了使用Grover算子作为硬币的量子行走在商图上的演化算子.

2基本概念

定义2设G=(V,E)是一个图，～是顶点集V上的一个等价关系.G关于～的商图[8]定义如下：顶点集合是商集V/～，两个等价类[u]，[v]构成一条边当且仅当uv是G中的一条边.

图的自同构是保持图不变的顶点的置换，所有置换的集合构成图的自同构群.令G是Cayley图Γ的一个自同构群，G作用于顶点集合V形成了一个划分，划分的块对应于由等价关系y=gx(g∈G)定义的等价类x≡y.图Γ在自同构群G的子群H定义的等价关系下的商图表示为Γ/H.例如Cayley图Γ(S3,{t1=(1,2),t2=(2,3)})在自同构群的子群H=Z2(即交换两个方向1和2的子群)下的商图Γ/H如图1所示.

从图的对称性角度，Krovi等人使用Cayley图的自同构群在图的Hilbert空间上的群作用定义了等价关系.为叙述方便，我们直接给出n维超立方体上顶点的等价关系～为含有相同个数的1的顶点等价.

d-正则图G=(V,E)上离散量子行走算法模型可以用酉演化算子U的重复应用来描述[9].这个算子作用于Hilbert空间HS⊗HC，其中HS是由对应顶点V的状态|v〉张成的空间，HC是由基向量{|i〉|i∈{1,…,d}}张成的d维量子硬币空间.算子U可以写作U=S(I⊗C)，其中硬币算子C是“翻转”量子硬币的酉算子，移位算子S是根据硬币空间的状态执行移位操作的置换矩阵.

Grover算子[10,11]CG是基于离散量子行走的算法中频繁使用的硬币算子，形式如式(1)所示.该算子是所有满足酉性和置换对称性的算子中距恒等算子最远的.Krovi表明对于特定的初态，使用Grover算子的超立方体上离散量子行走具有指数级的快于经典情况的到达时间(hitting time)[5].

(1)

将Grover算子改写为CG=|φ〉〈φ|-(I-|φ〉〈φ|)=|φ〉〈φ|-|φ⊥〉〈φ⊥|，|φ⊥〉与|φ〉正交.该算子对任意向量的作用为保持该向量平行于均匀叠加态|φ〉的部分不变，而将垂直于|φ〉的部分取反，即CG对任意向量的作用为以|φ〉作反射.

3n维超立方体商图的上的移位算子

3.1n维超立方体的商图

如上所述，定义顶点的等价关系～为含有相同个数的1.以三维立方体为例，如顶点001、010和100等价.n维超立方体在上述等价关系～下形成的商图为有n+1个点的线，将其重新标记为

|0,R〉,|1,L〉,|1,R〉,…,|n-1,R〉,|n,L〉，

R和L分别表示方向(或边)向右和向左.图2给出了3维立方体的商图G/～.根据等价关系的定义，商图上点x对应于原图上所有包含x个1的顶点构成的等价类，记为Vx.

3.2商图上的移位算子

(2)

当n=3时，

X为Pauli X矩阵.

由于Grover算子保持了超立方体的对称性，下面我们给出使用Grover硬币的情况下商图上硬币算子的计算.

43维立方体商图上的硬币算子

(3)

(4)

由此得到商图上的硬币算子

CH=C0⊕C1⊕C2⊕C3

(5)

5n维超立方体商图上的硬币算子

5.1商图上硬币算子的计算

上述过程可以自然地扩展到n维超立方体.度为1的点0和n对应的硬币算子为1阶单位阵，即C0=Cn=(1).

下面给出商图上点x(x=1,2,…,n-1)处的硬币算子Cx的计算.由于超立方体上相邻顶点仅有一位不同(海明距离为1)，将Vx中顶点的x个1 中的一位变为0得到超立方体上有x-1个1的顶点的集合Vx-1，故Vx中每个顶点与Vx-1中的顶点有x条边相连；将Vx中顶点的n-x个0中的一位变为1后得到超立方体上有x+1个1的顶点的集合Vx+1，故Vx中每个顶点与Vx+1中的顶点有n-x条边相连.所有连接Vx-1和Vx的x条边坍缩为商图上的边|L〉，同时所有连接Vx和Vx+1的n-x条边坍缩为商图上的边|R〉.由此，令Px是由n阶单位矩阵经如下变换得来的2×n维矩阵：将其前x行相加并归一化，后n-x行相加并归一化，

(6)

则商图上点x(x=1,2,…,n-1)处的硬币算子为

(7)

故n维超立方体商图上的硬币算子

CH=1⊕C1⊕…⊕Cn-1⊕1

(8)

联系式(2)得出的SH，商图上的演化算子UH最终可由UH=SHCH求得.

5.2正确性证明

n维超立方体的Grover硬币算子作用于量子行走的硬币空间，将硬币态以均匀叠加态|φ〉作反射.下面证明商图上量子行走的硬币算子CH和原图上的硬币算子C具有相同的作用.

6其他情况的讨论

上述计算过程基于超立方体上使用Grover硬币算子的情况，下面对在不同数据结构上或使用不同的硬币算子的量子行走加以讨论.

量子算法中另一个常用的算子是Shor的大数质因子分解算法中进行离散量子傅里叶变换的算子[12]：

(9)

其中，ω=exp(2πi/d).

Q算子在每个硬币态之间均等地分配幅度，使得测量硬币空间得到各个方向的概率相同.由于该算子不具有置换对称性[1]，使用其作为硬币算子构成行走的酉算子U和超立方体的自同构群不满足对易关系.由此，置换不变性允许我们将图上的量子行走转化为更为简单的商图上的量子行走，如果使用如Q算子则不可能.

7结语

本文延续使用商图理论从对称性角度研究量子行走算法这一思路进行更加深入细致的研究，给出了量子行走算法在商图上的硬币算子的一个简洁、直观的计算方法，并证明了商图上的算子和原图中的Grover算子的作用都是将向量以均匀叠加态作反射.对超立方体、Jonson图等不同量子行走数据结构对应商图上的硬币算子给出了统一的解释.以上结论都基于满足置换对称性的Grover算子，对于不满足置换对称性但可能满足其他对称性的算子的分析则有待深入研究.

参考文献

[1]Kempe J.Discrete quantum walks hit exponentially faster[J].Probability Theory and Related Fields,2005,133(2):215-235.

[2]Grover L.Quantum mechanics helps in searching for a needle in a haystack[J].Phys Rev Lett，1997,79(2):325-328.

[3]Shenvi N,Kempe J,Whaley K B.Quantum random-walk search algorithm[J].Physical Review A,2003,67(5):052307.

[4]Ambainis A.Quantum walk algorithm for element distinctness[J].SIAM Journal on Computing,2007,37(1):210-239.

[5]Krovi H.Symmetry in quantum walks[D].Los Angeles:University of Southern California,2007.

[6]Potocek V.Symmetries in discrete time quantum walks on Cayley graphs[DB/OL].http://arxiv.org/abs/1211.0172v1,2012.

[7]Rotman J J.An Introduction to the Theory of Groups[M].New York：Springer,1995.356-357.

[8]Ross K A.Wright C R.Discrete Mathematics[M].New Jersey：Pearson,2002.583-587.

[9]Venegas-Andraca S E.Quantum walks:A comprehensive review[J].Quantum Information Processing,2012,11(5):1015-1106.

[10]Kempe J.Quantum random walks—an introductory overview[J].Contemporary Physics,2003,44(4):307-327.

[11]Neilsen M,Chuang I.量子计算与量子信息[M].北京：高等教育出版社,2000.251-252.

[12]Shor P W.Algorithms for quantum computation:discrete logarithms and factoring[A].Symposium on the Foundations of Computer Science[C].Washington DC:IEEE Computer Society,1994.124-134.

薛希玲女,1985年出生于山东临沂.东南大学计算机科学与工程学院博士研究生.研究方向为量子行走算法及应用.

E-mail：xuexiling@126.com

李文骞男，1979年出生于江苏南京.东南大学计算机科学与工程学院博士研究生.研究方向为可逆逻辑，量子安全通信.

陈汉武男,1955年出生于江苏南京.东南大学教授、博士生导师.主要研究领域为经典信息论，量子信息与量子计算，数理解析.

E-mail：hw-chen@seu.edu.cn

刘志昊男,1982年出生于湖南邵阳.博士，东南大学讲师，主要从事量子信息和量子通信方面的研究.

The Evolutionary Operator of Quantum Walks with Grover Coin on Quotient Graph

XUE Xi-ling1,LI Wen-qian1,2,CHEN Han-wu1,3,LIU Zhi-hao1,3

(1.SchoolofComputerScienceandEngineering,SoutheastUniversity,Nanjing,Jiangsu210096,China;2.DepartmentofInformationTechnology,NanjingForestPoliceCollege,NanjingJiangsu210023,China;3.KeyLaboratoryofComputerNetworkandInformationIntegration(SoutheastUniversity),MinistryofEducation,Nanjing,Jiangsu211189,China)

Abstract:Using the symmetry of graphs,quotient graph is adopted as an important mathematical tool to analyze quantum walk algorithms.The evolution operator of quantum walk on quotient graph consists of shift operator and coin operator.This paper presents a method to construct the matrix of Grover coin operator on the quotient graph of hypercube,and gives a proof of its correctness.As the shift operator on quotient graph can be derived straightforwardly from shift operator on the original graph,the unitary evolution operator of quantum walks with Grover operator as coin operator can be determined.

Key words:coin operator;quotient graph;quantum walk

作者简介

DOI:电子学报URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.03.009

中图分类号:TP387

文献标识码：A

文章编号：0372-2112 (2016)03-0555-05

基金项目:国家自然科学基金(No.61170321)；高等学校博士学科点专项科研基金(No.20110092110024)；江苏省自然科学基金(No.BK20140651)

收稿日期:2014-05-11；修回日期：2015-02-25；责任编辑：梅志强