Deutsch與Deutsch—Jozsa算法簡介

黃蘊琦+葉澤坤+陳韋江

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

關鍵詞：量子計算；量子算法；量子并行性；Deutsch算法；Deutsch-Jozsa算法

中圖分類號：TP301.6 文獻標識碼：A 文章編號：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世紀初，德國物理學家普朗克在研究黑體輻射問題時提出了一個假設：能量在發射和吸收的時候，不是連續不斷，而是一份一份來進行的。這個假設，標志著量子力學的開端。此后，愛因斯坦、薛定諤、波恩、德布羅意、狄拉克等許多天才物理學家投入到這個領域的研究當中，量子力學理論迎來飛速發展。

目前經典計算機的運算速度已經達到了非常高的水平，但集成電路技術也在逼近極限，很難再通過器件的改良來提升計算機的計算能力。與此同時，人們對運算速度的需求沒有停止，仍然有許多問題不能在有效的時間得到解決。

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

2 量子計算基本概念

2.1 量子比特

在經典計算機里，我們利用比特作為最小單位進行存儲。一個比特只能是兩種狀態，要么為0，要么為1。而對應的在量子計算機里我們用量子比特來進行存儲。量子比特則是用和來表示對應的0，1狀態，記，。與經典比特不同的是，量子比特可以是狀態的線性組合[2]，又被稱為疊加態，如下所示：

其中和是復數，且滿足條件。

同樣地，對于多量子比特來說，當時，可如下表示：

其中，是復數，且滿足條件。==， ==，和類似。（是一個矩陣，是一個維矩陣，則，是一個維矩陣）

2.2 測量

對于單量子比特，可定義觀測量集合{}，它們滿足，其中是的共軛轉置矩陣（取0或1）當我們對進行測量時[3]，有的概率測量結果為0，此時量子比特變為 有的概率測量結果為1，此時量子比特變為。特別地，當==時，以的概率測量得到0，以的概率測量得到1。

而對于2位的量子比特，可定義觀測量集合{}，它們滿足。當我們對進行測量時，有的概率測量結果為，此時量子比特變為。（其中=0，1，2或3）

2.3 量子門

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

2.4 量子算法

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

3 Deutsch算法

3.1 問題描述和經典算法

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

表1

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

我們稱和為常數函數，和為平衡函數。Deutsch問題可如下表述：對于這樣一個函數，如何通過對oracle的查詢，確定它是常數函數還是平衡函數？

在經典算法[6]里，我們使用經典比特來進行計算。為了確定單比特函數的類型，我們至少要對oracle進行兩次的查詢。通過計算和的值，我們不僅可以判斷出函數的類型，甚至可以得到的具體形式。

3.2 Deutsch算法的提出

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

假設有這樣一個量子計算機Q，對每個函數，和整數a，b，在Q上存在一個程序使得函數對寄存器a的內容進行計算，并放置到寄存器b里，即

現考慮量子程序

它將使得Q終止于狀態

.

特別地，當N=2時，寄存器2，3的狀態為

.

現對其進行一次測量，其觀測量集合為{}，其中

-

-

+

+

若，則與正交，測量結果只可能是；若，則與正交，則測量結果只可能是。因此若結果測得是，則可以斷定；若結果測得是，則可以斷定；如果結果測得是，則無法得出結論。所以Deutsch算法可以以1/2的概率，只執行1次oracle就能得到的結果；而經典算法至少要計算兩次。

3.3 Deutsch算法的改進

由上文可知，原始的Deutsch算法是有1/2的概率會測得。在1998年，R. Cleve， A. Ekert， C. Macchiavello和M. Mosca對Deutsch算法進行改進[7]，將它從一個概率性算法變成一個確定性算法，這對于Deutsch算法來說有了質的飛躍。目前，我們所說的Deutsch算法一般指改進后的算法[8]，它能在調用oracle一次后，得出確定的結果。

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

圖1

假設一個量子oracle，的作用為：

其中⊕為異或操作。

給定初始狀態，作用Hadamard變換后得

對上述量子態作用后得：

由異或操作性質可知：

。

因此，上式可寫成：

由于第二個寄存器的結果與我們的最終結果無關，下面只考慮第一個寄存器上的量子態：

將其整理得：

對上述量子態再次作用Hadamard變換后可得：

現在，我們對測量，若，則函數為常數函數；若，則函數為平衡函數。

4 Deutsch-Jozsa算法

4.1 問題描述和經典算法

現在將單比特的Deutsch問題推廣至比特，對于函數，我們這里只考慮常數函數和平衡函數。若對于所有的，有或，則為常數函數；若，則為平衡函數。對于這樣的函數，我們在最壞情況下需要對oracle進行次查詢才能得出結論。若要對這個方法進行改進，一個很有效的方法就是利用量子并行性來進行計算。

4.2 Deutsch-Jozsa算法的提出

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

當N=時，為了得到確定性的結果，經典算法需要次查詢，而Deutsch-Jozsa算法僅需要對oracle進行兩次查詢，在查詢次數上有了指數級的提升。

定義一個酉算子，使得

算子可以被量子計算機在有限步之內執行。

定義一個量子狀態

可從空白狀態開始，在步內被制備。

給出一個oracle ，使得

⊕

現有如下演化過程

內積的絕對值為

||=||

如果是平衡函數，即命題B是錯的，則內積的絕對值為0；如果是常數函數，即命題A是錯的，則內積的絕對值為1。因此，在使用投影算子進行測量后，若測量結果是0，說明不平行，內積的絕對值不為1，則命題A是正確的；若測量的結果是1，不正交，內積的絕對值不為0，則命題B是正確的。

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

4.3 Deutsch-Jozsa算法的改進

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

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

給定初始狀態，作用Hadamard變換后可得：

對上述量子態作用后，得到：

因最后一位量子態的結果與我們的最終結果無關，因此只考慮前面部分，對該部分作用Hadamard變換后我們得到

其中表示和的取模2的內積，即

對于該輸出態，我們對個量子比特進行測量。如果函數是常數函數，那么我們測量得到的概率為1，如果是平衡函數，那么測到這個態的概率為0。這樣，只需要對oracle進行一次查詢，我們就可以確定函數是常數的還是平衡的，這與經典算法里需要次的查詢有了指數級速度的提升。

由于Deutsch-Jozsa算法所解決的問題并不像Shor算法，Grover算法等那樣具有實際應用價值，它并不常被人們提及。但是它作為第一個體現量子算法優越性的算法，是非常具有里程碑式的意義的。

5 結束語

作為首個量子算法和首個體現指數級加速的量子算法，Deutsch算法和Deutsch-Jozsa算法說明了比起經典計算機，量子計算機能夠更快速更有效地解決一些特定的問題，顯示出了量子計算機的巨大潛力，并且鼓舞著人們去尋找更多的量子算法，這推動了量子計算以及整個理論計算機學科的發展。

參考文獻：

[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] 吳盛俊， 周錦東， 張永德. 量子算法簡介[J]. 大學物理， 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.