Grover算法量子處理架構的設計與模擬

張洪濤, 代永濤, 凃玲英

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

?

Grover算法量子處理架構的設計與模擬

張洪濤, 代永濤, 凃玲英

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

針對混合架構經典-量子算法的量子算法處理單元，設計基于Grover算法的量子處理架構.將一種用于量子計算仿真的量子程序設計語言引入Grover量子搜索算法中，并在Linux操作系統中進行執行與模擬.結果表明：所提架構可以提高量子搜索算法的執行性能;利用反饋調節可以有效地實現量子搜索算法的最佳性能.

Grover量子搜索算法; 量子處理架構; 量子程序設計語言; 仿真

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

1 量子算法處理單元

1.1 量子計算機系統

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

1.2 量子處理單元的架構

圖1 量子計算機系統的原理框圖 圖2 量子處理單元的架構Fig.1 Block diagram of quantum computer system Fig.2 Framework of quantum algorithm processing unit

2 架構設計與模擬實現

2.1 量子處理架構的設計

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

式中:|τ〉為尋找的標記態；N=2n為元素個數.

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

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

2.2 量子模擬平臺的搭建及相關配置

QCL(quantumcomputationlanguage)[21-22]是一個結構化命令式量子程序設計語言，其語法和C/Pascal類似.它提供了基本的量子運算符和量子態的表示方法，能實現量子位的各種幺正變換及測量操作.在Linux操作系統中有如下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解壓后，進入所在文件夾；然后，直接運行make命令就會在當前文件夾中生成qcl可執行文件,至此說明qcl已經安裝成功；最后，直接運行./qcl，就可以進入qcl量子模擬環境.

2.3 實驗結果及分析

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

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

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

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

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

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

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

3 結束語

[1] 方糧,劉汝霖.量子計算機: 量子算法與物理實現[J].計算機工程與科學,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] 薛飛.量子計算的核磁共振實驗實現及量子CPU的設計[D].合肥：中國科學技術大學,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] 吳楠,宋方敏.一種高效容錯的通用量子計算機體系結構[J].計算機學報,2009,32(1):161-168.

[12] 宋輝.量子計算機體系結構及模擬技術的研究與實現[D].長沙：國防科學技術大學,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量子搜索算法的核磁共振的仿真實現[D].無錫：江南大學,2007:5-21.

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

[16] 韓廣甫.Grover量子搜索算法的改進及其在圖像檢索中的應用[D].南京：南京郵電大學,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].趙千川,譯.北京:清華大學出版社,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.

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

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-)，男，教授，博士，主要從事量子計算與量子信息、嵌入式系統開發的研究.E-mail:zhanght@mail.hbut.edu.cn.

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

TP 301

A

1000-5013(2016)06-0749-05