張洪濤, 代永濤, 凃玲英, 舒　軍, 熊紅梅, 胡一凡

(湖北工業(yè)大學(xué) 納米電子技術(shù)與微系統(tǒng)實(shí)驗(yàn)室,電氣與電子工程學(xué)院, 湖北 武漢 430068)

?

Grover量子搜索算法的模擬實(shí)現(xiàn)

張洪濤, 代永濤, 凃玲英*, 舒軍, 熊紅梅, 胡一凡

(湖北工業(yè)大學(xué) 納米電子技術(shù)與微系統(tǒng)實(shí)驗(yàn)室,電氣與電子工程學(xué)院, 湖北 武漢 430068)

摘要：將一種用于量子計(jì)算仿真的量子程序設(shè)計(jì)語言引入Grover量子搜索算法中，并在Linux操作系統(tǒng)中模擬實(shí)現(xiàn)該算法。仿真結(jié)果與理論分析結(jié)果的一致性驗(yàn)證了Grover量子搜索算法可以將搜索問題從經(jīng)典的N步縮小到步，是對(duì)經(jīng)典搜索算法的二次加速。同時(shí)，量子程序設(shè)計(jì)語言的引入，為量子搜索算法的研究提供了一種強(qiáng)大、簡(jiǎn)便、通用的工具。關(guān)鍵詞:Grover量子搜索算法; 量子程序設(shè)計(jì)語言; 仿真

MR:Subjectclassification: 68Q12,81P68

Grover量子搜索算法可用于圖的著色、最短路徑、排序等問題的求解，還可以有效破譯DES密碼體系，具有加速搜索密碼系統(tǒng)密鑰的潛在用途。經(jīng)過多年的改進(jìn)及研究擴(kuò)展，Grover量子搜索算法不斷趨于完善，目前已經(jīng)形成一個(gè)能夠適應(yīng)各種不同搜索需求且較為完整的搜索算法體系。

1量子Grover算法

1.1Grover量子搜索算法的原理

Grover量子搜索算法[16-18]的基本思想是通過對(duì)初始等幅疊加態(tài)進(jìn)行幺正變換，反復(fù)應(yīng)用Grover 量子迭代過程來抑制非目標(biāo)項(xiàng)的概率幅而放大所要尋找的目標(biāo)項(xiàng)的概率幅。最后,通過對(duì)量子態(tài)進(jìn)行測(cè)量，以接近1的概率搜索到目標(biāo)項(xiàng)。

1.2Grover量子搜索算法具體執(zhí)行步驟

第一步：初始化，產(chǎn)生一個(gè)等幅度的狀態(tài)疊合。

第二步：完成對(duì)判決函數(shù)的并行計(jì)算。

第三步：對(duì)最后分量做“Z操作”變換，標(biāo)出真解，且只有真解的幅度才是負(fù)值。

第四步：對(duì)|x,f(x)〉的第一分量執(zhí)行D變換，增大真解b對(duì)應(yīng)狀態(tài)|b,1〉的出現(xiàn)概率。其中D變換的變換矩陣D=(dij)2n×2n為

其中，ai是|i〉的幅度。

第五步：重復(fù)執(zhí)行第三步至第四步k次后進(jìn)行觀察，得到觀察結(jié)果|x,1〉，并將x作為真解輸出。Grover量子搜索算法的流程圖見圖1。

1.3Grover量子搜索算法的應(yīng)用

2Grover量子搜索算法的模擬實(shí)現(xiàn)

2.1量子程序設(shè)計(jì)語言QCL的基本要素

QCL是一個(gè)結(jié)構(gòu)化命令式量子程序設(shè)計(jì)語言[10-11]，其語法和C/Pascal類似。量子操作由函數(shù)和量子過程進(jìn)行定義，包含了豐富的量子數(shù)據(jù)類型，并引入量子寄存器和基于條件變換的量子控制結(jié)構(gòu)。其語句分為簡(jiǎn)單語句、流程控制語句、交互命令3類。其中，簡(jiǎn)單語句包括賦值語句、輸入輸出語句、子程序調(diào)用語句、測(cè)量語句和初始化語句；流程控制語句包括循環(huán)語句、如果語句和異常終止語句；交互語句包括模擬語句、開殼語句、列表語句和退出語句。類型分為標(biāo)量(整型、實(shí)型、復(fù)型、字符串型和布爾型)、張量(向量、矩陣和n 階張量)以及量子(通用寄存器qureg、量子常量quconst、目標(biāo)寄存器quvoid和擦除寄存器quscratch)3類,并設(shè)計(jì)了透明的擦除機(jī)制以保證其量子位得以充分利用。具體來說，它主要包含以下幾方面特點(diǎn)：第一，保留了傳統(tǒng)數(shù)據(jù)類型、函數(shù)、控制流以及交互式I/O，具有傳統(tǒng)程序結(jié)構(gòu)的特色；第二， 提供了各種量子數(shù)據(jù)類型以及量子位存儲(chǔ)和寄存的表示方法；第三，反映了量子計(jì)算的酉變換之可逆性、狀態(tài)之不可觀察性和量子位之非定域性等特點(diǎn)；第四，實(shí)現(xiàn)了量子算法的可逆的幺正變換和不可逆的測(cè)量操作。

2.2grover.qcl偽代碼

procedure grover(intn) {

intl=floor(log(n,2))+1; //量子比特?cái)?shù)

intm=ceil(pi/8*sqrt(2^l)); //迭代次數(shù)

intx;

inti;

quregq[l]; //為量子堆中的l位變量q分配空間

quregf[1];

printl,“qubits, using”,m,“iterations”;

{

reset;

H(q);// 制備疊加態(tài)

fori= 1 tom{ // 主循環(huán)

query(q,f,n); // 執(zhí)行查詢操作

CPhase(pi,f); // 受控相位變換

!query(q,f,n); // 不執(zhí)行查詢操作

diffuse(q); // 離散操作

}

measureq,x; // 進(jìn)行測(cè)量操作

print “measured”,x;

} untilx==n;

reset; // 將所有量子寄存器復(fù)位

}

2.3實(shí)驗(yàn)結(jié)果及分析

當(dāng)n=100、10 000、1 000 000時(shí)，其Grover量子搜索算法搜索結(jié)果分別如圖2中a、b和c所示。為更直觀地反映該算法的成功率，我們通過數(shù)據(jù)模擬得到算法的成功率P與搜索問題的解在整個(gè)搜索空間中所占的比例M/N之間的關(guān)系，如圖2中d所示。

圖2Grover量子搜索算法搜索結(jié)果及成功概率

Fig.2The search results of Grover quantum search algorithm and Grover′s probability

3結(jié)語

參考文獻(xiàn):

[1]GROVERLK.Afastmechanicalalgorithmfordatabasesearch[J].AnnualAcmSymposiumonTheoryofComputing, 1996:212-219.

[2]GROVERLK.Quantummechanicshelpsinsearchingforaneedleinahaystack[J].PhysicalReviewLetters, 79(2):325, 1997.

[3] 盧春紅.3量子位的Grover量子搜索算法的核磁共振的仿真實(shí)現(xiàn)[D].無錫:江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院,2007.

[4] 馬宏源,王洪福,張壽.在熱腔中實(shí)現(xiàn)Grover量子搜索算法[J].延邊大學(xué)學(xué)報(bào)(自然科學(xué)版),2008,34(1):27-30.

[5]YEAL,GUOGC.SchemeforimplementingquantumdensecodingincavityQED[J].PhysicalReviewA,2005, 71(3):309-315.

[6] 張煜東,韋耿,吳樂南.一種改進(jìn)的Grover量子搜索算法[J].信號(hào)處理,2009,25(2):256-259.

[7]PROTOPOPESCUV,BARHENJ.Solvingaclassofcontinuousglobaloptimizationproblemsusingquantumalgorithms[J].PhysicsLettersA,2002,296:9-14.

[8] 韓廣甫.Grover量子搜索算法的改進(jìn)及其在圖像檢索中的應(yīng)用[D].南京:南京郵電大學(xué)通信與信息工程學(xué)院,2013.[9]CHRISTOPHD,PETERH.Aquantumalgorithmforfindingtheminimum[J/OL].QuantumPhysics,http://xxx.lanl.gov/9607014.PDF,1999.

[10] 馬穎.基于量子計(jì)算理論的優(yōu)化算法研究[D].西安:西北工業(yè)大學(xué)電子信息學(xué)院，2014:32-48.

[11] ?MER B.A procedural formalism for quantum computing[D].Vienna:Department of Theoretical Physics,Technical University of Vienna,1998.

[12] ?MER B.Structured quantum programming[D].Vienna:Department of Theoretical Physics,Technical University of Vienna,2003.

[13] CHUANG I L,GERSHENFELD N,KUBINEC M.Experimental implementation of fast quantum searching[J].Physical Review Letters,1997,79(2):325-328.

[14] JONES J A,MOSCA M,HANSEN R H.Implementation of quantum search algorithm on a quantum computer[J].Nature,1998,393(6683):344-346.

[15]KWIAT P G,MITCHELL J R,SCJWOMDT P D D,et al.Grover's search algorithm:an optical approach[J].Journal of Modern Optics,1999,47(2):257-266.

[16] GROVER L K. Quantum computers can search rapidly by using almost any transformation[J]. Physical Review Letters, 1998,80(19): 4329-4332.

[17] GROVER L K. Fixed-point quantum search[J]. Physical Review Letters, 2005, 95:150501.

[18] GROVER L K. Rapid sampling though quantum computing[C]//Proceedings of the thirty-second annual ACM symposium on Theory of computing.New York:ACM, 2000:618-626.

[19] 蘇曉琴，郭光燦.量子通信與量子計(jì)算[J].量子電子學(xué)報(bào)，2004,21(6):706-718.

〔責(zé)任編輯宋軼文〕

ThesimulationofGroverquantumsearchalgorithm

ZHANGHongtao,DAIYongtao,TULingying*,SHUJun,XIONGHongmei,HUYifan

(NanoelectronicTechnologyandMicro-SystemLaboratory,SchoolofElectricalandElectronicEngineering,HubeiUniversityofTechnology,Wuhan430068,Hubei,China)

Keywords:Groverquantumsearchalgorithm;quantumprogramminglanguage;simulation

Abstract:The quantum programming language is used in quantum computation to the research of quantum search algorithm, and then simulated the algorithm in Linux operating systems. The simulation results are tallied with theoretic ones, which verified the time complexity of Grover's quantum searching algorithm is),butthealgorithm′stimecomplexityonclassicalcomputersisO(N).Therefore,it′stwotimesofaccelerationoftheclassicalsearchalgorithm.Andtheimportofquantumprogramminglanguageprovidedapowerful-convenientanduniversaltoolfortheresearchofquantumsearchalgorithm.

文章編號(hào)：1672-4291(2016)03-0007-04

doi:10.15983/j.cnki.jsnu.2016.03.132

收稿日期：2015-08-18

基金項(xiàng)目：武漢市科技局“十城千輛新動(dòng)力汽車計(jì)劃”項(xiàng)目(2013011801010600)

*通信作者：凃玲英，女，副教授。E-mail:tuly.hbgd@163.com

中圖分類號(hào)：TP301.6

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