因?yàn)榱孔佑?jì)算的并行性,? 搜索問題,? 比如說數(shù)據(jù)庫搜索, 最短路徑問題,?加密問題, 圖形著色問題等,? 都被視為可以做到量子加速.

然而在實(shí)際上,? 設(shè)計(jì)一個(gè)可以解決問題的量子算法是困難的.??比如說數(shù)據(jù)庫搜索問題里,? 常用電子線路儲(chǔ)存數(shù)據(jù),??當(dāng)量子線路對數(shù)據(jù)庫歷遍時(shí),? 實(shí)際上也是等于用電子計(jì)算機(jī)歷遍了一次數(shù)據(jù)庫.? 當(dāng)然解決辦法就是使用量子位儲(chǔ)存數(shù)據(jù),? n個(gè)量子位可以最多儲(chǔ)存 2^n 個(gè)數(shù)據(jù) [實(shí)際上使用相位可以理論上儲(chǔ)存無窮個(gè)數(shù)據(jù)].

如此可見達(dá)到量子加速的搜索算法需要滿足幾點(diǎn):? 搜索黑盒允許量子操作,? 并且量子黑盒里的復(fù)雜度小于或差不多等于電子黑盒的復(fù)雜度,? 電子計(jì)算不存在更快速的算法.? 滿足以上幾點(diǎn)才可以說量子算法可能達(dá)到加速效果.? 但不止如此,? 下面通過一個(gè)簡單的圖形著色問題來了解一下最著名的量子搜索算法 -- Grover算法.

注:? 以下算法全部是python+nyasQuantumCalculate,? 關(guān)于庫可以見結(jié)語

圖形著色問題

給出一個(gè)已知的圖(Graph),? 也就是已知的頂點(diǎn)(Vertex)和連接頂點(diǎn)的邊(Edge),? 對每個(gè)頂點(diǎn)打上標(biāo)簽 [也就是著色],? 尋找一個(gè)可能著色使得每條邊上的頂點(diǎn)都不是相同顏色.

由問題描述可以知道,? 只有不存在自環(huán)的無向圖才是圖形著色問題的討論范圍.? 并且常用索引表示頂點(diǎn),? 列表表示邊.? 比如:? 以下表示了一個(gè)圖:

并且簡單推導(dǎo)可以知道這個(gè)圖至少需要4種顏色來著色,? 使用2bits可以對4種顏色編碼,? 并且把全部頂點(diǎn)顏色編碼為一個(gè)列表,? 則下面是一個(gè)可用的著色方案:

設(shè)計(jì)算法

量子計(jì)算可用看作可逆邏輯計(jì)算的拓展,? 而可逆邏輯計(jì)算則通過X, CNOT和CCNOT還原傳統(tǒng)電子計(jì)算邏輯.? ?加法器示例

首先需要解決的問題是如何判斷顏色相等.? 不難知道這個(gè)方法需要輸入兩個(gè)寄存器表示兩個(gè)顏色,? 和一個(gè)標(biāo)記位用來獲取結(jié)果.? 如果兩個(gè)寄存器狀態(tài)相同則翻轉(zhuǎn)標(biāo)記位的狀態(tài).??XOR門是一個(gè)很好的判斷兩bits是否相同的門,? 而可控過程是非常好的多位AND門,? 細(xì)節(jié)可以參考代碼備注.? 正所謂自己動(dòng)手才是學(xué)編程的正確姿勢,? 下面代碼可以自己試著驗(yàn)證運(yùn)行一下.

有了檢驗(yàn)一條邊的頂點(diǎn)顏色是否相等的方法后,? 對整個(gè)圖的每條邊進(jìn)行歷遍,? 當(dāng)全部邊的頂點(diǎn)顏色都不相同時(shí),? 則表明是一個(gè)可用的著色方案.

需要注意的是,? 盡管Reset可以快速地重置量子位,? 但是在程序結(jié)束前的Reset是沒有意義的.? 實(shí)際上量子計(jì)算機(jī)的重置是通過升溫或激光等方法使量子退相干,? 這個(gè)過程會(huì)損失大部分?jǐn)?shù)據(jù),? 所以不可以通過簡單Reset去重置tmpQubits.

可以留意到,? 上面的方法沒有使用到量子特性 [比如說相位, 疊加, 干涉等],? 所以這個(gè)算法是完全電子邏輯的.? 實(shí)際上把 `from nyasQuantumCalculate import *` 改為?`from nyasQuantumCalculate.RevCal import *` 從量子計(jì)算模擬切換為可逆電子計(jì)算模擬,? 上面的方法依然是正確的 [除了變量類型標(biāo)注].

Grover搜索算法

Grover算法是通用的搜索算法,? 通用的意思是,? 搜索過程與具體問題無關(guān),? 只要滿足:? 每次執(zhí)行某個(gè)黑盒所有正確答案的相位都被翻轉(zhuǎn),??Grover算法就搜索出黑盒里的"正確"答案.

Grover算法需要反復(fù)計(jì)算某個(gè)過程,? 每迭代一次(某種程度內(nèi)),? 測量得到正確答案就會(huì)增長.? 單次迭代包含兩步:? ?1)? 應(yīng)用黑盒;? 2) 應(yīng)用Grover擴(kuò)散算子(Grover?diffusion?operator).? 黑盒把正確答案的相位進(jìn)行翻轉(zhuǎn),? Grover算子把正確答案的出現(xiàn)概率增大,? 并減少錯(cuò)誤答案的出現(xiàn)概率.

Grover算子表示為

其中 W 為 Hadamard變換(Hadamard Transform),??Hadamard變換的逆為它自身,? 并且忽略全局相位的影響,? 則Grover算子為??.??關(guān)于Grover算子的細(xì)節(jié)就留到附章討論,? 這里先著重實(shí)現(xiàn)算法.

如果把系統(tǒng)狀態(tài)表示為正確答案和錯(cuò)誤答案的疊加態(tài),? 其中Good是正確答案,? Bad是錯(cuò)誤答案,? 則任意一個(gè)系統(tǒng)狀態(tài)都處于在??空間里的單位圓上.? 設(shè)系統(tǒng)的均勻疊加態(tài)??與??之間的夾角為θ,? 不難知道有以下關(guān)系:??, 其中M為全部正確答案的數(shù)量,? N為全部可能答案的數(shù)量.? 那么Grover算法的單次迭代實(shí)際上是把系統(tǒng)狀態(tài)在??空間里逆時(shí)針旋轉(zhuǎn)θ.? 如下圖

當(dāng)系統(tǒng)狀態(tài)與的夾角越靠近?π/2,? 測量結(jié)果越可能得出正確答案.? 不難看到如果迭代次數(shù)過多讓系統(tǒng)狀態(tài)接近的話,? 正確答案的概率會(huì)變小.? 所以最佳迭代次數(shù)為 ,? 其中[]為四舍五入,? sin^-1為方sin函數(shù) [arcsin].

搜索問題答案

在Grover算法里,? 黑盒是需要翻轉(zhuǎn)正確答案的相位,? 也就是相位黑盒,? 但這里設(shè)計(jì)的驗(yàn)證著色方案是否有效的算法是翻轉(zhuǎn)標(biāo)記位的狀態(tài),? 也就是標(biāo)記黑盒.? 可以使用"相位反沖"的技巧把標(biāo)記黑盒轉(zhuǎn)為相位黑盒.??有關(guān)量子黑盒

已知問題里有5個(gè)頂點(diǎn),? 又需要2bits表示顏色,? 也就是需要總共10個(gè)量子位來表示全部著色方案.??全部可能方案的數(shù)量為 2^10 = 1024 個(gè),? 而正確方案的數(shù)量為 2 * 4! = 48 個(gè),? 至于總共數(shù)量怎么出來就不是量子計(jì)算的討論范圍了.? 包裝Grover搜索算法:

可以注意到Grover搜索算法并不能保證運(yùn)行完后以100%概率測得正確方案,? 進(jìn)行測量后還需要對結(jié)果進(jìn)行檢查,? 如果不正確則重復(fù)運(yùn)行算法.? 測量后,? 量子位坍縮到測量結(jié)果里而損失其它信息,? 這時(shí)候可以使用另一個(gè)量子位與寄存器運(yùn)行GraphColoring檢查寄存器是否處于正確的方案里.? 綜上,? 搜索圖形著色方案的主體程序?yàn)?

加上輸出:

如果還是在意結(jié)果是否正確,? 可以在最下面加一段代碼驗(yàn)證:

其中answer包含全部正確方案.

經(jīng)過上面的例子可以看出,? Grover搜索算法并不能以概率1給出正確答案.? 并且有一個(gè)比較嚴(yán)苛的條件就是需要知道正確答案的總數(shù)M才能以最少運(yùn)行次數(shù)實(shí)現(xiàn)算法.? 實(shí)際操作里,? 如果不知道正確答案的總數(shù),? 可以讓 j 為一個(gè)較小的數(shù)字開始,? 比如說3,? 每次獲得錯(cuò)誤結(jié)果就增大 j. 直到獲得正確結(jié)果.

在使用nyasQuantumCalculate的時(shí)候,? 可以把 Options.autoNormalize 設(shè)為?False 以加快運(yùn)行速度.? 這個(gè)選項(xiàng)是在每個(gè)位門作用之后把系統(tǒng)歸一化,? 設(shè)置為False后每個(gè)位門的計(jì)算誤差會(huì)逐漸累積下來 [每次大約10^-17],? 在誤差過大的時(shí)候可能會(huì)導(dǎo)致一部分邏輯出錯(cuò),? 這時(shí)候可以調(diào)整 Utils 里的 delta 以允許更大的誤差 [默認(rèn)10^-8,? 調(diào)整需要直接修改庫].

老推銷員繼續(xù)推自己的庫: [github.com/nyasyamorina/nyasQuantumCalculate]

瑟圖群: [274767696]