量子算法

量子算法是一種專為量子計算機設計的計算程式，它利用了量子力學中的獨特性質來執行任務。這些性質包括量子疊加、量子糾纏和量子干涉等，使得量子算法在某些情況下能夠比傳統經典算法更高效地解決問題。

量子計算機具有天然的並行處理能力，由於量子疊加原理，一個量子系統可以同時處理大量信息，且對於某些特定類型的問題，比如大整數分解或無序資料庫搜尋，量子算法能提供指數級的速度提升。量子計算的並行性是有別於經典計算並行性的。經典的並行計算主要是靠多重硬體同時計算來實現，而量子並行計算是在同一個量子線路中完成的。

量子算法的發展前景非常廣闊，如在新材料與藥物發現方面，量子模擬算法可以精確地模擬分子和材料的行為，從而加速新材料的研發過程以及新藥的開發；在加密與安全方面，基於量子特性的加密技術，如量子密鑰分發（QKD），提供了理論上絕對安全的通信手段；在最佳化問題上，量子最佳化算法可以幫助解決複雜的組合最佳化問題。套用方面，金融機構已經開始探索使用量子算法進行市場趨勢分析、風險評估和投資策略最佳化，量子密鑰分發和其他基於量子的技術正逐漸成為增強信息安全的重要工具。

基本介紹

• 中文名：量子算法
• 外文名：Quantum Algorithm
• 所屬學科：計算機科學、數學
• 相關人物：Shor, David Deutsch, Richard Jozsa等
• 基本單位：量子比特

定義

量子算法是在量子位和量子門上執行的有限序列，指令定義明確，用於解決一個或一類問題。

發展歷史

理論提出及探索階段

1980年：美國阿貢國家實驗室的Paul Benioff發表了一篇論文，提出了量子力學模型的圖靈機，這是量子計算概念的初步探索。

1981年：諾貝爾獎得主理察·費曼（Richard Feynman）在麻省理工學院的演講中提出了量子計算機的概念，指出經典計算機難以有效模擬量子系統，而量子計算機可以。

1985年：英國牛津大學的大衛·德伊奇（David Deutsch）提出了量子圖靈機的概念，並設計了第一個量子算法Deutsch算法。

1992年：Deutsch與劍橋大學的理察·喬薩（Richard Jozsa）合作，擴展了Deutsch算法，形成了Deutsch-Jozsa算法，這是首個展示量子計算優勢的算法。

通用量子算法發展階段

1994年：彼得·肖爾（Peter Shor）提出了Shor算法，這是一個能夠在多項式時間內解決大整數因式分解問題的量子算法，這對密碼學產生了巨大影響。

1996年：Lov Grover提出了Grover算法，這是一種量子搜尋算法，能夠以平方根加速的方式在無序資料庫中搜尋特定元素。

2009年：Aram Harrow、Avinatan Hassidim和Seth Lloyd開發了HHL算法，用於求解線性方程組，相比經典算法有指數級加速效果。

專用量子算法繁榮階段

2009年至2018年間：隨著量子硬體的發展，研究人員開始探索非通用量子計算架構，即專用量子計算機，這些架構專注於解決特定類型的問題。例如，變分量子特徵值求解器（VQE）和量子近似最佳化算法（QAOA）就是在這一時期開發出來的，它們被設計用來解決化學和最佳化問題。

量子AI探索階段

2018年後：量子計算與人工智慧（AI）的結合成為了新的研究熱點。谷歌、IBM等公司開始探索如何利用量子計算來增強機器學習算法，例如通過量子神經網路（QNN）和量子支持向量機（QSVM）等。

基礎概念

量子比特

一個量子比特（quantum bit，簡稱qubit）可由一個二維單位列向量表示。和是兩個特殊的量子比特，稱為可計算基態，用狄拉克符號表示為，。一般的單量子比特用表示，即。因此，且。

由於，所以存在實數、和使得，而對觀測沒有影響，因此可以忽略，即也可表示為。其中，，。可見，所有單量子比特與Bloch球面上的點一一對應，如圖2.1所示。

圖2.1 bloch球面.

量子邏輯門

在量子計算中，通過對量子位狀態進行一系列的酉變換來實現某些邏輯變換功能。因此，在一定時間間隔內實現邏輯變換的量子裝置，稱其為量子邏輯門（量子門）。量子門是在物理上實現量子計算的基礎。單量子比特門可以由矩陣給出，對用作量子門的矩陣，唯一要求是其具有酉性，即，其中是的共軛轉置，是單位矩陣。表2.2給出了常用的單比特量子門的名稱及矩陣表示。

由表2.2通過簡單計算，可知和。應該指出，儘管門被稱為門，但矩陣中出現的確是，這是因為

故將其稱為門。

主要優勢

並行處理能力

量子疊加：量子比特（qubits）不同於經典比特只能處於0或1狀態，它可以同時處於這兩種狀態的任意線性組合。這意味著個量子比特可以表示種可能的狀態，並且所有這些狀態都是同時存在的。例如，一個3量子比特系統可以同時代表8個不同的狀態：。當執行算法時，這相當於同時對個數據點進行操作。

並行計算：由於這種疊加性質，量子計算機可以在一次運算中對大量數據執行相同的操作。如果一個函式需要對每個輸入值進行評估，那么量子計算機能夠利用疊加態來一次性評估該函式對於所有可能輸入的結果，這是量子並行性的體現。

加速特定問題解決

並非所有計算任務都能從量子並行性和加速中獲益，目前只有部分特定類型的問題被證明可以通過量子算法得到有效解決，如下文提到的Shor算法。

量子計算複雜性研究中最顯著的結果之一是。很明顯，，其中BQP（bounded-error quantum polynomial time）是量子計算機在多項式時間內可以解決的一類決策問題。BPP是判定問題的經典複雜類，它可以在經典圖靈機上用多項式時間以有界錯誤機率求解。所以有。如果證明了，意味著量子計算機比經典計算機更強大，也意味著。但是，目前還不清楚是否成立。

著名的量子算法

Deutsch算法

Deutsch算法是第一個量子算法。雖然該算法簡單，但它體現了量子並行性和量子相干性的基本思想，也展現了量子算法的基本過程。

首先介紹Deutsch問題：對於給定的一個布爾函式，通過對的函式值查詢來確定是常值函式（即）還是平衡函式（即）還是平衡函式（即）。

求解Deutsch問題的經典確定性算法必須分別查詢函式值與，才可以計算出，進而確定是平衡函式還是常值函式。也就是說，求解Deutsch問題的經典確定性算法查詢次數為2。之後可以看到，量子算法只需要查詢1次的函式值，就可以確定為平衡函式還是常值函式。

由CNOT門的定義

可知

，

可得

更一般地

設函式，可以通過一個2量子比特的酉變換來查詢，即對於，有可以驗證該變換是酉變換。實現的電路如圖4.1.1所示。

圖4.1.1 2量子比特的Uf門

根據上面的定義有

因而，有

Deutsch算法電路圖如圖4.1.2所示。可以看到，Deutsch算法只需要調用1次門，也就是只需要查詢一次函式，就可以確定是平衡函式還是常值函式。相比於最好的經典算法可以減少一次對函式的查詢，體現了量子算法相比經典確定算法具有查詢次數的優勢。

圖4.1.2 Deutsch算法電路圖

Shor算法

在Shor算法被發現之前，已知的大整數分解方法（如通用數域篩法等）對於非常大的整數來說是非常耗時的。大整數分解問題是許多公鑰加密體系的基礎之一，特別是RSA加密算法的安全性依賴於大整數難以快速分解的事實。因此，如果能夠找到一種高效的方法來解決這個問題，將直接影響到這些加密技術的安全性。

Shor算法的核心就是利用數論中的這樣一個命題：大數的素數分解可歸結為尋找以為模的同餘式的周期，即可將大數N質因子分解轉化為求某個函式的周期問題。其基本思想是：首先，利用量子並行性通過一步計算獲得該函式所有的函式值的疊加態；然後，通過測量這個疊加態得到該函式自變數的某種疊加態；最後，對其進行量子快速傅立葉變換（Quantum Fast Fourier Transformation）。其實，上述過程就是將大數質因子分解轉化為用量子FFT在多項式步驟內完成的求一個函式的周期問題。得到的周期後，按照一定的機率算法，可以推導出N的一個因子。值得指出，該算法屬於機率求解算法，不能保證每次分解都能成功，但是，Shor已經證明該算法成功的機率隨著大數的二進制長度按多項式遞減。因此，只需將上述過程重複的次數置為的多項式值，就可以接近1的機率得到大數的一個因子，而另一因子用大數除以該因子即可得到。大數因子分解屬於典型的NP問題，任何經典算法對該問題都是無能為力的，而Shor算法為套用量子計算機實現大數質因子分解提供了可能。

Grover算法

在計算機科學中，從資料庫眾多的數據里找出所需要的數據，稱為資料庫的搜尋問題。而當資料庫中眾多的數據處於無序狀態時，需要遍歷搜尋的次數隨著資料庫的規模而成比例增加。在經典算法中，只能採取逐個元素驗證的方法遍歷地搜尋下去，因此需要的步驟與被搜尋集合中元素數目成正比，顯然這種方法很耗時。為了加速上述問題的搜尋過程，1996年Grover提出了一種量子搜尋算法，他將問題的搜尋步數從經典算法的縮小到。顯然這種算法起到了對經典算法的二次加速作用，從而顯著地提高了搜尋的效率。

量子相位估計算法

設是酉矩陣，相應的特徵向量為以及對應的特徵值分別為，其中，即

，

而且

相位估計問題可以描述如下：給定酉運算元，且為的特徵向量，即，目標是儘可能精確地估計出，輸出的近似值。

設為作用於個量子比特上的酉變換，是一正整數，表示作用於個量子比特上的酉變換，其定義為

，其中，為比特量子態。

量子相位估計的電路圖如圖4.4所示，其中藉助了量子傅立葉變換QFT模組。

圖4.4 量子相位估計算法

實際套用

求解線性/非線性方程組

求解線性方程組是科學及工程計算中的一個基本問題。經典計算方法通常包括疊代法和直接法。典型的疊代方法有Jacobi法、Gauss-Seidel法、SOR方法及Krylov子空間方法（如CG、GMRES、BiCGStab等）。在直接法中，常用的是部分旋轉的高斯消元法（GEPP）。在量子計算領域，也可以從這兩個方面來介紹求解線性方程組的量子算法。

疊代法：量子疊代算法可以通過逐步逼近來求解線性方程組。可以利用量子計算的特殊性質來加速疊代過程，例如量子梯度下降算法、矩陣線性運算的行列疊代法等。

直接法：量子直接求解算法可以通過一次計算得到線性方程組的精確解。這些算法可以利用量子線路以及量子相位估計等技術來實現，例如HHL算法。

求解特徵值問題

傳統的經典求矩陣特徵值問題有QR方法、Jacobi和Sturm序列方法、冪法和反冪法；複雜度方面，QR方法、Jacobi方法、Sturm方法和反冪法的複雜度為，冪法的複雜度為，其中表示矩陣維數。

近年來經典求矩陣特徵值問題已取得了一些重要的進展。例如針對大規模稀疏矩陣，出現了一系列高效的疊代方法和預處理技術，能夠顯著提高求解速度和準確性。此外，基於GPU等並行計算技術的加速方法也得到了廣泛套用。

與經典算法相比，基於量子電路的量子算法在計算複雜度方面表現出了潛在的優勢。目前關於特徵值的量子解法器主要有兩種：

１）量子相位估計算法（QPE）；

２）量子變分本徵求解器（VQE）。

QPE由Lloyd在1999年提出，其利用受控操作、量子傅立葉逆變換和測量實現對酉運算元特徵值的估計。VQE是在2014年由Peruzzo等提出的，它是一種基於VQA思想計算哈密頓量特徵值的算法。

求解微分方程

微分方程在現代社會的套用非常廣泛。實際上，超級計算機的許多主要套用形式均為大型微分方程系統。

量子計算機可以模擬量子系統，而量子系統是由有限類型的線性微分方程描述的。因此，高維空間的線性微分方程求解問題可藉助量子計算機來解決。相較於傳統計算機的求解方式，量子計算機更有可能對高維微分方程的經典算法產生指數級的加速。

量子機器學習

量子機器學習算法不僅僅是簡單地將原機器學習中複雜度較高的部分替換為量子版本進行最佳化，而是基於量子計算模型和量子信息學理論，重新設計和構建了一系列適用於量子計算機的機器學習算法和模型。

Wiebe等基於HHL算法首次提出量子線性回歸算法。當數據矩陣稀疏且具有很低的條件數時，該算法相對經典算法具有指數加速。

Lloyd等利用多拷貝量子態哈密頓量的模擬，實現了非稀疏矩陣的最大特徵值求解，即完成量子主成分分析。該算法拓展了先前對稀疏矩陣求解問題，同樣使用HHL算法進行特徵提取。

Rebentrost等進一步利用HHL算法和哈密頓量模擬設計了一個量子支持向量機算法。該算法在數據矩陣低秩的條件下能夠在多項式時間內完成對數據的分類，相比經典SVM算法具有指數加速效果。

Duan等提出了一個基於線性判別分析的量子數據降維算法，該算法同樣相對經典算法達到了指數加速效果。然而，目前這類工作只能生成構成低維空間的主成分，並未完整的實現將高維數據集映射到低維空間以獲得相應的低維數據集。

2018年，Rebentrost等利用HHL算法設計了量子Hopfield神經網路，給出了Hopfield網路作為傳染病識別器的套用。

同年，Pierre-Luc等利用HHL算法實現了量子生成對抗網路，其中利用HHL算法實現生成模型的訓練和生成新樣本。

Kerenidis等提出了一種推薦系統的量子算法，該算法比之前的經典算法在矩陣規模上有指數量級加速。

總結

在過去的20年中，量子計算經歷了快速發展，並成為高性能計算領域一個新的發展方向。線上性和非線性方程求解、矩陣運算以及圖相關運算等領域，量子計算取得了一系列重要的研究成果。

已有的研究結果表明：在這些領域中，量子計算可以實現指數加速或多項式加速。