機(jī)器之心報(bào)道
機(jī)器之心編輯部
4 月 20 日，在機(jī)器之心「量子計(jì)算」線上圓桌活動(dòng)中，機(jī)器之心邀請到了中科院計(jì)算所研究員、量子計(jì)算實(shí)驗(yàn)室主任孫曉明。他的演講主題為《量子搜索算法與線路優(yōu)化》，報(bào)告簡要回顧了搜索算法和線路優(yōu)化的發(fā)展以及目前面臨的挑戰(zhàn)，介紹了其團(tuán)隊(duì)在這兩方面的一些工作進(jìn)展。
機(jī)器之心對他的演講內(nèi)容做了不改變原意的編輯。
我今天想要介紹的是關(guān)于量子搜索算法與線路優(yōu)化，重點(diǎn)介紹搜索這部分。眾所周知，搜索是在經(jīng)典計(jì)算機(jī)上面應(yīng)用最廣泛的算法之一，它可以應(yīng)用于搜索引擎、路徑導(dǎo)航或者推薦系統(tǒng)等�，F(xiàn)在它還可以應(yīng)用于新藥的研發(fā)，甚至我們可以將密碼破譯看成一個(gè)搜索問題。
舉例而言，我們想要破譯一個(gè)哈希函數(shù)，相當(dāng)于要搜到一個(gè)字符串，使得它哈希之后滿足某一些特性，比如它的前 32 位都是 0，等等。我們知道，計(jì)算機(jī)算法界有一套被奉為圣經(jīng)的圖書Knuth 所著的《計(jì)算機(jī)編程的藝術(shù)》（The Art of Computer Programming），它的整個(gè)第三卷都在講 Sorting 和 Searching，由此可見搜索的重要性。
量子搜索算法
我們也知道，量子計(jì)算在 90 年代突然火了起來，其中一個(gè)重要的原因是兩個(gè)重要算法的提出，即 Shor 算法和 Grover 算法。
Grover 算法
Grover 算法可以在一個(gè)無序的數(shù)據(jù)庫上去查找一個(gè)特定的元素，比如想在一個(gè)數(shù)據(jù)庫里查一個(gè)特定的 IP 地址，或者找一個(gè)哈希函數(shù)的原像，以及棋類游戲的最優(yōu)策略，都可以看作一個(gè)搜索任務(wù)。
對于經(jīng)典算法來說，在一個(gè)沒有加過索引的數(shù)據(jù)庫上，如果數(shù)據(jù)庫的規(guī)模是 n 的話，那么肯定需要線性于 n 的時(shí)間。而量子算法可以有開平方量級的加速，它雖然沒有像 Shor 算法那樣能夠達(dá)到一個(gè)指數(shù)規(guī)模的加速，但開平方在很多情況下其實(shí)也很有意義。比如說在大數(shù)據(jù)處理中，本來有 1 億條的數(shù)據(jù)要處理，Grover 算法可以做到萬這個(gè)量級。
再比如密碼分析，原本是 2 的 90 次方的一個(gè)暴力枚舉算法，我們可以降到 2 的 45 次方左右。對于現(xiàn)在的超算，2 的 45 次方的規(guī)模是可以接受的。
對于 Grover 搜索，它里面要用到一個(gè)很重要的模塊Oracle。我們經(jīng)常會(huì)看到這樣一種說法，如果有 50 個(gè)量子比特就可以實(shí)現(xiàn) 2 的 50 次方的并行加速，這件事情基本上是對的。他其實(shí)在說這樣一件事情，如果可以制備 n 個(gè)比特的疊加態(tài)，譬如我們記 n 是 logN 的話，那么事先制備 n 個(gè)零態(tài)，然后做一個(gè) Hardmard 變換之后，它就可以生成所有的從 1 到 N（或者從 0 到 N-1=2 的 n 次方減 1）個(gè)計(jì)算基的疊加態(tài)。然后根據(jù)線性性，它經(jīng)過一個(gè) Oracle 之后就可以計(jì)算全部的 f(x)（x=1~N），會(huì)得到這樣一個(gè)態(tài)（圖中包含藍(lán)色的疊加態(tài)）。
這里其實(shí)有兩個(gè)問題，剩余的報(bào)告里也會(huì)談到，就是涉及到 Oracle 的制備，它是基于 QRAM 可以實(shí)現(xiàn)的角度。但在很多問題當(dāng)中，這個(gè) Oracle 是有具體的意義的，比如像我們剛才介紹過的，它可能是下圖左上角的一個(gè)哈希函數(shù)，或者甚至是一個(gè) NP 完全問題，比如一個(gè) SAT 公式等。這樣一個(gè) oracle 該怎么制備呢？其實(shí)大家很早（例如 Nielsen 和 Chuang 的《Quantum Computation and Quantum Information》書中）就定性地知道：只要是一個(gè)可逆函數(shù)，那么都可以通過量子的方式實(shí)現(xiàn)出來。
最近，我們在 oracle 的定量實(shí)現(xiàn)方面做過這樣一個(gè)工作，已經(jīng)上傳到了 arxiv 上。我們針對的是這樣一類函數(shù)，即 CNF 或者 SAT oracle 的制備。
論文地址：https://arxiv.org/pdf/2101.05430.pdf
另外一個(gè)問題是怎么樣讀出計(jì)算結(jié)果？我們知道量子的測不準(zhǔn)原理， 2^n個(gè)結(jié)果是不可能一次全部讀出來的，每次讀出來的概率其實(shí)只有1/2^n，這意味著如果有50個(gè)比特的話，每次只有 1/2^50 的概率看見任何一個(gè)結(jié)果。如果想要拿到特定的計(jì)算結(jié)果，又要花 2^50 的時(shí)間重復(fù)測量，所以這里量子就沒有產(chǎn)生加速。
但是，Grover 算法很巧妙的設(shè)計(jì)了一個(gè)通過若干次的對稱和反轉(zhuǎn)，然后只需要根號 N 的時(shí)間，就能夠以高概率拿到我們想要的結(jié)果。
振幅放大算法
在 Grover 之后，理論工作者又提出了一個(gè)被稱為振幅放大的算法，它想要解決的是這樣一個(gè)場景：如果現(xiàn)在有一個(gè)隨機(jī)搜索算法，它的成功率可能比較低，比如萬分之 1。我們希望通過調(diào)用這個(gè)算法來拿到一個(gè)高的成功概率。
古人常說，「三個(gè)臭皮匠頂個(gè)諸葛亮」。如果每一個(gè)算法的成功概率是萬分之 1，那么我們平均要重復(fù) 1 萬次。但是，使用振幅放大算法的思想（它和 Grover 很像）可以做到開平方，也就是說本來要 1 萬次，其實(shí)只需要大約 100 次這個(gè)量級就可以做成。
當(dāng)然這需要事先把這個(gè)算法變成一個(gè)量子算法，然后才可以產(chǎn)生這樣一個(gè)加速。比如說我們把它應(yīng)用到剛才說的 NP 完全問題或 SAT 問題上，如果隨機(jī)地選一個(gè)解，成功的概率是 1/2^n。所以，如果只是簡單粗暴地使用一下 Grover 算法，就可以做到根號 2 的 n 次方，也就 1.414^n。
但是還可以再加一些算法設(shè)計(jì)的技巧，這是因?yàn)閯偛胖皇呛唵蔚卣{(diào)用一下 Grover 算法，并沒有任何算法的技術(shù)在里面。假如做一些更好的算法設(shè)計(jì)，并使用一些更好的 SAT 求解算法的話，事實(shí)上復(fù)雜性可以做到比原來要小很多。
另外還有一些問題，比如在大數(shù)據(jù)里，我們經(jīng)常想在一個(gè)社區(qū)里找一個(gè)子團(tuán)，哪怕是找一個(gè)三角形這樣最簡單的子團(tuán)。其實(shí)，這個(gè)問題到現(xiàn)在都不知道它最好的量子算法可以做到什么程度。
如果簡單地用 Grover 算法可以做一個(gè) n^1.5 的算法，因?yàn)槿切我还沧疃嗍?n^3，所以 Grover 就可以做 n^1.5。后來 Szegedy 可以做到 n^10/7，到現(xiàn)在可以做到 n^5/4。但是否還有更好的，我們尚不清楚。
這其實(shí)給我們一個(gè)啟示，即很多人在問的量子算法為什么設(shè)計(jì)起來比較難。在我看來，一個(gè)方面的原因是量子確實(shí)有一點(diǎn)反直觀，它不像我們經(jīng)典世界那樣看得見摸得著，所以設(shè)計(jì)起來是有不小的難度。另一方面目前從事該方向研究的人員還很不足，紐約時(shí)報(bào)的一個(gè)報(bào)道稱全世界從事量子計(jì)算的專家不超過一千人。
研究成果介紹
局部搜索
下面介紹我與勝譽(yù)以前共同做的一個(gè)工作：Grover 搜索可以用來解求全局極值，即需要根號 n 的時(shí)間就可以找到一個(gè)全局極大值或極小值。如果我們只需要找一個(gè)局部極值，譬如在機(jī)器學(xué)習(xí)里有很多應(yīng)用，很多時(shí)候其實(shí)找一個(gè)局部極值就可以。
Aaronson 最早研究了這一問題并給出了一個(gè)基本上可以做到開三次方的算法。勝譽(yù)、姚老師和我一起證明了，這個(gè)開三次方的加速就是最好的了。
權(quán)重判定
下面分享一下我們最近做的一個(gè)小工作，稱為權(quán)重判定問題。它需要區(qū)分這樣兩種情況，即解的個(gè)數(shù)或者有 k 個(gè)或者有 l 個(gè)，k 和 l 是事先給定的兩個(gè)數(shù)。其他的情形都不管，只需要能區(qū)分這兩種權(quán)重就行。
我們可以看到一些特例，譬如說 k 等于 0，l 等于 n/2，即恰好有一半解還是一個(gè)解都沒有。這個(gè)就是最早提出的第一個(gè)量子算法，即 Deustch-Josza 算法要做的事情。再譬如 k 等于 0，l 等于 1，區(qū)分有沒有至少一個(gè)解，這個(gè)就是 Grover 算法做的事情。
其實(shí)在我們之前，中山大學(xué)的邱道文老師他們做過一些工作，另外其他研究者也做過一些工作，這里不再一一贅述。
主要結(jié)果
接下來直接說一下我們的結(jié)論，我們給出了一個(gè)下界和一個(gè)上界。這里我用圖來說明上下界分別是什么樣子。
右上圖說的是上界，也就是一個(gè)量子算法。對于不同的參數(shù) d，我們可以首先生成一批點(diǎn)，譬如之前的工作能做的區(qū)域只有綠色、紅色以及這些點(diǎn)（中間圖）。我們基本上把所有的區(qū)域都解決了，比如說 d=2 的時(shí)候有兩個(gè)點(diǎn)（右上圖），這兩個(gè)點(diǎn)它左上都只需要 1 次量子查詢，就和（左圖）綠色的一樣。
再下一個(gè) Case 有 5 個(gè)點(diǎn)，就是下面右上圖中的 4 個(gè)紅點(diǎn)和 1 個(gè)藍(lán)點(diǎn)。它的左上方的淺藍(lán)色區(qū)域，量子只需要兩步就可以解決，完全覆蓋了之前的一些結(jié)論。同時(shí)，這 5 個(gè)點(diǎn)的右下方，也就是右下圖淺黃色這片區(qū)域。我們可以證明，它們是不可能用量子兩步解決的，至少要三步。
然后，我們進(jìn)一步定義集合 S_3，即有另一批點(diǎn)。它的左上方有一個(gè)算法可以 3 步做成，它的右下方任何算法至少要 4 步才能做成，類似可以推廣到任意的d。
剛才勝譽(yù)的工作也提到了我以前的博士生袁佩，這個(gè)工作是和袁佩博士、現(xiàn)在的一個(gè)博士生何嘯宇以及前同事楊光一起做的。
量子復(fù)雜性下界
同時(shí)我們還做了一個(gè)下界，也就是說，我們可以證明在一些區(qū)域上量子不能做得特別好。其中最核心的一個(gè)定理是 2001 年 Beals 等人證明的一個(gè)結(jié)論，對精確量子算法，它的復(fù)雜度可以被這個(gè)函數(shù)寫成一個(gè)多項(xiàng)式后它的 Degree 除以 2 給出一個(gè)下界。所以，我們就可以把這個(gè)問題轉(zhuǎn)化成去考慮它的多項(xiàng)式表示的多項(xiàng)式次數(shù)。
研究多項(xiàng)式次數(shù)需要用到一些工具，這里有一個(gè)很著名的多項(xiàng)式叫切比雪夫多項(xiàng)式（Chebyshev Polynomials），就是說 cos mθ（m 是一個(gè)整數(shù)）都可以寫成 cos θ的一個(gè)多項(xiàng)式，比如根據(jù)二倍角公式，cos 3θ可以寫成，等等。
Grover 搜索背后的關(guān)鍵其實(shí)也是這樣一個(gè)切比雪夫多項(xiàng)式。我們在這個(gè)工作中也要用到它，最關(guān)鍵的一點(diǎn)就是切比雪夫多項(xiàng)式構(gòu)成了多項(xiàng)式空間的一組基。接著我們把任何一個(gè)多項(xiàng)式展開到這組基上，再利用切比雪夫多項(xiàng)式的一些性質(zhì)證出來一個(gè)下界。
帶先驗(yàn)知識的量子搜索
下面介紹我們最近做的另一個(gè)工作，稱為帶先驗(yàn)知識的量子搜索。由于在 Grover 搜索中，我們對想要找的解一無所知，也就是說它是任何一個(gè)的概率都是相等的。但在有些搜索問題里，比如α-β剪枝，我們事先知道一定的概率分布，即走哪條路的概率更高一點(diǎn)。
假如我們現(xiàn)在把它建模成 p = (p_1, p_2, …, p_N) 的形式，我們知道 1 是解的概率是 p_1，2 是解的概率是 p_2，N 是解的概率是 p_N。在這種情況下怎樣做一個(gè)最好的搜索呢？我們最近研究了這個(gè)問題，大概的核心結(jié)論是需要制備一個(gè)特殊的初態(tài)，這也是后來我們跟勝譽(yù)一起討論初態(tài)制備問題的出發(fā)點(diǎn)之一。
制備了這個(gè)特殊的初態(tài)之后，后面的算法步驟（對稱、翻轉(zhuǎn)等）跟 Grover 算法很像。我們可以證明，這樣做在漸進(jìn)意義上幾乎是最優(yōu)的。
電路優(yōu)化
下面再簡單介紹一下量子電路優(yōu)化方面的工作。最近，量子硬件發(fā)展很快，John Preskill 教授在 2018 年提出了一個(gè)概念，叫做 NISQ（含噪聲、中等尺度量子系統(tǒng)）。剛才勝譽(yù)也提到 IBM 有個(gè)路線圖，稱明年就可以做到 1000 多個(gè)比特。但是，它的特點(diǎn)是噪聲很大，所以需要壓縮電路的深度。
之前我們做了這樣一個(gè)工作，就是去討論 CNOT 電路的線路深度。眾所周知，CNOT 加上單比特門就是 Universal 的，可以生成任何的量子電路。所以，CNOT 電路有一定的重要性。
下面是一個(gè)例子，說明一個(gè) CNOT 電路可以轉(zhuǎn)成一個(gè)等價(jià)的電路。原來的深度是 7，現(xiàn)在深度是 5。最核心的一點(diǎn)是，CNOT 電路本質(zhì)上可以寫成這些變量的一個(gè)線性組合。
CNOT 電路的化簡其實(shí)和 F_2 上的可逆矩陣分解有重要聯(lián)系。事實(shí)上，我們在每一層上可以放多個(gè) CNOT 門，譬如下面左下圖第一層放了兩個(gè) CNOT 門，它對應(yīng)右下圖第二個(gè)矩陣。從線性代數(shù)上，可以將它看作一個(gè)行消元，即把第一行加到第二行，第三行加到第四行。
所以，CNOT 電路的化簡可以變成這樣一個(gè)數(shù)學(xué)問題，即如果允許并行的高斯消元，要把一個(gè)可逆的矩陣化成單位陣，最少需要多少步？注意每一步可以并行地來做。
結(jié)果介紹
我們做了如下一些結(jié)果，主線是討論輔助比特和電路深度之間的關(guān)系。
這是之前的結(jié)果，輔助比特達(dá)到 n^2 的時(shí)候有一個(gè)結(jié)果，輔助比特為 0 的時(shí)候也有一些結(jié)果。我們可以把兩邊的結(jié)果都加以改進(jìn)，而且還有一個(gè)更一般性的結(jié)果，就是如果有 m 個(gè)輔助比特，那么這個(gè)電路深度可以優(yōu)化到一個(gè)緊的界，即下圖右下方的表達(dá)式。特別的當(dāng) m 等于 0 和 m 等于 n^2 的時(shí)候，我們的結(jié)果分別可以把原來的兩個(gè)界優(yōu)化一些。
團(tuán)隊(duì)及書籍介紹
下圖中是我們中科院計(jì)算所量子計(jì)算與算法理論實(shí)驗(yàn)室團(tuán)隊(duì)的一部分成員，包括剛才工作中提到的張家琳老師、田國敬老師、袁佩博士、蔣佳卿、何嘯宇和楊帥等。
這次活動(dòng)我們得到了兩家出版社的大力支持。與尚云教授、李綠周教授、尹璋琦教授、魏朝暉博士、田國敬博士一起，我們花了三年時(shí)間翻譯了量子計(jì)算領(lǐng)域最經(jīng)典的一本教材，即 Michael A. Nielsen 和 Isaac L. Chuang 合著的《量子計(jì)算與量子信息》（10 周年版）（Quantum Computation and Quantum Information 10th Anniversary Edition） ，譯著共 570 多頁。
我們覺得它是一本非常優(yōu)秀的教材，即使從現(xiàn)在的角度來看。當(dāng)然，這本書確實(shí)缺少一些比較近期的（比如在硬件實(shí)現(xiàn)方面）內(nèi)容。但是它作為入門教材對讀者非常友好，特別是如果你從屬于計(jì)算機(jī)領(lǐng)域，并且想要學(xué)習(xí)量子計(jì)算，那么你只需要掌握最基本的線性代數(shù)知識，閱讀這本書就完全沒有問題。
