基于Cirq的Deutsch-Jozsa電路綜合算法

戴 娟,李志強(qiáng),楊冬晗

(揚(yáng)州大學(xué)信息工程學(xué)院,江蘇 揚(yáng)州 225100)

0 引言

Deutsch-Jozsa算法作為第一個(gè)量子算法,首次實(shí)現(xiàn)了對(duì)經(jīng)典算法的指數(shù)級(jí)加速,解決了n個(gè)量子比特的Deutsch問題,奠定了量子算法的基本思想[1]。一般的經(jīng)典算法處理問題需要做2n-1+1次,而Deutsch-Jozsa算法只需要一步就可以完成。與經(jīng)典算法相比,量子算法融入了量子力學(xué)的很多特征,比如量子的相干性、量子疊加性、量子并行性、糾纏性等等。這些物理性質(zhì)很大程度上提高了計(jì)算的效率,使該算法具有更快的運(yùn)算潛能[2]。

此前,很多學(xué)者研究了Deutsch-Jozsa算法的電路實(shí)現(xiàn)及其應(yīng)用。Cheng等[3]研究了如何模擬Deutsch-Jozsa電路,Xie等[4]研究了Deutsch-Jozsa的復(fù)雜性,Cheng等[5]實(shí)現(xiàn)了利用四能級(jí)超導(dǎo)量子干涉儀實(shí)現(xiàn)Deutsch算法,Zhang等[6]研究了量子Fourier變換在實(shí)現(xiàn)Deutsch-Jozsa算法中的應(yīng)用。但是,還未見針對(duì)Deutsch-Jozsa算法的電路綜合算法的詳細(xì)報(bào)道。研究Oracle電路的構(gòu)建、Deutsch-Jozsa電路的綜合對(duì)解決Deutsch問題至關(guān)重要。本文在利用Cirq源碼研究1比特Deutsch電路的基礎(chǔ)上,研究構(gòu)建n比特Oracle電路,從而綜合Deutsch-Jozsa算法的電路,進(jìn)而對(duì)其進(jìn)行模擬。

1 Deutsch-Jozsa算法

Deutsch問題給定一個(gè)承諾,函數(shù)f(x)要么是常數(shù)函數(shù)要么是平衡函數(shù)。構(gòu)造Deutsch-Jozsa電路,通過測(cè)量可以判斷這個(gè)函數(shù)是常數(shù)函數(shù)還是平衡函數(shù)[7]。

圖1 Deutsch-Jozsa電路圖Fig.1 Schematic diagram of Deutsch-Jozsa circuit

輸入狀態(tài)為 |φ0〉=|0〉?n|1〉。Deutsch-Jozsa 算法的實(shí)現(xiàn)步驟如下:

第1步把n+1個(gè)Hadamard門分別作用在每一個(gè)量子比特上,得到

第2步通過Uf,對(duì)這n+1個(gè)量子比特操作,得到

第3步將n個(gè)Hadamard門分別作用在前n個(gè)量子比特上,得到

由此可見,當(dāng)f(x)是常數(shù)時(shí),一定可測(cè)得|0〉?n;當(dāng)f(x)是平衡函數(shù)時(shí),一定不可測(cè)得|0〉?n。反之,同樣可以根據(jù)對(duì)前n個(gè)量子比特的測(cè)量去判斷f(x)是常數(shù)還是平衡函數(shù)[9]。

2 Deutsch-Jozsa電路綜合算法

2.1 Deutsch-Jozsa電路綜合算法

Deutsch-Jozsa算法的Oracle電路如圖2所示,在Oracle電路中,第一根量子比特線的輸出與輸入是一樣的;第二根量子比特線的輸出值與f(x)的值有關(guān)。當(dāng)f(x)=0,y⊕f(x)=y,即經(jīng)過黑盒子第二根量子線的輸出不變;當(dāng)f(x)=1,y⊕f(x)=∧y,即經(jīng)過Oracle電路后第二根量子線翻轉(zhuǎn)[10]。

圖2 Oracle電路圖Fig.2 Schematic diagram of Oracle circuit

當(dāng)n=2時(shí),其控制輔助位y翻轉(zhuǎn)的f(x)電路如圖3所示。根據(jù)生成的f(x)集合將圖3中的電路進(jìn)行級(jí)聯(lián),即可生成Oracle電路。其部分Python代碼如下:

圖3 n=2時(shí)的 f(x)電路圖Fig.3 f(x)circuit for n=2

以n=4為例,隨機(jī)生成平衡函數(shù)f(x)=＜0,1,0,1,1,1,0,0,0,0,1,1,1,1,0,0＞,構(gòu)造Deutsch-Jozsa電路如圖4所示,其中,t0表示構(gòu)建電路消耗的時(shí)間,t1表示模擬電路消耗的時(shí)間,g1表示電路中的總門數(shù),c1表示總層數(shù)。同時(shí)根據(jù)其測(cè)量結(jié)果驗(yàn)證f(x)是一個(gè)平衡函數(shù),也驗(yàn)證了綜合算法的正確性[11,12]。

2.2 Deutsch-Jozsa電路綜合算法的優(yōu)化

2.2.1 簡(jiǎn)化X門

在綜合出來的電路中,兩個(gè)連續(xù)的X門相當(dāng)于一個(gè)恒等電路,即可去掉[13]。

部分Python代碼如下:

仍然以n=4為例,對(duì)圖4中的電路進(jìn)行優(yōu)化的結(jié)果如圖5,其中,t2表示優(yōu)化后模擬電路消耗的時(shí)間,g2表示優(yōu)化后的電路中的總門數(shù),c2表示其電路的總層數(shù)。

圖4 n=4時(shí)的Deutsch-Jozsa電路圖Fig.4 Deutsch-Jozsa circuit for n=4

圖5 n=4時(shí)的電路優(yōu)化Fig.5 Optimization circuit for n=4

2.2.2 利用X門構(gòu)造等效電路

當(dāng)f(x)是一個(gè)全是1的常數(shù)函數(shù)時(shí),構(gòu)造的電路相當(dāng)于全0的常數(shù)函數(shù)加一個(gè)X門。以n=3為例,f(x)=＜1,1,1,1,1,1,1,1,＞是一個(gè)常數(shù)函數(shù),簡(jiǎn)化X門后的電路如圖6所示。

圖6 n=3時(shí)的Deutsch-Jozsa電路圖Fig.6 Deutsch-Jozsa circuit for n=3

Oracle電路使得y⊕f(x)=∧y,其效果等效于添加一個(gè)X門,如圖7所示。

圖7 n=3時(shí)的等效電路Fig.7 Equivalent circuit for n=3

3 實(shí)驗(yàn)結(jié)果及優(yōu)化情況分析

表1給出了Deutsch-Jozsa電路綜合算法在n個(gè)量子比特情況下平衡函數(shù)的實(shí)驗(yàn)結(jié)果。其中,t0是利用綜合算法構(gòu)造Deutsch電路消耗的時(shí)間,t1、t2分別是優(yōu)化前后模擬電路時(shí)消耗的時(shí)間,層數(shù)c的含義如圖8所示,一個(gè)虛線框表示一層,該電路共5層。

圖8 一個(gè)簡(jiǎn)單電路Fig.8 A simple circuit

從表1實(shí)驗(yàn)數(shù)據(jù)可以看出,隨著量子位數(shù)的增加,構(gòu)造電路所需要的時(shí)間以及電路模擬時(shí)間也在增加。當(dāng)n=1、2時(shí),由于量子門數(shù)比較少,其電路優(yōu)化前后的門數(shù)以及層數(shù)沒有顯著的變化。當(dāng)n≥3時(shí),電路優(yōu)化以后,其門數(shù)的應(yīng)用、電路的層數(shù)以及模擬電路需要的時(shí)間成倍數(shù)級(jí)地減少。n的值越大,優(yōu)化的效果越明顯。

表1 實(shí)驗(yàn)結(jié)果Table 1 Experimental results

該程序使用ThinkPad E431在Python3.7的環(huán)境中運(yùn)行。當(dāng)n=17時(shí),該環(huán)境已不能正常地構(gòu)造出電路,因此實(shí)驗(yàn)結(jié)果對(duì)比只展示出n≤16的部分。

4 結(jié)論

首次提出利用Google的Cirq框架綜合電路算法,具有重要的研究意義。該綜合算法可以根據(jù)f(x)集合自動(dòng)構(gòu)建Deutsch電路并對(duì)其進(jìn)行模擬,優(yōu)化后的電路相比優(yōu)化前不僅減少了總門數(shù)和總層數(shù),電路模擬的速度有了成倍的提高。Deutsch-Jozsa算法中構(gòu)建Oracle電路的思路為后續(xù)研究Grover量子搜索算法、Shor算法等奠定了基礎(chǔ)。