量子Fourier變換在實現Deutsch-Jozsa算法中的應用

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

(1. 湖北工業大學 納米電子技術與微系統實驗室, 湖北 武漢 430068;

2. 湖北工業大學 電氣與電子工程學院, 湖北 武漢 430068)

?

量子Fourier變換在實現Deutsch-Jozsa算法中的應用

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

(1. 湖北工業大學 納米電子技術與微系統實驗室, 湖北 武漢 430068;

2. 湖北工業大學 電氣與電子工程學院, 湖北 武漢 430068)

摘要：提出利用量子Fourier變換解決Deutsch-Jozsa算法問題的觀點.結合量子Fourier變換和Deutsch-Jozsa算法的量子電路，找到一種利用量子Fourier變換解決Deutsch-Jozsa算法新的量子電路，并考察該量子電路中各個線路的量子狀態，結合算法對該量子線路的狀態進行研究.結果表明：利用量子Fourier變換解決Deutsch問題，能夠有效地提高運算速度，節省運算時間.

關鍵詞：Deutsch-Jozsa算法； 量子傅里葉變換； 量子電路； 量子算法

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

1Deutsch-Jozsa算法

1.1Deutsch命題

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

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

圖1　實現一般Deutsch-Jozsa算法的量子線路Fig.1　Quantum circuit of the general Deutsch-Jozsa algorithm

|x,y⊕f(x)〉.

Deutsch-Jozsa算法計算過程有以下5個步驟.

步驟1狀態初始化，|0〉?n|1〉.

步驟5測量最終輸出z，→z.

2量子Fourier變換

2.1量子Fourier變換的定義

量子Fourier變換[11]定義:在一組標準正交基|0〉,…,|N-1〉上的一個線性算子,其在基態上的作用，表示為

(1)

對任意狀態的作用，可表示為

(2)

(3)

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

接著，對第二量子比特執行類似過程,產生狀態為

對每個量子比特繼續這樣的操作，導出最終狀態

經過交換運算，量子比特狀態為

3結合量子Fourier變換的Deutsch-Jozsa算法

3.1算法的實現

在Deutsch-Jozsa算法的經典量子線路(圖1)中，過多地使用了Hadamard變換,使計算比較復雜.量子Fourier變換的有效電路,如圖2所示.圖2中，對輸入狀態的每一位進行變換，得到輸入狀態最終的量子Fourier變換.將這兩種量子線路結合，利用量子Fourier變換代替Hadamard變換，實現的方法，如圖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量子線路的分析

根據有效電路分析電路狀態，初始狀態為A選擇的數|x〉.

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

(4)

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

(5)

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

(6)

對|φ2,2〉右邊部分進行交換運算，可以得到

(7)

最終，可以得到

(8)

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

(9)

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

(10)

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

3.3算法的分析和比較

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

|x,y⊕f(x)〉和量子并行性計算f(x)，此處的y由B提供.A得到B計算的結果后，利用量子并行性對前n位量子比特進行量子Fourier變換，再通過適當的測量，確定f(x)是平衡函數還是常數函數.

圖4　兩種算法的計算時間對比圖Fig.4　Comparison of two kinds of algorithm in computation time

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

4結束語

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

參考文獻：

[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]王蘊,黃德才,俞攸紅.量子計算及量子算法研究進展[J].計算機系統應用,2011,20(6):228-231,237.

[6]魏達秀,楊曉冬,羅軍,等.七量子位Deutsch-Jozsa量子算法的核磁共振實驗實現[J].原子核物理評論,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上離散對數量子計算算法[J].計算機學報,2014,37(5):1058-1062.

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

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

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

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

中圖分類號：TP 306

文獻標志碼：A

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

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

收稿日期：2015-10-14

doi:10.11830/ISSN.1000-5013.2016.02.0155

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