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

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

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

?

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

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

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

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

MR:Subjectclassification: 68Q12,81P68

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

1量子Grover算法

1.1Grover量子搜索算法的原理

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

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

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

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

第三步：對最后分量做“Z操作”變換，標出真解，且只有真解的幅度才是負值。

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

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

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

1.3Grover量子搜索算法的應用

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

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

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

2.2grover.qcl偽代碼

procedure grover(intn) {

intl=floor(log(n,2))+1; //量子比特數(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; // 進行測量操作

print “measured”,x;

} untilx==n;

reset; // 將所有量子寄存器復位

}

2.3實驗結(jié)果及分析

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

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

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

3結(jié)語

參考文獻:

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

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

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

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

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

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

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

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

[10] 馬穎.基于量子計算理論的優(yōu)化算法研究[D].西安:西北工業(yè)大學電子信息學院，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].量子電子學報，2004,21(6):706-718.

〔責任編輯宋軼文〕

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.

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

doi:10.15983/j.cnki.jsnu.2016.03.132

收稿日期：2015-08-18

基金項目：武漢市科技局“十城千輛新動力汽車計劃”項目(2013011801010600)

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

中圖分類號：TP301.6

文獻標志碼：A