崔競一，劉翼鵬，郭建勝

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

0 引言

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

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

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

1 相關(guān)知識

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

1.1 IBM量子計算云服務(wù)簡介

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

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

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

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

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

1.2 量子傅里葉變換

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

(1)

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

(2)

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

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

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

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

(3)

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

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

2.2 基礎(chǔ)量子線路

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

2.2.1受控非門

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

圖3 可反向的受控非操作

2.2.2交換門

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

圖4 交換門的量子線路

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

2.2.3受控變換

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

圖5 受控V門的量子線路

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

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

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

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

(4)

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

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

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

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

3 理論分析與實驗驗證

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

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

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

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

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

第五部分測量后以概率1得到100。

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

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

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

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