量子計算簡述

文章目錄

• 1、量子概念
• • 1.1、定義
  • 1.2、基本性質
  • • 1.2.1、量子測不準（不确定關系）
    • 1.2.2、量子不可克隆
    • 1.2.3、量子不可區分
    • 1.2.4、量子态疊加(superposition)
    • 1.2.5、量子态糾纏(entanglement)
    • 1.2.6、量子态相幹性(interference)
  • 1.3、量子資訊
  • 1.4、量子門
  • 1.5、量子并行計算原理
• 2、典型量子算法
• • 2.1、Shor算法
  • 2.2、Grove算法
  • 2.3、HHL算法
  • 2.4、量子機器學習與深度學習算法
• 3、量子計算機

1、量子概念

1.1、定義

量子(Quantum)屬于一個微觀的實體概念。如果一個實體量存在最小的不可分割的基本機關[1]，那麼稱這個實體量是可量子化的，并把實體量的基本機關稱為量子。現代實體中，将微觀世界中所有的不可分割的微觀粒子（光子、電子、原子等）或其狀态等實體量統稱為量子。

量子這個數學概念的意思究竟是什麼呢？就是“離散變化的最小單元”。

量子這個概念最早由德國實體學家普朗克在1900年提出的，他假設黑體輻射中的輻射能量是不連續的，隻能取能量基本機關的整數倍，這很好地解釋了黑體輻射的實驗現象。即假設對于一定頻率的電磁輻射，物體隻以“量子”的方式吸收和發射。

量子假設的提出有力地沖擊了牛頓力學為代表的經典實體學，促進實體學進入微觀層面，奠定了現代實體學基礎，進入了全新的領域

經典力學中的機率反映的是資訊的缺乏，可以通過減少這些因素的幹擾來增強預測能力。而量子力學的機率是一種本質的随機性。

1.2、基本性質

1.2.1、量子測不準（不确定關系）

也稱為不确定性原理，即觀察者不可能同時知道一個粒子的位置和它的速度，粒子位置的總是以一定的機率存在某一個不同的地方，而對未知狀态系統的每一次測量都必将改變系統原來的狀态。也就是說，測量後的微粒相比于測量之前，必然會産生變化。

1.2.2、量子不可克隆

量子不可克隆原理，即一個未知的量子态不能被完全地克隆。在量子力學中，不存在這樣一個實體過程：實作對一個未知量子态的精确複制，使得每個複制态與初始量子态完全相同。

1.2.3、量子不可區分

量子不可區分原理，即不可能同時精确測量兩個非正交量子态。事實上，由于非正交量子态具有不可區分性，無論采用任何測量方法，測量結果的都會有錯誤。

1.2.4、量子态疊加(superposition)

量子狀态可以疊加，是以量子資訊也是可以疊加的。這是量子計算中的可以實作并行性的重要基礎，即可以同時輸入和操作個量子比特的疊加态。

1.2.5、量子态糾纏(entanglement)

兩個及以上的量子在特定的(溫度、磁場)環境下可以處于較穩定的量子糾纏狀态，基于這種糾纏，某個粒子的作用将會瞬時地影響另一個粒子。愛因斯坦稱其為: “幽靈般的超距作用”。

在量子力學中，體系的狀态可以用一個函數來表示，稱為“态函數”（是的，你既可以把它了解為一個函數，也可以把它了解為一個矢量，兩者不沖突，怎麼友善怎麼來）。單粒子體系的态函數是一進制函數，多粒子體系的态函數是多元函數。如果這個多元函數可以分離變量，也就是可以寫成多個一進制函數直接的乘積，我們就把它稱為“直積态”。如果它不能分離變量，我們就把它稱為“糾纏态”。

如：F(x, y) = xy + 1，就可以說X和Y是糾纏的

用一個态(|01> + |10>)/√2作例子，我們可以把它記為|β01>。這個态的特點是，你對它測量粒子1的狀态，會以一半的機率發現粒子1處于|0>，粒子2處于|1>，另一半機率發現粒子1處于|1>，粒子2處于|0>。你無法預測單次測量的結果，但你可以确定，粒子1變成什麼，粒子2就同時變成了相反的狀态。

1.2.6、量子态相幹性(interference)

量子力學中微觀粒子間的互相疊加作用能産生類似經典力學中光的幹涉現象。

1.3、量子資訊

量子力學有一條基本原理叫做“疊加原理”：如果兩個狀态是一個體系允許出現的狀态，那麼它們的任意線性疊加也是這個體系允許出現的狀态。

利用微觀粒子狀态表示的資訊稱為量子資訊。量子比特(quantum bit或qubit)是量子資訊的載體，它有兩個可能的狀态，一般記為

|0>

和

|1>

，對應經典資訊裡的0和1。狀态和是二維複向量空間中的機關向量，它們構成了這個向量空間的一組标準正交基。量子比特的狀态是用一個疊加态表示的，

如: | φ \varphi φ>= α \alpha α|0>+ β \beta β|1> ，其中 α 2 + β 2 = 1 \alpha^2+\beta^2=1 α2+β2=1

疊加原理說的是：如果一個體系能夠處于|0>和處于|1>，那麼它也能處于任何一個a|0> + b|1>，這樣的狀态稱為“疊加态”。

而且測量結果為|0>态的機率是 α 2 \alpha^2 α2，而得到|1>态的機率是 β 2 \beta^2 β2。這說明一個量子比特能夠處于既不是|0>又不是|1>的狀态上，而是處于|0>和|1>的一個線性組合的所謂中間狀态之上。經典資訊可表示為011000，而量子資訊可表示為| φ 1 \varphi_1 φ1​>| φ 2 \varphi_2 φ2​>| φ 3 \varphi_3 φ3​>

• 經典比特是“開關”，隻有開和關兩個狀态（0和1），而量子比特是“旋鈕”，就像收音機上調頻的旋鈕那樣，有無窮多個狀态（所有的a|0> + b|1>）。顯然，旋鈕的資訊量比開關大得多。

一個經典的二進制存儲器隻能存一個數：要麼存 0，要麼存 1。但一個二進制量子存儲器卻可以同時存儲0和1這兩個數。兩個經典二進制存儲器隻能存儲以下四個數的一個數: 00，01，10 或 11。倘若使用兩個二進制量子存儲器，則以上四個數可以同時被存儲下來。按此規律，推廣到N個二進制存儲器的情況，理論上，N個量子存儲器與N個經典存儲器分别能夠存儲個 2 N 2^N 2N數和1個數。由此可見，量子存儲器的存儲能力是呈指數增長的，它比經典存儲器具有更強大的存儲資料的能力，尤其是當 N 很大時(如 N=250 )，量子存儲器能夠存儲的資料量比宇宙中所有原子的數目還要多。

1.4、量子門

在量子計算，特别是量子線路的計算模型裡面，一個量子門 (Quantum gate，或量子邏輯門)是一個基本的，操作一個小數量量子比特的量子線路 。它是量子線路的基礎，就像傳統邏輯門跟一般數字線路之間的關系。

與多數傳統邏輯門不同，量子邏輯門是可逆的。 然而，傳統的計算可以隻使用可逆的門表示· 舉例來說，可逆的Toffoli門 可以實做所有的布爾函數。 這個門有一個直接等同的量子門，也是以代表量子線路可以模拟所有傳統線路的操作。

量子邏輯門使用酉矩陣表示。 就像常見的邏輯門一般是針對一個或兩個比特進行操作，常見的量子門也是針對一個或兩個量子比特進行操作。 這也代表這一些量子門可以以2 × 2或者4 × 4的酉矩陣表示。

量子門常使用矩陣表示，操作K個量子比特的門可以用2k x 2k 的酉矩陣表示。 一個門輸入跟輸出的量子比特數量必須要相等。 量子門的操作可以用代表量子門的矩陣與代表量子比特狀态的向量作相乘來表示。

例如：

阿達馬門

阿達馬門是隻對一個一個量子比特進行操作的門。 這個門将基本狀态

|0>

變成 ∣ 0 > + ∣ 1 > 2 \frac{|0>+|1>}{\sqrt{2}} 2

​∣0>+∣1>​ ，并且将

|1>

變成 ∣ 0 > − ∣ 1 > 2 \frac{|0>-|1>}{\sqrt{2}} 2

​∣0>−∣1>​ 。這個門可以以阿達馬矩陣表示：

H = 1 2 ( a b c d ) H=\frac{1}{\sqrt{2}}\bigl(\begin{matrix} a & b \\ c & d \end{matrix} \bigr) H=2

​1​(ac​bd​)

因為矩陣的每一列正交，是以H 是一個酉矩陣。

1.5、量子并行計算原理

由于量子比特可以同時處于兩種狀态的疊加态，是以量子門操縱它時，實際上同時操縱了其中的兩種狀态。

是以，若一個量子計算機同時操縱N個量子比特，那麼它實際上可以同時操縱 2 N 2^N 2N個狀态，其中每個狀态都是一個N位的經典比特。這就是量子計算機的并行計算能力。

2、典型量子算法

2.1、Shor算法

大整數素因子分解難題指的是：将兩個大的質因子

p1、p2

相乘容易，

N=p1*p2

，但是将它們相乘的結果分解為兩個素因子十分困難。經典算法求解該問題時計算複雜度會随着問題的規模指數增長，目前最有效的傳統求解方法複雜度為：

O(exp[ n 1 / 3 ( l o g n ) 2 / 3 n^{1/3}(logn)^{2/3} n1/3(logn)2/3])

衆所周知，RSA公鑰密碼正是基于這樣的一個數學難題。

1994年，應用數學家Shor 提出了一個實用的量子算法，通常稱為Shor算法。它的出現使得大整數分解問題在量子計算機中在多項式時間内解決成為可能，它計算複雜度僅為

O( n 2 n^2 n2(logn)(loglogn))。

顯然，相比經典算法，Shor算法相當于進行了指數加速。算法主要思想是将整數質因子分解問題轉化為求解量子傅裡葉變換的周期，将多個輸入制備為量子态疊加，進行并行處理和操作，進而到到了量子加速的目的。

在實際應用中， 2001年，IBM公司的研究小組首次在開發的核磁共振（Nuclear magnetic resonance，NMR）量子計算機中使用Shor算法，成功将15分解成3×5，這一成果引起業界廣泛的關注和讨論。理論上，一旦更多量子比特的量子計算機研究成功，對于1000位大整數，采用 Shor算法可以在不到1秒内即可進行素因子分解，而采用傳統計算機分解需要年（而宇宙的年齡為年）。由此可見在量子計算機面前，現有的公開密鑰 RSA體系不再安全。

2.2、Grove算法

搜尋問題指的是從個未分類的元素中尋找出某個特定的元素。對于該問題，經典算法逐個地進行搜尋，直到找到滿足的元素為止，平均需要

N/2

,時間複雜度為

O(N)

1996年，計算機科學家Grover在提出一個量子搜尋算法，通常稱為Grover算法。采用該量子算法進行搜尋僅需 ( π 4 ) N \left(\frac{\pi}{4}\right)\sqrt{N} (4π​)N

​次,複雜度為O( N \sqrt{N} N

​)。相比傳統算法，它進行了二次加速，再次展現了量子計算并行帶來的高效優勢。舉一個直覺的例子，若要從有着100萬個号碼的電話本中找出某個人的号碼。經典方法是逐個地進行搜尋，平均需要搜尋50萬次才能找到正确的号碼。而采用Grover的量子算法，它會首先将100萬個号碼制備為量子疊加态。然後在制備的量子疊加态上通過反複執行量子操作的疊代，每一次疊代，它将放大正确的态（尋找的電話号碼）的機率，同時減少非正确的态的機率。當進行 ( π 4 ) 1 0 6 ≈ 785 \left(\frac{\pi}{4}\right)\sqrt{10^6}\approx785 (4π​)106

​≈785次後，正确态的機率接近于1，此時去測量，可以正确态的結果，進而得到查找的電話号碼。

由于很多問題都可以看作一個搜尋問題，如尋找對稱密碼(DES/AES等)的正确密鑰，搜尋方程的最佳參數等，是以Grover算法的用途十分廣泛。

2.3、HHL算法

求解線性方程是一個基本的數學的問題，在工程等領域有重要的廣泛。對于方程，其中A是N*N矩陣，是N維向量，求解N維未知向量。若采用 Gauss 消元法可以在 O ( N 3 ) O(N^3) O(N3)時間内求解。

2008年，Harrow、Hassidim A和Lloyd S三位學者提出了一種可以在 O ( l o g 2 ( N ) ) O(log_2(N)) O(log2​(N))時間内求解線性方程組的量子算法[14]，通常稱為HHL算法。同樣地，需要将多個輸入制備為量子态疊加，進而進行量子并行操作。

由于機器學習算法中的某些求參過程同樣可看作是該類問題，是以學者們已經将 HHL 算法應用到機器學習領域，比如 K-means 聚類,支援向量機，資料拟合等算法中，進而達到加速的目的。

2.4、量子機器學習與深度學習算法

在量子算法中，有一類算法是應用在機器學習或深度學習領域。由于近年來人工智能和機器學習/深度學習的研究熱潮，同樣帶動了量子機器學習/深度學習的發展和研究。

衆所周知，傳統的機器學習/深度學習算法仍然面臨計算瓶頸的挑戰。然而，若充分利用量子計算的并行性，則可以進一步優化傳統機器學習算法的效率，突破計算瓶頸，加速人工智能程序。量子機器學習的研究可追溯到1995年，Kak最先提出量子神經計算的概念。相繼學者們提出了量子聚類、量子深度學習和量子向量機等算法。2015年，潘建偉教授團隊在小型光量子計算機上，首次實作了量子機器學習算法。

從經典—量子的二進制概念出發可以将機器學習問題按照資料和算法類型的不同分為4類，如表1所示。

表1 機器學習分類

簡稱	算法類型	資料類型	應用執行個體
C-C	經典	經典	傳統機器學習
C-Q	經典	量子	量子優化控制
Q-C	量子	經典	量子支援向量機等
Q-Q	量子	量子	量子回報控制

量子機器學習的訓練資料必須以某種可以為量子計算機識别的格式載入（即制備量子疊加态），經過量子機器學習算法處理以後形成輸出，而此時的輸出結果是量子疊加态的，需要經過測量得到最終結果，該流程如圖1（量子機器學習的基本流程）所示。

表2概述了目前文獻中見到的一些典型量子機器學習算法，及其所需資源和性能改善特征。

表2 主要量子機器學習算法

• 如前所述，量子機器學習算法相比經典算法，有以下顯著優勢：

(1) 量子加速。由于量子态的可疊加性，相比傳統計算機，量子算法可以在不增加硬體的基礎上實作并行計算，在此基礎上利用Shor算法、HHL算法和Grover搜尋等算法，可實作相對于完成同樣功能的經典算法的二次甚至指數加速。

(2) 節省記憶體空間。将經典資料通過制備量子态疊加編碼為量子資料，并利用量子并行性進行存儲，可實作指數級地節省存儲硬體需求。

3、量子計算機

所謂量子計算機，它是指具有量子計算能力的實體裝置。為什麼要出現這種裝置呢？主要有兩個原因：(1) 外部原因：摩爾定律失效。根據摩爾定律，內建電路上可容納的半導體數目每隔24個月增加一倍，性能也相應增加一倍。然而，一方面随着晶片元件內建度的提高會導緻機關體積内散熱增加，由于材料散熱速度有限，就會出現計算速度上限，産生“熱耗效應”。另一方面元件尺寸的不斷縮小，在納米甚至埃尺度下經典世界的實體規律不再适用，出現“尺寸效應”。(2) 内部原因：量子計算機的強并行性。這是量子計算機相比傳統計算機的顯著優勢，量子計算機和量子算法互相結合，可以将計算效率進行二倍加速甚至指數加速，例如傳統計算機計算需要1年的任務，使用量子計算機可能需要不足1秒的時間。

不同于傳統計算機，量子計算機用來存儲資料的對象是量子比特；不同于傳統計算機，量子計算機用使用量子邏輯門進行資訊操作，如對單個量子操作的邏輯門：泡利-X門，泡利-Y門，泡利-Z門和Hadamard門等；對兩個量子操作的雙量子邏輯門：受控非門CNOT，受控互換門SWAP等等。

這些量子的邏輯門的操作可以看做一種矩陣變換，即乘以幺正矩陣（可看做正交矩陣從實數域推廣到複數域）的過程。圖10以Hadamard門為例，表述了對量子态

|0>

的形象操作過程。

由圖可知，Hadamard門可以将一個量子态變成兩個量子态的疊加狀态。形象地說，貓生的狀态通過Hadamard門轉換成生和死的疊加态（機率為狀态幅度的平方，機率各為50%）。這種性質十分有用，是實作并行計算基礎，可以将N個輸入資料轉換成一個疊加的量子态，一次量子計算操作，相當于進行了N個資料操作，即實作了N次的并行，後文提到的量子算法正是利用這些量子邏輯門的變換特性。其他量子邏輯門的幺正矩陣有所不同，但操作也類似，這裡不做贅述。

此外，量子計算機用使用的量子邏輯門是可逆的；而傳統計算機的邏輯門一般是不可逆的。前者操作後産生的能量耗散，而後者進行幺正矩陣變換可實作可逆計算，它幾乎不會産生額外的熱量，進而解決能耗上的問題。與傳統的計算機相同的是，量子計算機的理論模型仍然是圖靈機。不同的是，量子計算目前并沒有作業系統，代替用量子算法進行控制，這決定了目前的量子計算機并不是通用的計算機，而屬于某種量子算法的專用計算機。量子計算機和傳統計算機的比較結果如表3所示。

表3 量子計算機VS 傳統計算機

量子計算機的基本原理如圖11所示。它主要的過程如下：

(1) 選擇合适的量子算法，将待解決問題程式設計為适應量子計算的問題。

(2) 将輸入的經典資料制備為量子疊加态。

(3) 在量子計算機中，通過量子算法的操作步驟，将輸入的量子态進行多次幺正操作，最終得到量子末态。

(4) 對量子末态進行特殊的測量，得到經典的輸出結果。

迄今為止，科學家用來嘗試實作量子計算機的硬體系統有許多種，包括液态核磁共振、離子阱、線性光學、超導、半導體量子點等。其中，超導和半導體量子點由于可集乘度高，容錯性好等優點，目前被認為是實作量子計算機的兩種可能方案[1]。最近，IBM宣布的研制50比特和谷歌研制的72比特量子計算機都是基于低溫超導系統的方案。

$ umask  
      0022##表示擁有者（u）不用去掉權限，其他兩個去掉w（寫）