量子Fourier變換在實(shí)現(xiàn)Deutsch-Jozsa算法中的應(yīng)用

張洪濤, 熊紅梅, 凃玲英, 舒軍

(1. 湖北工業(yè)大學(xué) 納米電子技術(shù)與微系統(tǒng)實(shí)驗(yàn)室, 湖北 武漢 430068;

2. 湖北工業(yè)大學(xué) 電氣與電子工程學(xué)院, 湖北 武漢 430068)

?

量子Fourier變換在實(shí)現(xiàn)Deutsch-Jozsa算法中的應(yīng)用

張洪濤1,2, 熊紅梅1,2, 凃玲英1,2, 舒軍2

(1. 湖北工業(yè)大學(xué) 納米電子技術(shù)與微系統(tǒng)實(shí)驗(yàn)室, 湖北 武漢 430068;

2. 湖北工業(yè)大學(xué) 電氣與電子工程學(xué)院, 湖北 武漢 430068)

摘要：提出利用量子Fourier變換解決Deutsch-Jozsa算法問題的觀點(diǎn).結(jié)合量子Fourier變換和Deutsch-Jozsa算法的量子電路，找到一種利用量子Fourier變換解決Deutsch-Jozsa算法新的量子電路，并考察該量子電路中各個(gè)線路的量子狀態(tài)，結(jié)合算法對(duì)該量子線路的狀態(tài)進(jìn)行研究.結(jié)果表明：利用量子Fourier變換解決Deutsch問題，能夠有效地提高運(yùn)算速度，節(jié)省運(yùn)算時(shí)間.

關(guān)鍵詞：Deutsch-Jozsa算法； 量子傅里葉變換； 量子電路； 量子算法

近年來，隨著量子計(jì)算機(jī)研究的發(fā)展，人們不斷地探索新的實(shí)現(xiàn)量子計(jì)算機(jī)的方案和新的量子算法.Deutsch-Jozsa算法是由Deutsch等[1]在1992年提出的第一個(gè)量子計(jì)算算法,并由Cleve等[2]在1998年提出改進(jìn).1994年，Shor[3]構(gòu)造了大數(shù)質(zhì)因子分解的量子算法，Shor算法可以在多項(xiàng)式時(shí)間內(nèi)，求解大整數(shù)分解和有限域上離散對(duì)數(shù)問題.1996年，Grover給出了一種量子搜索算法[4]，Grover量子搜索算法可以平方根地加速無序數(shù)據(jù)庫的搜索.自Shor算法和Grover量子搜索算法提出以后，有研究者將量子理論原理與智能計(jì)算相結(jié)合提出了量子智能計(jì)算[5].有關(guān)Deutsch-Jozsa算法的研究也一直在繼續(xù)向前，并取得相當(dāng)不錯(cuò)的成績(jī).羅軍等[6]在核磁共振量子計(jì)算機(jī)上實(shí)驗(yàn)實(shí)現(xiàn)了7位Deutsch-Jozsa算法;Zheng[7]利用腔QED實(shí)現(xiàn)了Deutsch-Jozsa算法;Dasgupta等[8]在原子系統(tǒng)中實(shí)現(xiàn)了Deutsch-Jozsa算法.量子傅里葉變換[9]作為一種基本量子工具，它在Shor的大數(shù)質(zhì)因子分解算法已經(jīng)得到了有效的應(yīng)用,而Deutsch-Jozsa算法提出后,卻鮮有人將其與量子傅里葉變換結(jié)合.因此，本文從Deutsch-Jozsa算法原理出發(fā)，把量子Fourier變換應(yīng)用于Deutsch-Jozsa算法中.

1Deutsch-Jozsa算法

1.1Deutsch命題

函數(shù)f(x)∈{0,1}，要么f(x)對(duì)所有的x是常數(shù)，即f(x)為常數(shù)；要么f(x)是平衡函數(shù)，即對(duì)x的所有取值，函數(shù)取1的概率為1/2，取0的概率也為1/2.A,B兩人進(jìn)行數(shù)據(jù)傳送，A從0到2n-1中選擇一個(gè)數(shù)x，并發(fā)送給B，B利用f(x)對(duì)數(shù)x進(jìn)行計(jì)算，得到結(jié)果后告訴A計(jì)算結(jié)果，A必須用最快的時(shí)間，確定B用的是常數(shù)還是平衡函數(shù)[6].

1.2Deutsch-Jozsa算法的量子線路和算法流程

圖1　實(shí)現(xiàn)一般Deutsch-Jozsa算法的量子線路Fig.1　Quantum circuit of the general Deutsch-Jozsa algorithm

|x,y⊕f(x)〉.

Deutsch-Jozsa算法計(jì)算過程有以下5個(gè)步驟.

步驟1狀態(tài)初始化，|0〉?n|1〉.

步驟5測(cè)量最終輸出z，→z.

2量子Fourier變換

2.1量子Fourier變換的定義

量子Fourier變換[11]定義:在一組標(biāo)準(zhǔn)正交基|0〉,…,|N-1〉上的一個(gè)線性算子,其在基態(tài)上的作用，表示為

(1)

對(duì)任意狀態(tài)的作用，可表示為

(2)

(3)

2.2量子Fourier變換的量子線路和算法流程

接著，對(duì)第二量子比特執(zhí)行類似過程,產(chǎn)生狀態(tài)為

對(duì)每個(gè)量子比特繼續(xù)這樣的操作，導(dǎo)出最終狀態(tài)

經(jīng)過交換運(yùn)算，量子比特狀態(tài)為

3結(jié)合量子Fourier變換的Deutsch-Jozsa算法

3.1算法的實(shí)現(xiàn)

在Deutsch-Jozsa算法的經(jīng)典量子線路(圖1)中，過多地使用了Hadamard變換,使計(jì)算比較復(fù)雜.量子Fourier變換的有效電路,如圖2所示.圖2中，對(duì)輸入狀態(tài)的每一位進(jìn)行變換，得到輸入狀態(tài)最終的量子Fourier變換.將這兩種量子線路結(jié)合，利用量子Fourier變換代替Hadamard變換，實(shí)現(xiàn)的方法，如圖3所示.

圖2　量子Fourier變換的有效電路　　　　　圖3　利用量子Fourier變換解決Deutsch問題的有效電路　Fig.2　Efficient circuit of quantum Fig.3　Efficient circuit of Deutsch problem 　　Fourier transform by quantum Fourier transform

3.2量子線路的分析

根據(jù)有效電路分析電路狀態(tài)，初始狀態(tài)為A選擇的數(shù)|x〉.

B得到A發(fā)送的數(shù)|x〉后，對(duì)其使用幺正變換Uf:|x,y〉→|x,y⊕f(x)〉，可以得到|φ2〉，即

(4)

由式(4)可知：B的函數(shù)計(jì)算結(jié)果保存在量子比特的幅度中.A得到B的計(jì)算結(jié)果|φ2〉后，利用量子并行性對(duì)狀態(tài)|φ21〉=(-1)f(x)|x〉進(jìn)行量子Fourier變換.將狀態(tài)|x〉寫成二進(jìn)制形式x=x12n-1+x22n-2+…+xn20.圖3中，|φ2,1〉的幅值省略沒有寫出,即

(5)

由量子Fourier變換的定義式(2)，有

(6)

對(duì)|φ2,2〉右邊部分進(jìn)行交換運(yùn)算，可以得到

(7)

最終，可以得到

(8)

由式(1),(3),(20)可以得到

(9)

即得到φ2,1的量子Fourier變換為

(10)

由式(10)可知：如果f(x)是常數(shù)函數(shù)，φ2，1進(jìn)行量子Fourier變換后的φ2，4幅值為正數(shù)或負(fù)數(shù)；如果f(x)是平衡函數(shù)，對(duì)φ2，4的正負(fù)幅度貢獻(xiàn)抵消，幅度為0.歸納起來，若最終測(cè)量結(jié)果是0，則函數(shù)是平衡函數(shù)；否則，函數(shù)是常數(shù)函數(shù).

3.3算法的分析和比較

在圖3的量子線路中，A直接從0到2n-1中選擇的數(shù)x發(fā)送給B，B利用幺正變換Uf:|x,y〉→

|x,y⊕f(x)〉和量子并行性計(jì)算f(x)，此處的y由B提供.A得到B計(jì)算的結(jié)果后，利用量子并行性對(duì)前n位量子比特進(jìn)行量子Fourier變換，再通過適當(dāng)?shù)臏y(cè)量，確定f(x)是平衡函數(shù)還是常數(shù)函數(shù).

圖4　兩種算法的計(jì)算時(shí)間對(duì)比圖Fig.4　Comparison of two kinds of algorithm in computation time

對(duì)比圖1和圖3可知：在Deutsch-Jozsa算法中，減少對(duì)Hadamard變換的使用，改用量子Fourier變換也一樣可以快速地判斷出f(x)是平衡函數(shù)還是常數(shù)函數(shù)，而且比使用Hadamard變換更簡(jiǎn)單、直接、快速.兩種Deutsch-Jozsa算法的計(jì)算時(shí)間對(duì)比，如圖4所示.圖4中：t為時(shí)間；B為量子比特.由圖4可知：同一個(gè)數(shù)x分別采用的兩種Deutsch-Jozsa算法，利用量子傅里葉變換后的Deutsch-Jozsa算法比Deutsch-Jozsa算法耗時(shí)短，能更快地得到判斷結(jié)果.

4結(jié)束語

文中介紹了Deutsch算法、量子線路算法和量子Fourier變換.在此基礎(chǔ)上，推導(dǎo)并驗(yàn)證Deutsch-Jozsa算法可結(jié)合量子傅里葉變換進(jìn)行快速計(jì)算，為解決Deutsch-Jozsa算法提供了新思路，這對(duì)“相對(duì)黑盒”指數(shù)加速的量子算法[12]的研究提供了新的方案，也為后面進(jìn)行量子算法和量子計(jì)算機(jī)[13]的研究起著重要的作用.

參考文獻(xiàn)：

[1]DEUTSCH D,JOZSA R.Rapid solution of problems by quantum computation[J].Proceedings:Mathematical and Physical Sciences,1992,439(1907):553-558.

[2]CLEVE R,EKERT A,MACCHIAVELLO C,et al.Quantum algorithms revisited[J].Proceedings of the Royal Society A Mathematical Physical and Enginneering Sciences,1997,454(1969):339-354.

[3]SHOR P W.Algorithms for quantum computation: Discrete logarithm factoring[C]∥Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science.Los Alamitos:IEEE Press,1994:181-182.

[4]GROVER L.A fast quantum mechanical algorithm for database search[C]∥Proceedings of the 28th Annual ACM Symposium on the Theory of Computing.New York:ACM,1996:212-219.

[5]王蘊(yùn),黃德才,俞攸紅.量子計(jì)算及量子算法研究進(jìn)展[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2011,20(6):228-231,237.

[6]魏達(dá)秀,楊曉冬,羅軍,等.七量子位Deutsch-Jozsa量子算法的核磁共振實(shí)驗(yàn)實(shí)現(xiàn)[J].原子核物理評(píng)論,2002,19(2):278-280.

[7]ZHENG Shibiao.Scheme for implementing the Deutsch-Jozsa algorithm in cavity QED[J].Physical Review A,2004,70(3):034301(1-3).

[8]DASGUPTA S,BISWAS A,AGARWAL G S.Implementing Deutsch-Jozsa algorithm using light shifts and atomic ensembles [J].Physical Review A,2005,71(1):012333(1-8).

[9]NIELSON M A,CHUANG I L.Quantum computation and quantum information[M].Cambridge:Cambridge University Press,2000:32-35,217-219.

[10]BALLHYSA E.A generalization of Deutch-Jozsa algorithm[M].Germany:LAMBERT Academic Publishing,2010:15-20.

[11]付向群,鮑皖蘇,王帥.ZN上離散對(duì)數(shù)量子計(jì)算算法[J].計(jì)算機(jī)學(xué)報(bào),2014,37(5):1058-1062.

[12]龍桂魯.量子計(jì)算算法介紹[J].物理,2010,39(12):803-809.

[13]張毅,盧凱,高穎慧.量子算法與量子衍生算法[J].計(jì)算機(jī)學(xué)報(bào),2013,36(9):1835-1842.

(責(zé)任編輯： 黃曉楠 英文審校： 吳逢鐵)

Application of the Quantum Fourier Transform in Deutsch-Jozsa Algorithm

ZHANG Hongtao1,2, XIONG Hongmei1,2,TU Lingying1,2, SHU Jun2

(1. Nanoelectron technology and microsystem Laboratory, Hubei University of Technology, Wuhan 430068, China;2. School of Electrical and Electronic Engineering, Hubei University of Technology, Wuhan 430068, China)

Abstract：A new method to solve Deutsch-Jozsa algorithm by using quantum Fourier transform was presented. Combine the quantum circuits of quantum Fourier transform and Deutsch-Jozsa algorithm, then a new quantum circuit of solving Deutsch-Jozsa algorithm used quantum Fourier transform was found. And the quantum circuit processes were observed step by step, and states of the circuit was analyzed. The results showed that solving Deutstch problem by quantum Fourier transform can improve the operation speed and save the operation time.

Keywords：Deutsch-Jozsa algorithm; quantum Fourier transform; quantum circuit; quantum algorithms

中圖分類號(hào)：TP 306

文獻(xiàn)標(biāo)志碼：A

基金項(xiàng)目：湖北省武漢市科技局“十城千輛新動(dòng)力汽車計(jì)劃”(2013011801010600)

通信作者：張洪濤(1963-)，男，教授，博士，主要從事數(shù)字信號(hào)處理和數(shù)字圖像處理、嵌入式系統(tǒng)、納米器件集成和納米半導(dǎo)體技術(shù)的研究.E-mail:zhanght@mail.hbut.edu.cn.

收稿日期：2015-10-14

doi:10.11830/ISSN.1000-5013.2016.02.0155

文章編號(hào)：1000-5013(2016)02-0155-05