HHL量子算法的普适量子线路设计.pdf
《HHL量子算法的普适量子线路设计.pdf》由会员分享,可在线阅读,更多相关《HHL量子算法的普适量子线路设计.pdf(12页珍藏版)》请在咨信网上搜索。
1、第 40 卷 第 5 期2023 年 9 月量 子 电 子 学 报CHINESE JOURNAL OF QUANTUM ELECTRONICSVol.40 No.5Sep.2023HHLHHL量子算法的普适量子线路设计量子算法的普适量子线路设计季 雯 1,叶 宾 1,2*(1 中国矿业大学信息与控制工程学院,江苏 徐州 221116;2 地下空间智能控制教育部工程研究中心,江苏 徐州 221116)摘要:HHL(Harrow-Hassidim-Lloyd)量子算法实现了近似求解线性方程组Ax=b,是许多复杂量子算法的重要组成部分。尽管HHL量子算法相比于经典算法能够实现指数级加速,但是目前HH
2、L量子算法大多为抽象的算法描述或分析,所设计出的量子线路规模很小,且不具有普适性。在分析HHL量子算法原理的基础上,使用通用量子门自上而下地设计了算法的关键模块,包括酉矩阵的通用量子门分解模块、量子相位估计模块、量子全加器与乘法器模块、量子态条件旋转变换模块等,从而实现了求解线性方程组的普适量子线路。利用IBM qiskit量子计算开发平台进行的量子仿真实验表明,所设计的HHL量子线路能够求解一般形式的线性方程组,且易于扩展为中大规模的量子线路。关 键 词:量子计算;HHL量子算法;量子线路;量子相位估计;IBM qiskit平台中 图 分 类 号:O431.2;TP301 文 献 标 识 码
3、:A 文章编号:1007-5461(2023)05-00747-12A general quantum circuit design method for HHL quantum algorithmJI Wen 1,YE Bin 1,2*(1 School of Information and Control Engineering,China University of Mining and Technology,Xuzhou 221116,China;2 Engineering Research Center of Intelligent Control for Underground S
4、pace,Ministry of Education,Xuzhou 221116,China)AbstracAbstract t:Harrow-Hassidim-Lloyd(HHL)quantum algorithm has basically realized the function of solving linear equation Ax=b,and it is also the essential ingredient of many complex quantum algorithms.Although HHL quantum algorithm achieves exponent
5、ial speedup over its classical counterpart,most of the current HHL quantum algorithms are abstract algorithm descriptions or their analyses.Especially,the HHL quantum circuits developed so far are small in scale and not general.By analyzing the basic units of HHL quantum algorithm,the key modules of
6、 HHL algorithm,including a unitary matrix decomposition module by general quantum gates,a quantum phase estimation module,a quantum full adder and DODOI I:10.3969/j.issn.1007-5461.2023.05.014基金项目:徐州市科技计划项目(KC22286),河南省网络密码技术重点实验室研究课题(LNCT2019-S06)作者简介:季 雯(1996-),女,江苏徐州人,研究生,主要从事量子计算方面的研究。E-mail:导师简介
7、:叶 宾(1980-),河南南阳人,博士,副教授,硕士生导师,主要从事量子计算和量子信息方面的研究。E-mail:收稿日期:2021-09-24;修改日期:2021-11-22*通信作者。量 子 电 子 学 报40 卷multiplier module,and a conditional rotation module of quantum state,etc,were designed from top to down using general quantum gates,thus achieving a general quantum circuit for solving linear
8、 equations.Quantum simulations on the IBM qiskit quantum computation development platform show that the designed quantum circuits are suitable for solving more general linear equations and can be easily extended to medium or large-scale quantum circuits.K Keyey wordswords:quantum computation;HHL qua
9、ntum algorithm;quantum circuit;quantum phase estimation;IBM qiskit platform0 引 言HHL量子算法是由Harrow、Hassidim及Lloyd1提出的一种求解量子线性系统问题的量子算法,其利用量子态的相干叠加与纠缠等特性实现稀疏线性方程组 Ax=b 的快速求解,与经典的线性方程组求解算法相比,HHL量子算法可以达到指数级加速。对于一个 NN 的矩阵 A,若 A 的条件数为,则 HHL量子算法的时间复杂度为 O(2log2 N)(其中 为计算精度)。HHL量子算法与Shor质因数分解量子算法和Grover量子搜索算法一
10、样,已成为许多复杂量子算法的基本组成部分,且广泛应用于量子支持向量机2、量子判别分析3、量子线性回归4、量子无监督学习5、量子神经网络6等量子机器学习算法中。在当前的大数据时代,HHL量子算法带来的潜在加速收益非常明显7,8。基于 HHL 量子算法,Childs 等9应用哈密顿量的快速模拟,将 HHL 量子算法的计算复杂性由 O(2log2 N)降低为 O(2log2 Nlog21);Wossnig等10提出了一种求解非稀疏线性系统的量子算法,与经典算法相比带来了平方加速;Chen等11提出了用于求解布尔多项式方程组的量子算法。对于小规模的二元线性方程组,HHL量子算法已分别在光量子计算机和核
11、磁共振量子信息处理器上得到了实现和验证12,13。虽然目前HHL量子算法在算法分析与实验验证方面取得了以上成果,但其仍处于较为抽象的算法描述阶段,对于一般形式的线性方程组,所设计出的量子线路规模非常小,且没有完整和普适的量子线路设计方法。为了在中等规模甚至大规模的量子计算机上实现HHL量子算法,本文利用厄米矩阵的Pauli分解及乘积公式实现了一般哈密顿量的量子模拟线路,分别设计了量子相位估计、量子加法与乘法运算、量子态的条件旋转变换等重要算法模块对应的量子线路,经过IBM qiskit量子软件平台14 的仿真验证,构建了一种普适的求解线性方程组的量子线路。1 HHL算法原理线性方程组求解问题是
12、对于已知矩阵 ARNN 和 向量bRN,求出使方程组 Ax=b 成立的向量 xRN。利用量子计算机求解线性方程组Ax=b,首先要进行量子态编码。假设 A 为厄米矩阵,且 A 的维数 N=2nb(nb为进行量子态编码所用量子比特数目)。对于归一化单位向量 b(或者 x),将其第 i 个元素编码为量子叠加态 b (或者量子态 x)的第 i 个基态,那么HHL量子算法就是求出 x 以满足A x=b。HHL量子算法主要由三个基本模块组成,即量子相位估计模块、量子态受控旋转模块和量子态反演解算模块,如图1所示。图1共包含三个量子寄存器,其中量子寄存器F是1位辅助量子比特寄存器,寄存器L748第 5 期季
13、 雯等:HHL量子算法的普适量子线路设计用来存储矩阵 A 的特征值的二进制近似,寄存器B用于存储量子态b以及演化后所得量子态 x,三个量子寄存器的每个量子比特初态都为 0。图1 HHL量子线路概图。(a)量子相位估计模块(QPE);(b)量子态受控旋转模块;(c)量子态反演解算模块(QPE)15Fig.1 Diagram of HHL quantum circuit.(a)Quantum phase estimation module(QPE);(b)Quantum state controlled rotation module;(c)Time-reversal of the QPE mod
14、ule(QPE)15HHL量子算法的步骤如下1,15:1)将量子寄存器B初始化为量子态 b(量子寄存器B共有nb 个量子比特,且 2nb=N);2)量子相位估计 QPE,如图1(a)。厄米矩阵 A 具有谱分解 A=i=1Niuiui,其中 ui 为对应于实特征值 i 的特征向量,所以 U=ei2A 为酉矩阵,且具有特征值 eii2 和特征向量 ui。如果量子寄存器 L 的初态为 0nl,量子寄存器 B 的状态为 ui,则对矩阵 U 应用量子相位估计算法16可实现映射 0nlui iui,其中 i 为特征值 i 在量子寄存器L中的二进制表示。更一般地,若取矩阵 A的特征向量 ui 作为基向量,B
15、的状态 b 可表示为 b=i=1Nbiui,biR,此时将量子态 b=i=1Nbiui 输入到量子相位估计算法,即可实现映射 i=1Nbi0nluii=1Nbiiui;3)计算 i 的倒数 1/i,并以存储 1/i 的L作为控制寄存器,对初态为 0 的辅助量子比特F施加受控旋转量子运算如图1(b),使F的状态近似为1-C22j0+Cj1(其 中C是 归 一 化 常 数)。此 时,对 量 子 寄 存 器 F、L 和 B 完 成 映 射 i=1Nbi0 i uii=1Nbi(1-C22i0+Ci1)i ui;4)对量子寄存器L和B进行量子相位估计 的 状 态 反 演 如 图 1(c),可 得 i=
16、1Nbi(1-C22i0+Ci1)i uii=1Nbi(1-C22i0+Ci1)0nl ui;5)对辅助量子寄存器F进行量子测量。若测量结果为1,则量子寄存器L和B在测量后的量子态为1i=1N|bi/i2i=1Nbii0nl ui,因此B的状态与线性方程组的解x=A-1b=i=1N(-1iuiui)(biui)=i=1Nbiiui相比只相差了一个归一化因子。749量 子 电 子 学 报40 卷对于一般形式的线性方程组 Ax=b,若 A 不是厄米矩阵,则可以通过构造厄米矩阵 0AA0,将 Ax=b 增广转化为一个维数更高的线性方程组 0AA0 0 x=b0,并利用上述HHL量子算法进行求解。2
17、HHL量子电路设计2.1 量子相位估计模块对于一个酉矩阵 U,它具有模为1的复特征值 ei 和特征向量 ui,量子相位估计算法的目的即是在一定的误差范围内估算相位 的值16。量子相位估计算法的框架及概图如图2所示,图中 H 表示Hadamard量子门,QFT 表示量子傅里叶逆变换算法,Uj 表示逐次以量子寄存器L中的量子比特为控制比特且以寄存器B为目标量子寄存器的受控 Uj 运算。图2 量子相位估计算法的量子线路(a)框架和(b)概图Fig.2(a)Quantum circuit framework and(b)diagram of quantum phase estimation algor
18、ithm对于厄米矩阵A,相应的酉矩阵 U=ei2A具有特征值 ei2 和特征向量 u,其中 u 为对应于A的实特征值 的特征向量。若将 U 的特征向量 u 载入到图2中的量子寄存器B,且以受控 Uj 进行演化,并经量子傅里叶逆变换之后,量子相位估计算法最终对量子寄存器L进行量子测量,将给出二进制串lnl-1lnl-2l1l0。此时A对应于特征向量 u 的实特征值 可被估算为(lnl-1lnl-2l1l0)bin/2nl。量子相位估计算法的具体步骤如下:1)将 U 的特征向量 u 载入到量子寄存器B;2)对量子寄存器L中的每个量子比特都执行Hadamard量子门运算 如图2(b),得到量子态12
19、nl(0+1)nl u;3)从量子寄存器L的最低位L0开始,依次施加受控 Uj(其中j=2nl-12nl-221 20)量子门作用于量子寄存器B上 如图 2(b)所示。由于U2nl-1u=U2nl-2UU u=U2nl-2e4iu=e2i2nl-1u以及0 u+1 e2iu=(0+e2i1)u,经过一系列受控 Uj 运算,可得到量子态12nlk=02nl-1e2ikk u,其中 k 为存储在量子寄存器L 中 的 nl 位 二 进 制 数;4)对 量 子 寄 存 器 L 进 行 量 子 傅 里 叶 逆 变 换,可 得12nlk=02nl-1e2ik|k|uQFT12nlx=02nl-1k=02n
20、l-1e-2ik2nl()x-2nl|x|u,由于x的幅值在 x=2nl 时取得最大值,因此若对量子寄存器L进行量子测量,测量得到 2nl 的概率是最大的。750第 5 期季 雯等:HHL量子算法的普适量子线路设计2.1.1酉矩阵U的通用量子门分解为了利用通用量子门设计HHL量子线路,必须根据厄米矩阵A实现图2(b)中的一系列受控 Uj 运算。将结合厄米矩阵A的泡利矩阵分解以及积公式17,18,设计和实现酉矩阵 U 的量子线路。利用积公式设计的量子电路更具有直观性,且易于集成。基于泡利矩阵 X=0110、Y=0-ii0、Z=100-1和单位矩阵 I=1001,任意厄米矩阵A2nb2nb都可以进
21、行泡利矩阵分解,即A2nb2nb=G1G2GnbIXYZaG1G2Gnb(G1G2Gnb),(1)式中:系数aG1G2Gnb=12nbtr(G1G2Gnb)A2nb2nb,tr()表示矩阵的迹。根据(1)式,酉矩阵 U=ei2A 可写为 U=ei2G1G2GnbaG1G2Gnb(G1G2Gnb),结合积公式的一阶近似19,U 可进一步写为U=limm(G1G2GnbIXYZei2aG1G2Gnb(G1G2Gnb)/m)m.(2)以下对(2)式中形如 ei2aG1G2Gnb(G1G2Gnb)/m的运算项(简写为ei2a(G1G2Gnb)/m)进行量子线路设计。对于多量子比特运算 ei2a(G1G
22、2Gnb)/m,如果其中某个 Gi=I,则表明量子寄存器B的第i位无须进行任何运算;反之,如果 GiXYZ,则从所有 Gi 中选取i的最大值 i*=max i|GiXYZ,对量子寄存器B的第 i*位施加单比特旋转门 ei2aX/m=Rx(-22am),相应的量子线路如图3(a)所示。进一步,根据Clifford量子线路和量子旋转门的性质,可得 CNOT(Rx(a)I)CNOT=e-ia2CNOT()XICNOT=e-ia2XX(其中CNOT为受控量子非门),因此图3(a)中的单量子比特运算 ei2aX/m 扩展为双比特量子运算 ei2aXX/m 的量子线路,如图3(b)所示。类似地,多量子比特
23、运算 ei2aXXX/m 的量子线路如图3(c)所示。以这些单量子比特或多量子比特状态绕X轴的旋转运算为基础,结合 HXH=Z 以及 SXS=Y (其中H=12 111-1为 Hadamard 门,S=100ei2为 量 子 相 位 门),可 实 现 任 意 量 子 比 特 的 旋 转 运 算ei2a(G1G2Gnb)/m。例如,图3(d)(f)分别为量子比特运算 ei2aZ/m、双量子比特运算 ei2aYX/m和多量子比特运算 ei2aYI/m的量子线路。将图3所示的典型量子线路与(1)、(2)式相结合,即可构成酉算符 U=ei2A 的通用量子门近似分解线路。此时,对酉算符 U=ei2A 的
24、近似误差正比于1/m。2.1.2受控 Uj 运算的量子线路当厄米矩阵A的维数较大或者(2)式中m取值较大时,酉算符 U=ei2A 对应的量子线路深度将非常大,这不利于设计受控 Uj 运算的量子线路。在第2.1.1节中详细介绍了 Uj 的设计方法,本研究使用的是IBM qiskit量子计算开发平台20,因此在设计受控 Uj 的量子线路时调用量子线路对象的to_gate()方法,将酉算符 U 封装为1个自定义的量子门U_gate;然后对封装后的量子门U_gate调用U_gate.control(),并以寄存器L中的量子比特为控制位,嵌入到量子线路中,实现1次受控 U 运算 参考图2(b)。需要注意
25、的是,由于全局相751量 子 电 子 学 报40 卷位不可观测,在第2.1.1节中设计酉矩阵 U 的量子线路时并不需要考虑 ei2a(III)/m的项;但是在设计受控 U 运算量子线路时,ei2a/m成为相对相位,是不可忽略的。因此需要利用Phase Kickback方法将相移 ei2a/m 从目标寄存器B等价地转移到寄存器L的相应控制位(如图4所示)。受控 Uj运算由串联j个受控 U 运算的量子线路来实现。图3 酉矩阵U的通用量子门分解中部分量子线路图。(a)单量子比特运算 ei2aX/m;(b)双比特量子运算 ei2aXX/m;(c)多量子比特运算 ei2aXXX/m;(d)量子运算ei2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- HHL 量子 算法 适量 线路 设计
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。