崔競(jìng)一，劉翼鵬，郭建勝

(1.信息工程大學(xué)，河南 鄭州 450001；2.61497部隊(duì)，北京 100089)

0 引言

量子計(jì)算在密碼分析領(lǐng)域中相對(duì)經(jīng)典計(jì)算具有更為強(qiáng)大的優(yōu)勢(shì)。量子計(jì)算的并行能力使得其能夠相對(duì)經(jīng)典計(jì)算實(shí)現(xiàn)一定的加速效果，其中最為著名的算法包括：Shor算法[1]，能夠在大整數(shù)分解問(wèn)題上實(shí)現(xiàn)指數(shù)加速；Grover算法[2]，能夠在無(wú)結(jié)構(gòu)數(shù)據(jù)庫(kù)搜索問(wèn)題上實(shí)現(xiàn)指數(shù)加速。前者直接威脅了RSA、ECC、ECDSA等公鑰密碼體制，后者能夠加速對(duì)稱密碼算法的窮舉攻擊，從而引起了密碼學(xué)者對(duì)量子計(jì)算的關(guān)注。在Shor算法中使用的量子傅里葉變換[3]，能夠相對(duì)經(jīng)典算法實(shí)現(xiàn)指數(shù)加速。如若能夠?qū)⒘孔痈道锶~變換應(yīng)用至其他算法中，則大概率能夠?qū)崿F(xiàn)量子加速，因此人們對(duì)量子傅里葉變換的適用范圍及實(shí)現(xiàn)方案產(chǎn)生了極大的興趣。

目前，量子計(jì)算已經(jīng)不僅僅停留在理論研究的層面，隨著IBM、微軟、Google、D-Wave、Rigett、IonQ等公司著手設(shè)計(jì)了一系列的量子計(jì)算芯片，量子計(jì)算逐漸走向?qū)嵱没Ｔ诹孔佑?jì)算芯片方面，IBM早在2017年便宣布成功研制17量子比特的計(jì)算芯片[4]；2018年英特爾展示了49比特的量子計(jì)算芯片[5]；同年Google展示了72比特的量子計(jì)算芯片[6]；2019年CES上，IBM公司還展示了一臺(tái)20比特的量子計(jì)算機(jī)[7]。在量子計(jì)算云服務(wù)平臺(tái)方面，2017年IBM公司[8]提供了量子計(jì)算云服務(wù)，接入了5量子比特的超導(dǎo)量子計(jì)算芯片，可供遠(yuǎn)程公開(kāi)使用；2017年中科院與阿里巴巴[9]聯(lián)合上線了一個(gè)量子計(jì)算云平臺(tái)；2018年本源量子[10]也上線了超導(dǎo)量子計(jì)算芯片；同年，南方科技大學(xué)[11]上線了4量子比特的NMR量子計(jì)算服務(wù)。量子計(jì)算云服務(wù)的出現(xiàn)，使學(xué)者可以遠(yuǎn)程利用量子計(jì)算芯片實(shí)現(xiàn)理論量子算法[12]。

本文基于IBM公司提供的5量子比特計(jì)算芯片的結(jié)構(gòu)，設(shè)計(jì)出對(duì)應(yīng)的3量子比特傅里葉變換實(shí)現(xiàn)線路，并對(duì)其理論結(jié)果進(jìn)行了分析，同時(shí)給出了對(duì)應(yīng)的實(shí)驗(yàn)驗(yàn)證結(jié)果。

1 相關(guān)知識(shí)

本節(jié)對(duì)IBM量子計(jì)算云服務(wù)編程的相關(guān)知識(shí)與量子傅里葉變換的基礎(chǔ)知識(shí)進(jìn)行介紹。

1.1 IBM量子計(jì)算云服務(wù)簡(jiǎn)介

在IBM Q Experience網(wǎng)站上，可以在線使用圖例式編程方式與量子匯編語(yǔ)言(Quantum Assemble,QASM)編程方式實(shí)現(xiàn)量子算法，同時(shí)還能夠使用IBM公司提供的Qiskit套件進(jìn)行離線編程，然后運(yùn)行調(diào)用網(wǎng)站提供的量子計(jì)算云服務(wù)。在網(wǎng)站上，共提供了基于量子芯片與量子模擬器兩種運(yùn)行方式，其所基于的量子芯片是IBM公司的5量子比特超導(dǎo)量子計(jì)算芯片。

IBM量子計(jì)算云服務(wù)中提供了若干個(gè)基本量子門操作，如表1所示，用戶可基于這些基本量子門操作構(gòu)建出相應(yīng)算法的量子線路，通過(guò)運(yùn)行該量子線路，返回算法的輸出值。

目前，IBM Q Experience提供的量子計(jì)算芯片為ibmqx4結(jié)構(gòu)的IBM Q 5 Tenerife芯片，其具體示意圖如圖1所示，圖中5個(gè)數(shù)字表示5個(gè)量子比特，箭頭由控制比特指向受控比特。

圖1 ibmqx4的結(jié)構(gòu)示意圖

從ibmqx4的結(jié)構(gòu)示意圖中可以看出，其5個(gè)量子比特之間不能夠相互控制，存在一些制約關(guān)系。例如量子比特1僅能夠控制量子比特0，且僅受量子比特2控制。因此在設(shè)計(jì)實(shí)際算法的量子線路時(shí)，需要綜合考慮控制比特與受控比特的關(guān)系，否則所設(shè)計(jì)出的線路可能無(wú)法在ibmqx4結(jié)構(gòu)的量子芯片上實(shí)現(xiàn)。

1.2 量子傅里葉變換

量子傅里葉變換是一個(gè)定義在n維Hilbert空間上的離散傅里葉變換，量子傅里葉變換是一個(gè)幺正變換，定義為如下形式:

(1)

其中ω=ωN=e2πi/N為2n次本原單位根。具體當(dāng)輸入為n量子比特的狀態(tài)|j1…jn-1jn〉時(shí)，其輸出可以寫為:

(2)

2 量子傅里葉變換的線路實(shí)現(xiàn)

本節(jié)對(duì)量子傅里葉變換的實(shí)現(xiàn)方案進(jìn)行研究，首先介紹量子傅里葉變換的線路模型，其次給出ibmqx4結(jié)構(gòu)下常用的基礎(chǔ)線路，最后設(shè)計(jì)給出3比特量子傅里葉變換在ibmqx4結(jié)構(gòu)下的量子線路實(shí)現(xiàn)方案。

2.1 量子傅里葉變換的線路模型

量子傅里葉變換的線路主要由Hadamard門變換與受控相位旋轉(zhuǎn)操作Rk構(gòu)成，其中受控相位旋轉(zhuǎn)操作為

(3)

當(dāng)輸入為n量子比特的狀態(tài)|j1…jn-1jn〉時(shí)，對(duì)應(yīng)的n比特量子傅里葉變換線路圖如圖2所示。

圖2 n比特量子傅里葉變換線路

2.2 基礎(chǔ)量子線路

受ibmqx4芯片結(jié)構(gòu)的限制，量子比特之間不存在互控關(guān)系，因此許多理論量子線路無(wú)法直接應(yīng)用至ibmqx4芯片上，需要對(duì)理論量子線路進(jìn)行修改后才能進(jìn)行實(shí)驗(yàn)實(shí)現(xiàn)。下面給出幾個(gè)量子傅里葉實(shí)驗(yàn)方案中所涉及變換的實(shí)現(xiàn)線路。

2.2.1受控非門

當(dāng)僅使用一個(gè)CNOT門時(shí)，可以使用量子比特1控制量子比特0的非操作，而無(wú)法反向由量子比特0控制量子比特1的非操作。而通過(guò)增加4個(gè)Hadamard變換，可以給出一個(gè)可反向的受控非門操作，使得量子比特0可以控制量子比特1的非操作，具體線路如圖3所示。

圖3 可反向的受控非操作

2.2.2交換門

當(dāng)兩個(gè)量子比特可以相互控制時(shí)，則兩個(gè)量子比特之間的交換操作可以由3個(gè)CNOT來(lái)實(shí)現(xiàn)，而ibmqx4結(jié)構(gòu)中任意兩個(gè)量子比特均無(wú)法相互控制，因此使用3個(gè)CNOT門無(wú)法實(shí)現(xiàn)任意兩個(gè)量子比特的交換操作。結(jié)合圖2中可反向的受控非操作，可以實(shí)現(xiàn)量子比特0與量子比特1之間的交換操作，如圖4所示。

圖4 交換門的量子線路

特別地，若要實(shí)現(xiàn)非直接控制量子比特之間的交換時(shí)，例如量子比特0與量子比特3，需要借助中間量子比特2，利用3個(gè)交換門實(shí)現(xiàn)。

2.2.3受控變換

常見(jiàn)的受控變換是受控非門，也即受控X門，利用HXH=Z與SXS?=Y可以構(gòu)造出受控Z門與受控Y門，而在量子線路設(shè)計(jì)中通常需要在多種其他變換中添加控制比特。下面給出一個(gè)通用模型，當(dāng)需要構(gòu)造一個(gè)受控V門時(shí)，可以利用如圖5所示的線路模型。

圖5 受控V門的量子線路

其中線路A、B、C分別滿足如下條件ABC=I和eiαAZBZC=V。例如構(gòu)造受控H門時(shí)，需要有A=ei3π/8XSHTHS?，B=e-iπ/8SHT?HS?HSH，C=e-iπ/4HSH與eiα=-i。

在量子傅里葉變換的線路中，需要使用多個(gè)不同相位參數(shù)的受控相位變換CRz(α)。構(gòu)造受控相位變換時(shí)，可以利用一個(gè)相位變換與受控非門組合得到。例如構(gòu)造受控π/4相位變換時(shí)，可以直接由π/8相位變換與受控非門構(gòu)造得到，具體如圖6所示。

圖6 受控π/4相位變換量子線路

理論上利用上述線路可以由初始態(tài)|00〉制備得到|++〉，并以第一個(gè)量子比特為控制比特對(duì)第二個(gè)量子比特進(jìn)行受控π/4相位變換，可以得到如下量子態(tài):

(4)

可以看出該輸出量子態(tài)中各疊加分量的概率幅是相同的，因此當(dāng)驗(yàn)證該線路的正確性時(shí)，無(wú)法通過(guò)測(cè)量值的概率來(lái)判斷。需要對(duì)輸出的量子態(tài)進(jìn)行一定相位旋轉(zhuǎn)與變換后，通過(guò)特殊的輸出值來(lái)判斷線路得到的狀態(tài)是否為期望態(tài)，具體的方法見(jiàn)下節(jié)。

2.3 量子比特量子傅里葉變換的線路

由于量子傅里葉變換需要由一個(gè)比特控制多個(gè)比特，通過(guò)分析ibmqx4的結(jié)構(gòu)，可以得知利用量子比特0，1，2，同時(shí)結(jié)合上述受控相位變換與交換門，可以構(gòu)造得到對(duì)應(yīng)的3量子比特量子傅里葉變換的線路如圖7所示。同時(shí)，由于其結(jié)構(gòu)的限制，在ibmqx4結(jié)構(gòu)的量子計(jì)算芯片上能夠有效實(shí)現(xiàn)的量子傅里葉變換的規(guī)模為3比特，若需實(shí)現(xiàn)4比特的量子傅里葉變換，則需要使用可反向的控制非門來(lái)增加控制比特，使得實(shí)現(xiàn)效率明顯下降。

上述線路圖中共按照黑色虛線劃分為五個(gè)部分，第一部分設(shè)置初始量子態(tài)；第二部分為量子傅里葉變換的主要變換部分；第三部分是交換操作；第四部分是相位操作與Hadamard門變換，目的是驗(yàn)證得到量子態(tài)是否為期望值；第五部分是測(cè)量輸出。

3 理論分析與實(shí)驗(yàn)驗(yàn)證

本節(jié)分別給出圖7所示3比特量子傅里葉變換的理論結(jié)果與實(shí)驗(yàn)結(jié)果，并進(jìn)行了對(duì)比。

圖7 3比特量子傅里葉變換的量子線路

首先給利用理論分析結(jié)果如下：

第一部分初始量子態(tài)為|000〉，經(jīng)過(guò)X門后得到量子態(tài)|110〉；

第三部分執(zhí)行交換門操作后得到量子態(tài)為1/2(|0〉+e3iπ/4|1〉)(|0〉+eiπ/2|1〉)|-〉；

第五部分測(cè)量后以概率1得到100。

利用IBM Q量子計(jì)算云服務(wù)所提供的量子計(jì)算模擬器，運(yùn)行上述量子線路后得到結(jié)果如8圖所示。通過(guò)量子模擬器的輸出結(jié)果，可以判斷該量子線路能夠得到量子傅里葉變換的期望輸出值。

圖8 3比特量子傅里葉變換的模擬器輸出結(jié)果

下面在IBM Q5量子計(jì)算芯片“Tenerife”上進(jìn)行實(shí)際運(yùn)行，選取實(shí)現(xiàn)參數(shù)為1 024shots，實(shí)驗(yàn)三次后分別得到運(yùn)行結(jié)果如圖9所示。

圖9 參數(shù)為1 024shots的三次3比特量子傅里葉變換輸出結(jié)果

由于量子計(jì)算芯片的不完美性，量子門存在誤差、環(huán)境中存在各類噪聲等，導(dǎo)致量子計(jì)算芯片的輸出結(jié)果不唯一。上述3比特量子傅里葉變換的實(shí)際輸出結(jié)果如表2所示。

表2 3比特量子傅里葉變換的實(shí)際輸出值及概率幅

經(jīng)過(guò)多次運(yùn)算，可以觀察得到3比特量子傅里葉變換得到期望解的概率為66.2%+1%。當(dāng)選取實(shí)驗(yàn)參數(shù)為8 192 shots時(shí)，進(jìn)行三次實(shí)驗(yàn)可以得到結(jié)果如圖10所示。

經(jīng)過(guò)多次運(yùn)算，可以觀察得到3比特量子傅里葉變換得到期望解的概率為66.2%+3%。增大實(shí)驗(yàn)參數(shù)shot的取值時(shí)，對(duì)3比特量子傅里葉變換的輸出影響不大。

接下來(lái)，將線路圖第一部分的初始化量子態(tài)操作去除，則輸入量子態(tài)為全零，經(jīng)過(guò)傅里葉變換后則輸出量子態(tài)一定為均勻疊加態(tài)，直接經(jīng)過(guò)Hadamard門后一定得到全零態(tài)，具體的量子線路圖如圖11所示。經(jīng)過(guò)實(shí)驗(yàn)驗(yàn)證后得到輸出如圖12所示。

4 結(jié)論

本文簡(jiǎn)單介紹了IBM Q Experience中5量子比特計(jì)算芯片的編程基礎(chǔ)，給出了3比特量子傅里葉變換的實(shí)現(xiàn)方案，通過(guò)理論分析結(jié)果與實(shí)驗(yàn)實(shí)際輸出結(jié)果的對(duì)比，表明所給出實(shí)現(xiàn)方案的正確性。在實(shí)際量子計(jì)算芯片上進(jìn)行運(yùn)算時(shí)，由于量子門誤差存在，導(dǎo)致無(wú)法以確定概率得到正確輸出；量子模擬器能夠以確定概率得到正確輸出，而其計(jì)算能力又受限于經(jīng)典計(jì)算機(jī)，僅能做小規(guī)模驗(yàn)證演示。下一步可在文獻(xiàn)[7]中所提供的4量子比特NMR量子計(jì)算芯片上進(jìn)行計(jì)算，并對(duì)比其計(jì)算效果。

圖10 參數(shù)為8 192shots的三次3比特量子傅里葉變換輸出結(jié)果

圖11 3比特量子傅里葉變換的量子線路

圖12 3比特量子傅里葉變換實(shí)際輸出結(jié)果