基于IBM量子計算云服務的量子傅里葉變換實現(xiàn)*

崔競一，劉翼鵬，郭建勝

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

0 引言

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

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

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

1 相關知識

本節(jié)對IBM量子計算云服務編程的相關知識與量子傅里葉變換的基礎知識進行介紹。

1.1 IBM量子計算云服務簡介

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

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

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

圖1 ibmqx4的結構示意圖

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

1.2 量子傅里葉變換

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

(1)

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

(2)

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

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

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

量子傅里葉變換的線路主要由Hadamard門變換與受控相位旋轉操作Rk構成，其中受控相位旋轉操作為

(3)

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

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

2.2 基礎量子線路

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

2.2.1受控非門

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

圖3 可反向的受控非操作

2.2.2交換門

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

圖4 交換門的量子線路

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

2.2.3受控變換

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

圖5 受控V門的量子線路

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

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

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

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

(4)

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

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

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

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

3 理論分析與實驗驗證

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

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

首先給利用理論分析結果如下：

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

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

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

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

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

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

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

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

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

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

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

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

4 結論

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

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

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

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