薛希玲，李文騫，2，陳漢武，3，劉志昊,3

(1.東南大學(xué)計算機(jī)科學(xué)與工程學(xué)院，江蘇南京 210096； 2.南京森林警察學(xué)院信息技術(shù)系，江蘇南京 210023；

3.東南大學(xué)計算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室，江蘇南京 211189)

?

基于Grover硬幣算子的量子行走在商圖上的演化算子

薛希玲1，李文騫1，2，陳漢武1，3，劉志昊1,3

(1.東南大學(xué)計算機(jī)科學(xué)與工程學(xué)院，江蘇南京 210096； 2.南京森林警察學(xué)院信息技術(shù)系，江蘇南京 210023；

3.東南大學(xué)計算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室，江蘇南京 211189)

摘要：商圖是利用圖的對稱性分析量子行走算法的一種重要數(shù)學(xué)工具.量子行走在商圖上的演化算子由移位算子和硬幣算子構(gòu)成.本文以構(gòu)造的方式給出了Grover硬幣算子在超立方體的商圖上對應(yīng)的矩陣形式，并給出了其正確性證明.由于商圖上的移位算子可由原圖上的移位算子直接導(dǎo)出，從而確定了使用Grover算子作為硬幣的量子行走在商圖上的演化算子.

關(guān)鍵詞:硬幣算子;商圖;量子行走

1引言

作為設(shè)計隨機(jī)算法的一個有力的數(shù)學(xué)工具，經(jīng)典隨機(jī)行走為因式分解、k-SAT、圖同構(gòu)等問題提供了一系列最廣為人知的算法.而量子行走提供了加速經(jīng)典行走的可能性[1]，近年來設(shè)計基于量子行走的算法成為量子計算領(lǐng)域的研究熱點(diǎn).

另一方面，Grover利用搜索空間中的一個不變二維子空間，給出了搜索無結(jié)構(gòu)數(shù)據(jù)的最優(yōu)算法[2]，證明了將一個搜索問題限制在整個搜索空間的一個不變子空間中的思想是富有成效的.在基于量子行走的算法中，超立方體上的搜索算法SKW[3]通過搜索一個包含解的更小的空間以同等規(guī)模的時間復(fù)雜度給出了問題的解；Ambainis從商圖空間上的演化算子入手求解其特征值和特征向量以近似分析演化過程,設(shè)計算法求解元素獨(dú)立性問題[4].

在有關(guān)量子行走對稱性的研究中[5,6]，Krovi利用圖的自同構(gòu)群產(chǎn)生了行走的演化算子U的對稱群，這個對稱群決定了行走的不變子空間.文中證明如果初始狀態(tài)在該子空間中，量子行走將局限于這個子空間，即在比原圖小很多的商圖上演化.本文在上述工作的基礎(chǔ)上，主要探討基于Grover硬幣的量子行走的演化算子在商圖上的形式.以n維超立方體為例，我們推導(dǎo)出商圖上硬幣算子的形式，并給出了其正確性證明，從而確定了使用Grover算子作為硬幣的量子行走在商圖上的演化算子.

2基本概念

定義2設(shè)G=(V,E)是一個圖，～是頂點(diǎn)集V上的一個等價關(guān)系.G關(guān)于～的商圖[8]定義如下：頂點(diǎn)集合是商集V/～，兩個等價類[u]，[v]構(gòu)成一條邊當(dāng)且僅當(dāng)uv是G中的一條邊.

圖的自同構(gòu)是保持圖不變的頂點(diǎn)的置換，所有置換的集合構(gòu)成圖的自同構(gòu)群.令G是Cayley圖Γ的一個自同構(gòu)群，G作用于頂點(diǎn)集合V形成了一個劃分，劃分的塊對應(yīng)于由等價關(guān)系y=gx(g∈G)定義的等價類x≡y.圖Γ在自同構(gòu)群G的子群H定義的等價關(guān)系下的商圖表示為Γ/H.例如Cayley圖Γ(S3,{t1=(1,2),t2=(2,3)})在自同構(gòu)群的子群H=Z2(即交換兩個方向1和2的子群)下的商圖Γ/H如圖1所示.

從圖的對稱性角度，Krovi等人使用Cayley圖的自同構(gòu)群在圖的Hilbert空間上的群作用定義了等價關(guān)系.為敘述方便，我們直接給出n維超立方體上頂點(diǎn)的等價關(guān)系～為含有相同個數(shù)的1的頂點(diǎn)等價.

d-正則圖G=(V,E)上離散量子行走算法模型可以用酉演化算子U的重復(fù)應(yīng)用來描述[9].這個算子作用于Hilbert空間HS?HC，其中HS是由對應(yīng)頂點(diǎn)V的狀態(tài)|v〉張成的空間，HC是由基向量{|i〉|i∈{1,…,d}}張成的d維量子硬幣空間.算子U可以寫作U=S(I?C)，其中硬幣算子C是“翻轉(zhuǎn)”量子硬幣的酉算子，移位算子S是根據(jù)硬幣空間的狀態(tài)執(zhí)行移位操作的置換矩陣.

Grover算子[10,11]CG是基于離散量子行走的算法中頻繁使用的硬幣算子，形式如式(1)所示.該算子是所有滿足酉性和置換對稱性的算子中距恒等算子最遠(yuǎn)的.Krovi表明對于特定的初態(tài)，使用Grover算子的超立方體上離散量子行走具有指數(shù)級的快于經(jīng)典情況的到達(dá)時間(hitting time)[5].

(1)

將Grover算子改寫為CG=|φ〉〈φ|-(I-|φ〉〈φ|)=|φ〉〈φ|-|φ⊥〉〈φ⊥|，|φ⊥〉與|φ〉正交.該算子對任意向量的作用為保持該向量平行于均勻疊加態(tài)|φ〉的部分不變，而將垂直于|φ〉的部分取反，即CG對任意向量的作用為以|φ〉作反射.

3n維超立方體商圖的上的移位算子

3.1n維超立方體的商圖

如上所述，定義頂點(diǎn)的等價關(guān)系～為含有相同個數(shù)的1.以三維立方體為例，如頂點(diǎn)001、010和100等價.n維超立方體在上述等價關(guān)系～下形成的商圖為有n+1個點(diǎn)的線，將其重新標(biāo)記為

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

R和L分別表示方向(或邊)向右和向左.圖2給出了3維立方體的商圖G/～.根據(jù)等價關(guān)系的定義，商圖上點(diǎn)x對應(yīng)于原圖上所有包含x個1的頂點(diǎn)構(gòu)成的等價類，記為Vx.

3.2商圖上的移位算子

(2)

當(dāng)n=3時，

X為Pauli X矩陣.

由于Grover算子保持了超立方體的對稱性，下面我們給出使用Grover硬幣的情況下商圖上硬幣算子的計算.

43維立方體商圖上的硬幣算子

(3)

(4)

由此得到商圖上的硬幣算子

CH=C0⊕C1⊕C2⊕C3

(5)

5n維超立方體商圖上的硬幣算子

5.1商圖上硬幣算子的計算

上述過程可以自然地擴(kuò)展到n維超立方體.度為1的點(diǎn)0和n對應(yīng)的硬幣算子為1階單位陣，即C0=Cn=(1).

下面給出商圖上點(diǎn)x(x=1,2,…,n-1)處的硬幣算子Cx的計算.由于超立方體上相鄰頂點(diǎn)僅有一位不同(海明距離為1)，將Vx中頂點(diǎn)的x個1 中的一位變?yōu)?得到超立方體上有x-1個1的頂點(diǎn)的集合Vx-1，故Vx中每個頂點(diǎn)與Vx-1中的頂點(diǎn)有x條邊相連；將Vx中頂點(diǎn)的n-x個0中的一位變?yōu)?后得到超立方體上有x+1個1的頂點(diǎn)的集合Vx+1，故Vx中每個頂點(diǎn)與Vx+1中的頂點(diǎn)有n-x條邊相連.所有連接Vx-1和Vx的x條邊坍縮為商圖上的邊|L〉，同時所有連接Vx和Vx+1的n-x條邊坍縮為商圖上的邊|R〉.由此，令Px是由n階單位矩陣經(jīng)如下變換得來的2×n維矩陣：將其前x行相加并歸一化，后n-x行相加并歸一化，

(6)

則商圖上點(diǎn)x(x=1,2,…,n-1)處的硬幣算子為

(7)

故n維超立方體商圖上的硬幣算子

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

(8)

聯(lián)系式(2)得出的SH，商圖上的演化算子UH最終可由UH=SHCH求得.

5.2正確性證明

n維超立方體的Grover硬幣算子作用于量子行走的硬幣空間，將硬幣態(tài)以均勻疊加態(tài)|φ〉作反射.下面證明商圖上量子行走的硬幣算子CH和原圖上的硬幣算子C具有相同的作用.

6其他情況的討論

上述計算過程基于超立方體上使用Grover硬幣算子的情況，下面對在不同數(shù)據(jù)結(jié)構(gòu)上或使用不同的硬幣算子的量子行走加以討論.

量子算法中另一個常用的算子是Shor的大數(shù)質(zhì)因子分解算法中進(jìn)行離散量子傅里葉變換的算子[12]：

(9)

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

Q算子在每個硬幣態(tài)之間均等地分配幅度，使得測量硬幣空間得到各個方向的概率相同.由于該算子不具有置換對稱性[1]，使用其作為硬幣算子構(gòu)成行走的酉算子U和超立方體的自同構(gòu)群不滿足對易關(guān)系.由此，置換不變性允許我們將圖上的量子行走轉(zhuǎn)化為更為簡單的商圖上的量子行走，如果使用如Q算子則不可能.

7結(jié)語

本文延續(xù)使用商圖理論從對稱性角度研究量子行走算法這一思路進(jìn)行更加深入細(xì)致的研究，給出了量子行走算法在商圖上的硬幣算子的一個簡潔、直觀的計算方法，并證明了商圖上的算子和原圖中的Grover算子的作用都是將向量以均勻疊加態(tài)作反射.對超立方體、Jonson圖等不同量子行走數(shù)據(jù)結(jié)構(gòu)對應(yīng)商圖上的硬幣算子給出了統(tǒng)一的解釋.以上結(jié)論都基于滿足置換對稱性的Grover算子，對于不滿足置換對稱性但可能滿足其他對稱性的算子的分析則有待深入研究.

參考文獻(xiàn)

[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年出生于山東臨沂.東南大學(xué)計算機(jī)科學(xué)與工程學(xué)院博士研究生.研究方向?yàn)榱孔有凶咚惴皯?yīng)用.

E-mail：xuexiling@126.com

李文騫男，1979年出生于江蘇南京.東南大學(xué)計算機(jī)科學(xué)與工程學(xué)院博士研究生.研究方向?yàn)榭赡孢壿嫞孔影踩ㄐ?

陳漢武男,1955年出生于江蘇南京.東南大學(xué)教授、博士生導(dǎo)師.主要研究領(lǐng)域?yàn)榻?jīng)典信息論，量子信息與量子計算，數(shù)理解析.

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

劉志昊男,1982年出生于湖南邵陽.博士，東南大學(xué)講師，主要從事量子信息和量子通信方面的研究.

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:電子學(xué)報URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.03.009

中圖分類號:TP387

文獻(xiàn)標(biāo)識碼：A

文章編號：0372-2112 (2016)03-0555-05

基金項(xiàng)目:國家自然科學(xué)基金(No.61170321)；高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金(No.20110092110024)；江蘇省自然科學(xué)基金(No.BK20140651)

收稿日期:2014-05-11；修回日期：2015-02-25；責(zé)任編輯：梅志強(qiáng)