Grover量子搜索算法的模拟实现

张洪涛, 代永涛, 凃玲英, 舒　军, 熊红梅, 胡一凡

(湖北工业大学 纳米电子技术与微系统实验室,电气与电子工程学院, 湖北 武汉 430068)



Grover量子搜索算法的模拟实现

张洪涛, 代永涛, 凃玲英*, 舒军, 熊红梅, 胡一凡

(湖北工业大学 纳米电子技术与微系统实验室,电气与电子工程学院, 湖北 武汉 430068)

摘要：将一种用于量子计算仿真的量子程序设计语言引入Grover量子搜索算法中，并在Linux操作系统中模拟实现该算法。仿真结果与理论分析结果的一致性验证了Grover量子搜索算法可以将搜索问题从经典的N步缩小到步，是对经典搜索算法的二次加速。同时，量子程序设计语言的引入，为量子搜索算法的研究提供了一种强大、简便、通用的工具。关键词:Grover量子搜索算法; 量子程序设计语言; 仿真

MR:Subjectclassification: 68Q12,81P68

Grover量子搜索算法可用于图的着色、最短路径、排序等问题的求解，还可以有效破译DES密码体系，具有加速搜索密码系统密钥的潜在用途。经过多年的改进及研究扩展，Grover量子搜索算法不断趋于完善，目前已经形成一个能够适应各种不同搜索需求且较为完整的搜索算法体系。

1量子Grover算法

1.1Grover量子搜索算法的原理

Grover量子搜索算法[16-18]的基本思想是通过对初始等幅叠加态进行幺正变换，反复应用Grover 量子迭代过程来抑制非目标项的概率幅而放大所要寻找的目标项的概率幅。最后,通过对量子态进行测量，以接近1的概率搜索到目标项。

1.2Grover量子搜索算法具体执行步骤

第一步：初始化，产生一个等幅度的状态叠合。

第二步：完成对判决函数的并行计算。

第三步：对最后分量做“Z操作”变换，标出真解，且只有真解的幅度才是负值。

第四步：对|x,f(x)〉的第一分量执行D变换，增大真解b对应状态|b,1〉的出现概率。其中D变换的变换矩阵D=(dij)2n×2n为

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

第五步：重复执行第三步至第四步k次后进行观察，得到观察结果|x,1〉，并将x作为真解输出。Grover量子搜索算法的流程图见图1。

1.3Grover量子搜索算法的应用

2Grover量子搜索算法的模拟实现

2.1量子程序设计语言QCL的基本要素

QCL是一个结构化命令式量子程序设计语言[10-11]，其语法和C/Pascal类似。量子操作由函数和量子过程进行定义，包含了丰富的量子数据类型，并引入量子寄存器和基于条件变换的量子控制结构。其语句分为简单语句、流程控制语句、交互命令3类。其中，简单语句包括赋值语句、输入输出语句、子程序调用语句、测量语句和初始化语句；流程控制语句包括循环语句、如果语句和异常终止语句；交互语句包括模拟语句、开壳语句、列表语句和退出语句。类型分为标量(整型、实型、复型、字符串型和布尔型)、张量(向量、矩阵和n 阶张量)以及量子(通用寄存器qureg、量子常量quconst、目标寄存器quvoid和擦除寄存器quscratch)3类,并设计了透明的擦除机制以保证其量子位得以充分利用。具体来说，它主要包含以下几方面特点：第一，保留了传统数据类型、函数、控制流以及交互式I/O，具有传统程序结构的特色；第二， 提供了各种量子数据类型以及量子位存储和寄存的表示方法；第三，反映了量子计算的酉变换之可逆性、状态之不可观察性和量子位之非定域性等特点；第四，实现了量子算法的可逆的幺正变换和不可逆的测量操作。

2.2grover.qcl伪代码

procedure grover(intn) {

intl=floor(log(n,2))+1; //量子比特数

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

intx;

inti;

quregq[l]; //为量子堆中的l位变量q分配空间

quregf[1];

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

{

reset;

H(q);// 制备叠加态

fori= 1 tom{ // 主循环

query(q,f,n); // 执行查询操作

CPhase(pi,f); // 受控相位变换

!query(q,f,n); // 不执行查询操作

diffuse(q); // 离散操作

}

measureq,x; // 进行测量操作

print “measured”,x;

} untilx==n;

reset; // 将所有量子寄存器复位

}

2.3实验结果及分析

当n=100、10 000、1 000 000时，其Grover量子搜索算法搜索结果分别如图2中a、b和c所示。为更直观地反映该算法的成功率，我们通过数据模拟得到算法的成功率P与搜索问题的解在整个搜索空间中所占的比例M/N之间的关系，如图2中d所示。

图2Grover量子搜索算法搜索结果及成功概率

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

3结语

参考文献:

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

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

[3] 卢春红.3量子位的Grover量子搜索算法的核磁共振的仿真实现[D].无锡:江南大学物联网工程学院,2007.

[4] 马宏源,王洪福,张寿.在热腔中实现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] 马颖.基于量子计算理论的优化算法研究[D].西安:西北工业大学电子信息学院，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