Grover算法量子處理架構(gòu)的設(shè)計與模擬

張洪濤, 代永濤, 凃玲英

(湖北工業(yè)大學(xué) 電氣與電子工程學(xué)院, 湖北 武漢 430068)

?

Grover算法量子處理架構(gòu)的設(shè)計與模擬

張洪濤, 代永濤, 凃玲英

(湖北工業(yè)大學(xué) 電氣與電子工程學(xué)院, 湖北 武漢 430068)

針對混合架構(gòu)經(jīng)典-量子算法的量子算法處理單元，設(shè)計基于Grover算法的量子處理架構(gòu).將一種用于量子計算仿真的量子程序設(shè)計語言引入Grover量子搜索算法中，并在Linux操作系統(tǒng)中進(jìn)行執(zhí)行與模擬.結(jié)果表明：所提架構(gòu)可以提高量子搜索算法的執(zhí)行性能;利用反饋調(diào)節(jié)可以有效地實現(xiàn)量子搜索算法的最佳性能.

Grover量子搜索算法; 量子處理架構(gòu); 量子程序設(shè)計語言; 仿真

量子計算機[1]是一種遵循量子力學(xué)規(guī)律，進(jìn)行高速運算、存儲及處理量子信息的物理裝置，計算速度較超級計算機提高數(shù)十億倍.由于它利用量子系統(tǒng)的可逆運算的特征，可以有效解決耗熱問題.量子計算機與經(jīng)典計算機技術(shù)相比,具有較高的計算性能，所以受到了科學(xué)界和高新產(chǎn)業(yè)界的青睞[2].近幾年，已有許多學(xué)者和公司對其進(jìn)行了進(jìn)一步研究及完善，先后在量子仿真計算框架[3-4]、量子計算機體系結(jié)構(gòu)[5-11]、量子處理執(zhí)行效率[12]等方面提出了多種改進(jìn)措施，并取得了較為矚目的研究成果.因此，量子處理的研究為運行量子算法的量子處理器的體系結(jié)構(gòu)的研究提供了一種新思路，實現(xiàn)量子保密通信技術(shù)在電子商務(wù)和數(shù)據(jù)中心安全方面的應(yīng)用，具有一定的軍事和經(jīng)濟效益，應(yīng)用前景廣泛.Grover量子搜索算法[13-16]可用于圖的著色、最短路徑、排序等問題的求解，還可以有效地破譯DES密碼體系，已經(jīng)形成一個能夠適應(yīng)各種不同搜索需求且較為完整的搜索算法體系.本文在設(shè)計量子計算的核心量子處理器中,采用基于Grover量子搜索算法的新思路，提出一種基于Grover量子搜索算法的量子處理單元QAPU架構(gòu)的方案.

1 量子算法處理單元

1.1 量子計算機系統(tǒng)

量子算法處理單元(quantum algorithm processing unit，QAPU)[17-18]是可以運行量子算法的量子裝置，它需要一個混合的體系結(jié)構(gòu)執(zhí)行量子和經(jīng)典操作，其對應(yīng)操作分別運行于量子計算機和經(jīng)典計算機上.QAPU可作為量子計算機系統(tǒng)中的量子節(jié)點，其中,量子計算機系統(tǒng)是由大量的小節(jié)點和量子互聯(lián)總線構(gòu)成.節(jié)點執(zhí)行實際的計算，并且每一個節(jié)點由量子部分和經(jīng)典部分兩部分組成.量子部分包含量子數(shù)據(jù)，經(jīng)典部分包含實時測量和控制電路的量子裝置，相應(yīng)的操作分別由量子部分的節(jié)點和經(jīng)典部分的節(jié)點進(jìn)行執(zhí)行，并用QAPU和CPU代替.量子計算機系統(tǒng)的原理框圖,如圖1所示.圖1中：虛線表示非實時通信；實線表示實時通信.

1.2 量子處理單元的架構(gòu)

圖1 量子計算機系統(tǒng)的原理框圖 圖2 量子處理單元的架構(gòu)Fig.1 Block diagram of quantum computer system Fig.2 Framework of quantum algorithm processing unit

2 架構(gòu)設(shè)計與模擬實現(xiàn)

2.1 量子處理架構(gòu)的設(shè)計

Grover量子搜索算法包括不同量子態(tài)的n量子比特的|x〉和1量子比特的|y〉，分別對應(yīng)于控制寄存器和目標(biāo)寄存器的輸入.作為該算法的量子電路，算法從計算機的初態(tài)|0〉?n開始，用Hadamard變換使計算機處于均衡疊加態(tài)，即

式中:|τ〉為尋找的標(biāo)記態(tài)；N=2n為元素個數(shù).

量子搜索算法由反復(fù)應(yīng)用Grover迭代(G)或Grover算子的量子子程序組成,即

圖3 Grover量子搜索算法的量子處理框架Fig.3 Quantum processing framework for Grover′s quantum search algorithm

2.2 量子模擬平臺的搭建及相關(guān)配置

QCL(quantumcomputationlanguage)[21-22]是一個結(jié)構(gòu)化命令式量子程序設(shè)計語言，其語法和C/Pascal類似.它提供了基本的量子運算符和量子態(tài)的表示方法，能實現(xiàn)量子位的各種幺正變換及測量操作.在Linux操作系統(tǒng)中有如下5個安裝過程.

1) 下載QCL的安裝包.

2) 下載并安裝bison和flex工具.

3) 安裝依賴庫，如libplot2c2和libplot-dev等.

4) 下載一個最新的readline文件，然后解壓并安裝.tarxvzfreadline-5.2.tar.gz; /configure;make;makeinsatll.

5) 將qcl-0.6.4.tar.gz解壓后，進(jìn)入所在文件夾；然后，直接運行make命令就會在當(dāng)前文件夾中生成qcl可執(zhí)行文件,至此說明qcl已經(jīng)安裝成功；最后，直接運行./qcl，就可以進(jìn)入qcl量子模擬環(huán)境.

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

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

為了進(jìn)一步說明搜索過程中幅值變化情況，在n=20量子比特的搜索空間N=220=1 048 576中搜索某特定元素1 000 000， 特定元素(所需記錄)和非特定元素(其他記錄)的幅值隨迭代次數(shù)的變化關(guān)系，如圖4(d)，(f)所示.

(a) n=100 (b) n=10 000

(c) n=1 000 000 (d) 所需量子比特數(shù)和迭代次數(shù)

(e) 成功率與M/N的關(guān)系 (f) 幅值隨迭代次數(shù)的變化關(guān)系圖4 Grover量子搜索算法的模擬仿真Fig.4 Simulation of Grover quantum search algorithm

由圖4(d)可知：執(zhí)行此次搜索問題所需的量子比特數(shù)和迭代次數(shù)分別為20和805.

由圖4(e)可知：Grover算法僅在若干離散點處的成功率為1，隨著M/N的增大，成功率迅速下降，直至失效.當(dāng)要搜索的目標(biāo)數(shù)目超過數(shù)據(jù)庫中記錄總數(shù)的1/4時(如N=10 000)，Grover量子搜索算法搜索成功的概率呈下降趨勢；且當(dāng)要搜索的目標(biāo)數(shù)目超過數(shù)據(jù)庫記錄的一半時(如N=1 000 000)，算法幾乎失效.

3 結(jié)束語

[1] 方糧,劉汝霖.量子計算機: 量子算法與物理實現(xiàn)[J].計算機工程與科學(xué),2012,34(8):32-43.

[2]WEIMERH,ULLERM,LESANOVSKYI,etal.Arydbergquantumsimulator[J].NaturePhysics,2010,6(5):382-388.

[3]AGHAEIMRS,ZUKARNAINZA,MAMATA,etal.Anarchitecturalframeworkforquantumalgorithmsprocessingunit[J].LectureNotesinEngineeringandComputerScience,2010,2180(1):303-309.

[4]LEEYH,KHALIL-HANIM,MARSONOMN.AnFPGA-basedquantumcomputingemulationframeworkbasedonserial-parallelarchitecture[J].InternationalJournalofReconfigurableComputing,2016,2016(5):1-18.

[5]WANGAnming.Quantumcentralprocessingunitandquantumalgrorithm[J].ChinesePhysicsLetters,2002,19(5):620-622.

[6] 薛飛.量子計算的核磁共振實驗實現(xiàn)及量子CPU的設(shè)計[D].合肥：中國科學(xué)技術(shù)大學(xué),2004:90-96.

[7]BRIANRLC,COREYIO,GRANVILLEEO,etal.Classicalemulationofaquantumcomputer[J].InternationalJournalofQuantumInformation,2016，14(1)：1-12.

[8]METERRV,OSKINO.Architecturalimplicationsofquantumcomputingtechnologies[J].ACMJournalonEmergingTechnologiesinComputingSystems,2006,2(1):31-63.

[9]RONNOWTF,WANGZ,JOBJ,etal.Defininganddetectingquantumspeedup[J].Science,2014,345(6195):420-424.

[10] TéLLEZ V H,CAMPERO A,LUGA C,et al. An architecture of quantum CPU[J]. NSTI-Nanotech,2007(3):205-208.

[11] 吳楠,宋方敏.一種高效容錯的通用量子計算機體系結(jié)構(gòu)[J].計算機學(xué)報,2009,32(1):161-168.

[12] 宋輝.量子計算機體系結(jié)構(gòu)及模擬技術(shù)的研究與實現(xiàn)[D].長沙：國防科學(xué)技術(shù)大學(xué),2003:25-33.

[13] GROVER L K.A fast quantum mechanical algorithm for database search[C]∥28th Annual ACM Symposium on the Theory of Computation.New York:ACM Press,1996:212-219.

[14] 盧春紅.3量子位的Grover量子搜索算法的核磁共振的仿真實現(xiàn)[D].無錫：江南大學(xué),2007:5-21.

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

[16] 韓廣甫.Grover量子搜索算法的改進(jìn)及其在圖像檢索中的應(yīng)用[D].南京：南京郵電大學(xué),2013:13-34.

[17] AGHAEI M R S,ZUKARNAIN Z A.A quantum processing framework for quantum algorithms[J].Majlesi Journal of Electrical Engineering,2012,6(3):1-7.

[18] AGHAEI M R S,ZUKARNAIN Z A.A hybrid architecture approach for quantum algorithms[J].Journal of Computer Science,2009,5(10):725-731.

[19] MICHAEL A N,CHUANG I L.量子計算和量子信息(一)[M].趙千川,譯.北京:清華大學(xué)出版社,2003:228-231.

[20] ZALKA C.Grover′s quantum searching algorithm is optimal[J].Physical Review A,1997,60(4):2746-2751.

[21] ?MER B.A procedural formalism for quantum computing[D].Vienna：Technical University of Vienna,1998：16-83.

[22] ?MER B.Structured quantum programming[D].Vienna：Technical University of Vienna,2003：45-102.

(責(zé)任編輯： 陳志賢 英文審校： 吳逢鐵)

Design and Simulation of Quantum Processing Framework Based on Grover Algorithm

ZHANG Hongtao, DAI Yongtao, TU Lingying

(School of Electrical and Electronic Engineering, Hubei University of Technology, Wuhan 430068, China)

As for a quantum algorithm processing unit with the hybrid architecture for classical-quantum algorithms, the quantum processing framework based on Grover′s algorithm is designed. By applying the quantum programming language which is used in quantum computation to the research of Grover quantum search algorithm, then implemented and simulated the algorithm in Linux operating systems. The results show that the proposed framework can be used to improve the implementation performance of Grover algorithm. And the best performance of Grover algorithm can be achieved by using the feedback regulation.

Grover quantum search algorithm; quantum processing framework; quantum programming language; simulation

10.11830/ISSN.1000-5013.201606017

2016-04-26

張洪濤(1963-)，男，教授，博士，主要從事量子計算與量子信息、嵌入式系統(tǒng)開發(fā)的研究.E-mail:zhanght@mail.hbut.edu.cn.

湖北省武漢市科技局資助項目(2013011801010600)

TP 301

A

1000-5013(2016)06-0749-05