Deutsch與Deutsch—Jozsa算法簡(jiǎn)介

黃蘊(yùn)琦+葉澤坤+陳韋江

摘要：在經(jīng)典計(jì)算機(jī)里，隨著器件尺寸越來(lái)越接近物理極限，摩爾定律也即將失效。而量子計(jì)算機(jī)則為提升計(jì)算機(jī)的計(jì)算能力提供了一個(gè)全新的角度，量子計(jì)算特有的并行性使得經(jīng)典計(jì)算無(wú)法望其項(xiàng)背。該文首先介紹了量子計(jì)算的起源和基本概念；然后介紹第一個(gè)量子算法，Deutsch算法的提出和發(fā)展；最后介紹Deutsch-Jozsa算法，它解決了n比特的Deutsch問(wèn)題。盡管該兩個(gè)算法所解決的問(wèn)題不具有直接的實(shí)用價(jià)值，但Deutsch算法作為第一個(gè)量子算法，奠定了量子算法的基本思想，而Deutsch-Jozsa算法則首次實(shí)現(xiàn)了對(duì)經(jīng)典算法的指數(shù)級(jí)加速。該兩個(gè)算法為后來(lái)的量子算法的設(shè)計(jì)提供了思路和源泉。

關(guān)鍵詞：量子計(jì)算；量子算法；量子并行性；Deutsch算法；Deutsch-Jozsa算法

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）35-0149-04

Introduction to Deutsch and Deutsch-Jozsa Algorithms

HUANG Yun-qi， YE Ze-kun， CHEN Wei-jiang

（Sun Yat-sen University， Guangzhou 510006， China）

Abstract： In classical computers， Moore's Law is about to expire as device sizes become closer to physical limits. Quantum computers， on the other hand， provide a completely new perspective for enhancing the computational power of computers. The unique parallelism of quantum computation makes classical computation far behind. This paper first introduces the origin and basic concepts of quantum computation， then introduces the origin and the development of Deutsch algorithm， the first quantum algorithm. At last it introduces Deutsch-Jozsa algorithm， which solves n-bits Deutsch problem. Although the problems solved by these two algorithms do not have direct practical value， Deutsch algorithm， as the first quantum algorithm， laid the basic idea of ??quantum algorithm. And the Deutsch-Jozsa algorithm， for the first time， exponentially accelerates classical algorithms. These two algorithms provide ideas and sources for the later design of quantum algorithms.

Key words： quantum computation； quantum algorithm； quantum parallelism； Deutsch algorithm； Deutsch-Jozsa algorithm

1 背景

20世紀(jì)初，德國(guó)物理學(xué)家普朗克在研究黑體輻射問(wèn)題時(shí)提出了一個(gè)假設(shè)：能量在發(fā)射和吸收的時(shí)候，不是連續(xù)不斷，而是一份一份來(lái)進(jìn)行的。這個(gè)假設(shè)，標(biāo)志著量子力學(xué)的開(kāi)端。此后，愛(ài)因斯坦、薛定諤、波恩、德布羅意、狄拉克等許多天才物理學(xué)家投入到這個(gè)領(lǐng)域的研究當(dāng)中，量子力學(xué)理論迎來(lái)飛速發(fā)展。

目前經(jīng)典計(jì)算機(jī)的運(yùn)算速度已經(jīng)達(dá)到了非常高的水平，但集成電路技術(shù)也在逼近極限，很難再通過(guò)器件的改良來(lái)提升計(jì)算機(jī)的計(jì)算能力。與此同時(shí)，人們對(duì)運(yùn)算速度的需求沒(méi)有停止，仍然有許多問(wèn)題不能在有效的時(shí)間得到解決。

20世紀(jì)80年代初期，一些物理學(xué)家證明一臺(tái)計(jì)算機(jī)原則上可以以純粹的量子力學(xué)的方式運(yùn)行。量子計(jì)算以疊加性、干涉性、糾纏性、不可克隆、狀態(tài)變化等量子力學(xué)原理為基礎(chǔ)和約束，建立全新的計(jì)算體系。在此體系下固有的并行性，顯示出了其在計(jì)算速度上的巨大潛力。在這個(gè)體系下，許多學(xué)者提出了一些理論和方法來(lái)處理一些問(wèn)題，比在經(jīng)典體系下的處理更高效。如1994年，Peter Shor提出在量子計(jì)算機(jī)下，大數(shù)的素因子分解問(wèn)題可以在多項(xiàng)式時(shí)間內(nèi)解決[1]。本文中我們將介紹第一個(gè)量子算法，Deutsch算法及其改進(jìn)以及該算法的一般情況Deutsch-Jozsa算法。

2 量子計(jì)算基本概念

2.1 量子比特

在經(jīng)典計(jì)算機(jī)里，我們利用比特作為最小單位進(jìn)行存儲(chǔ)。一個(gè)比特只能是兩種狀態(tài)，要么為0，要么為1。而對(duì)應(yīng)的在量子計(jì)算機(jī)里我們用量子比特來(lái)進(jìn)行存儲(chǔ)。量子比特則是用和來(lái)表示對(duì)應(yīng)的0，1狀態(tài)，記，。與經(jīng)典比特不同的是，量子比特可以是狀態(tài)的線性組合[2]，又被稱為疊加態(tài)，如下所示：

其中和是復(fù)數(shù)，且滿足條件。

同樣地，對(duì)于多量子比特來(lái)說(shuō)，當(dāng)時(shí)，可如下表示：

其中，是復(fù)數(shù)，且滿足條件。==， ==，和類似。（是一個(gè)矩陣，是一個(gè)維矩陣，則，是一個(gè)維矩陣）

2.2 測(cè)量

對(duì)于單量子比特，可定義觀測(cè)量集合{}，它們滿足，其中是的共軛轉(zhuǎn)置矩陣（取0或1）當(dāng)我們對(duì)進(jìn)行測(cè)量時(shí)[3]，有的概率測(cè)量結(jié)果為0，此時(shí)量子比特變?yōu)?有的概率測(cè)量結(jié)果為1，此時(shí)量子比特變?yōu)椤Ｌ貏e地，當(dāng)==時(shí)，以的概率測(cè)量得到0，以的概率測(cè)量得到1。

而對(duì)于2位的量子比特，可定義觀測(cè)量集合{}，它們滿足。當(dāng)我們對(duì)進(jìn)行測(cè)量時(shí)，有的概率測(cè)量結(jié)果為，此時(shí)量子比特變?yōu)椤＃ㄆ渲?0，1，2或3）

2.3 量子門

在量子世界里，我們的運(yùn)算操作是由量子邏輯門完成的。量子邏輯門（簡(jiǎn)稱量子門）可以由酉矩陣及其組合來(lái)進(jìn)行表示。每個(gè)酉矩陣都可以定義一個(gè)有效的量子門。根據(jù)輸入的比特?cái)?shù)的不同我們可以分為單量子比特門和多量子比特門。常用的單量子比特門有Hadamard門，Pauli門等。下面舉一個(gè)作用Hadamard門變換的例子：

2.4 量子算法

量子算法即是利用量子的疊加性、糾纏性和狀態(tài)變化等特點(diǎn)來(lái)進(jìn)行設(shè)計(jì)的算法。量子算法通常由上述所說(shuō)的一系列量子邏輯門進(jìn)行順序操作來(lái)實(shí)現(xiàn)。在1985年，Deutsch首次提出了一種量子算法用于解決Deutsch問(wèn)題[4]，在1992年Deutsch和Jozsa一起提出Deutsch-Jozsa算法[5]，解決了n比特的Deutsch問(wèn)題，對(duì)經(jīng)典算法進(jìn)行了指數(shù)級(jí)速度的改進(jìn)。本文的剩余部分將用于介紹Deutsch算法和Deutsch-Jozsa算法的誕生及其演化改進(jìn)過(guò)程。

3 Deutsch算法

3.1 問(wèn)題描述和經(jīng)典算法

考慮一個(gè)黑盒子，我們稱為oracle。它可以計(jì)算一個(gè)比特的布爾函數(shù)。每做一次計(jì)算，我們就稱為是對(duì)oracle的一次查詢。對(duì)于這個(gè)函數(shù)，存在以下四種可能（表1）：

表1

[ 0 0 0 1 1 1 0 1 0 1 ]

我們稱和為常數(shù)函數(shù)，和為平衡函數(shù)。Deutsch問(wèn)題可如下表述：對(duì)于這樣一個(gè)函數(shù)，如何通過(guò)對(duì)oracle的查詢，確定它是常數(shù)函數(shù)還是平衡函數(shù)？

在經(jīng)典算法[6]里，我們使用經(jīng)典比特來(lái)進(jìn)行計(jì)算。為了確定單比特函數(shù)的類型，我們至少要對(duì)oracle進(jìn)行兩次的查詢。通過(guò)計(jì)算和的值，我們不僅可以判斷出函數(shù)的類型，甚至可以得到的具體形式。

3.2 Deutsch算法的提出

1985年，Deutsch首次提出了量子圖靈機(jī)模型[4]，并且設(shè)計(jì)了第一個(gè)量子算法—Deutsch算法用于解決上述所說(shuō)的Deutsch問(wèn)題。該算法將以1/2的概率對(duì)oracle進(jìn)行一次查詢就能得到函數(shù)的類型。這是人類歷史上首個(gè)利用量子的特性所設(shè)計(jì)出來(lái)的專門針對(duì)量子計(jì)算機(jī)的算法，開(kāi)創(chuàng)了量子算法的先河，為后面的Shor算法，Grover算法等的量子算法的設(shè)計(jì)提供了思路。因此，作為一個(gè)開(kāi)創(chuàng)性的算法，Deutsch算法的設(shè)計(jì)思路意義遠(yuǎn)大于它所解決問(wèn)題能力的意義。

假設(shè)有這樣一個(gè)量子計(jì)算機(jī)Q，對(duì)每個(gè)函數(shù)，和整數(shù)a，b，在Q上存在一個(gè)程序使得函數(shù)對(duì)寄存器a的內(nèi)容進(jìn)行計(jì)算，并放置到寄存器b里，即

現(xiàn)考慮量子程序

它將使得Q終止于狀態(tài)

.

特別地，當(dāng)N=2時(shí)，寄存器2，3的狀態(tài)為

.

現(xiàn)對(duì)其進(jìn)行一次測(cè)量，其觀測(cè)量集合為{}，其中

-

-

+

+

若，則與正交，測(cè)量結(jié)果只可能是；若，則與正交，則測(cè)量結(jié)果只可能是。因此若結(jié)果測(cè)得是，則可以斷定；若結(jié)果測(cè)得是，則可以斷定；如果結(jié)果測(cè)得是，則無(wú)法得出結(jié)論。所以Deutsch算法可以以1/2的概率，只執(zhí)行1次oracle就能得到的結(jié)果；而經(jīng)典算法至少要計(jì)算兩次。

3.3 Deutsch算法的改進(jìn)

由上文可知，原始的Deutsch算法是有1/2的概率會(huì)測(cè)得。在1998年，R. Cleve， A. Ekert， C. Macchiavello和M. Mosca對(duì)Deutsch算法進(jìn)行改進(jìn)[7]，將它從一個(gè)概率性算法變成一個(gè)確定性算法，這對(duì)于Deutsch算法來(lái)說(shuō)有了質(zhì)的飛躍。目前，我們所說(shuō)的Deutsch算法一般指改進(jìn)后的算法[8]，它能在調(diào)用oracle一次后，得出確定的結(jié)果。

具體的算法流程如圖1的量子線路所示：

圖1

假設(shè)一個(gè)量子oracle，的作用為：

其中⊕為異或操作。

給定初始狀態(tài)，作用Hadamard變換后得

對(duì)上述量子態(tài)作用后得：

由異或操作性質(zhì)可知：

。

因此，上式可寫(xiě)成：

由于第二個(gè)寄存器的結(jié)果與我們的最終結(jié)果無(wú)關(guān)，下面只考慮第一個(gè)寄存器上的量子態(tài)：

將其整理得：

對(duì)上述量子態(tài)再次作用Hadamard變換后可得：

現(xiàn)在，我們對(duì)測(cè)量，若，則函數(shù)為常數(shù)函數(shù)；若，則函數(shù)為平衡函數(shù)。

4 Deutsch-Jozsa算法

4.1 問(wèn)題描述和經(jīng)典算法

現(xiàn)在將單比特的Deutsch問(wèn)題推廣至比特，對(duì)于函數(shù)，我們這里只考慮常數(shù)函數(shù)和平衡函數(shù)。若對(duì)于所有的，有或，則為常數(shù)函數(shù)；若，則為平衡函數(shù)。對(duì)于這樣的函數(shù)，我們?cè)谧顗那闆r下需要對(duì)oracle進(jìn)行次查詢才能得出結(jié)論。若要對(duì)這個(gè)方法進(jìn)行改進(jìn)，一個(gè)很有效的方法就是利用量子并行性來(lái)進(jìn)行計(jì)算。

4.2 Deutsch-Jozsa算法的提出

1992年，Deutsch和Jozsa對(duì)原始的Deutsch算法進(jìn)行了拓展[5]，給出了Deutsch問(wèn)題在比特上的量子算法。給出一個(gè)函數(shù)，其中。在只使用2次oracle的情況下，就能判斷命題A，B的對(duì)錯(cuò)，其中命題A為：不是常數(shù)函數(shù)。命題B為：（0），（1），…，中0的個(gè)數(shù)不為N（即不是平衡函數(shù)）。

當(dāng)N=時(shí)，為了得到確定性的結(jié)果，經(jīng)典算法需要次查詢，而Deutsch-Jozsa算法僅需要對(duì)oracle進(jìn)行兩次查詢，在查詢次數(shù)上有了指數(shù)級(jí)的提升。

定義一個(gè)酉算子，使得

算子可以被量子計(jì)算機(jī)在有限步之內(nèi)執(zhí)行。

定義一個(gè)量子狀態(tài)

可從空白狀態(tài)開(kāi)始，在步內(nèi)被制備。

給出一個(gè)oracle ，使得

⊕

現(xiàn)有如下演化過(guò)程

內(nèi)積的絕對(duì)值為

||=||

如果是平衡函數(shù)，即命題B是錯(cuò)的，則內(nèi)積的絕對(duì)值為0；如果是常數(shù)函數(shù)，即命題A是錯(cuò)的，則內(nèi)積的絕對(duì)值為1。因此，在使用投影算子進(jìn)行測(cè)量后，若測(cè)量結(jié)果是0，說(shuō)明不平行，內(nèi)積的絕對(duì)值不為1，則命題A是正確的；若測(cè)量的結(jié)果是1，不正交，內(nèi)積的絕對(duì)值不為0，則命題B是正確的。

所以若測(cè)量結(jié)果為0 ，則不是常數(shù)函數(shù)；若測(cè)量結(jié)果是1，則不是平衡函數(shù)。特別地，若只能是常數(shù)函數(shù)和平衡函數(shù)中的一種時(shí)，Deutsch-Jozsa算法可以確定的類型。

4.3 Deutsch-Jozsa算法的改進(jìn)

對(duì)于原始的Deutsch-Jozsa算法，98年R. Cleve等作者的論文[7]也做出了改進(jìn)。原始算法中，我們需要對(duì)oracle進(jìn)行兩次的查詢來(lái)進(jìn)行判斷命題A，B的對(duì)錯(cuò)，而改進(jìn)后我們只需要對(duì)oracle進(jìn)行一次查詢便可以得到函數(shù)的類型[9]。

具體的算法流程如圖2量子線路所示。

給定初始狀態(tài)，作用Hadamard變換后可得：

對(duì)上述量子態(tài)作用后，得到：

因最后一位量子態(tài)的結(jié)果與我們的最終結(jié)果無(wú)關(guān)，因此只考慮前面部分，對(duì)該部分作用Hadamard變換后我們得到

其中表示和的取模2的內(nèi)積，即

對(duì)于該輸出態(tài)，我們對(duì)個(gè)量子比特進(jìn)行測(cè)量。如果函數(shù)是常數(shù)函數(shù)，那么我們測(cè)量得到的概率為1，如果是平衡函數(shù)，那么測(cè)到這個(gè)態(tài)的概率為0。這樣，只需要對(duì)oracle進(jìn)行一次查詢，我們就可以確定函數(shù)是常數(shù)的還是平衡的，這與經(jīng)典算法里需要次的查詢有了指數(shù)級(jí)速度的提升。

由于Deutsch-Jozsa算法所解決的問(wèn)題并不像Shor算法，Grover算法等那樣具有實(shí)際應(yīng)用價(jià)值，它并不常被人們提及。但是它作為第一個(gè)體現(xiàn)量子算法優(yōu)越性的算法，是非常具有里程碑式的意義的。

5 結(jié)束語(yǔ)

作為首個(gè)量子算法和首個(gè)體現(xiàn)指數(shù)級(jí)加速的量子算法，Deutsch算法和Deutsch-Jozsa算法說(shuō)明了比起經(jīng)典計(jì)算機(jī)，量子計(jì)算機(jī)能夠更快速更有效地解決一些特定的問(wèn)題，顯示出了量子計(jì)算機(jī)的巨大潛力，并且鼓舞著人們?nèi)ふ腋嗟牧孔铀惴ǎ@推動(dòng)了量子計(jì)算以及整個(gè)理論計(jì)算機(jī)學(xué)科的發(fā)展。

參考文獻(xiàn)：

[1] Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM review， 1999， 41（2）：303-332.

[2] Nielsen M A， Chuang I L. Quantum Computation and Quantum Information[M]. Cambridge： Cambridge University Press， 2000： 13-15.

[3] Nielsen M A， Chuang I L. Quantum Computation and Quantum Information[M]. Cambridge： Cambridge University Press， 2000： 84-85.

[4] Deutsch D. Quantum theory， the Church-Turing principle and the universal quantum computer[C]. Proceedings of the Royal Society of London A： Mathematical， Physical and Engineering Sciences. The Royal Society， 1985， 400（1818）：97-117.

[5] Deutsch D， Jozsa R. Rapid solution of problems by quantum computation[C]. Proceedings of the Royal Society of London A： Mathematical， Physical and Engineering Sciences. The Royal Society， 1992， 439（1907）：553-558.

[6] 吳盛俊， 周錦東， 張永德. 量子算法簡(jiǎn)介[J]. 大學(xué)物理， 1999， 18（12）：1-5.

[7] Cleve R， Ekert A， Macchiavello C， et al. Quantum algorithms revisited[C]. Proceedings of the Royal Society of London A： Mathematical， Physical and Engineering Sciences. The Royal Society， 1998， 454（1969）：339-354.

[8] Nielsen M A， Chuang I L. Quantum Computation and Quantum Information[M]. Cambridge：Cambridge University Press， 2000： 32-36.

[9] Strini G， Benenti G， Casati G. Principles of Quantum Computation and Information： Basic Tools And Special Topics[M]. NJ， USA：World Scientific Publishing Co.， 2007： 108-110.