4 月 20 日，在機器之心「量子計算」線上圓桌活動中，機器之心邀請到了中科院計算所研究員、量子計算實驗室主任孫曉明。他的演講主題為《量子搜索算法與線路優(yōu)化》，報告簡要回顧了搜索算法和線路優(yōu)化的發(fā)展以及目前面臨的挑戰(zhàn)，介紹了其團(tuán)隊在這兩方面的一些工作進(jìn)展。

演講回顧視頻（點擊閱讀原文查看）：https://app6ca5octe2206.pc.xiaoe-tech.com/detail/p_62612f69e4b09dda125e441b/6?fromH5=true

機器之心對他的演講內(nèi)容做了不改變原意的編輯。我今天想要介紹的是關(guān)于量子搜索算法與線路優(yōu)化，重點介紹搜索這部分。眾所周知，搜索是在經(jīng)典計算機上面應(yīng)用最廣泛的算法之一，它可以應(yīng)用于搜索引擎、路徑導(dǎo)航或者推薦系統(tǒng)等。現(xiàn)在它還可以應(yīng)用于新藥的研發(fā)，甚至我們可以將密碼破譯看成一個搜索問題。

舉例而言，我們想要破譯一個哈希函數(shù)，相當(dāng)于要搜到一個字符串，使得它哈希之后滿足某一些特性，比如它的前 32 位都是 0，等等。我們知道，計算機算法界有一套被奉為圣經(jīng)的圖書——Knuth 所著的《計算機編程的藝術(shù)》（The Art of Computer Programming），它的整個第三卷都在講 Sorting 和 Searching，由此可見搜索的重要性。

量子搜索算法

我們也知道，量子計算在 90 年代突然火了起來，其中一個重要的原因是兩個重要算法的提出，即 Shor 算法和 Grover 算法。Grover 算法Grover 算法可以在一個無序的數(shù)據(jù)庫上去查找一個特定的元素，比如想在一個數(shù)據(jù)庫里查一個特定的 IP 地址，或者找一個哈希函數(shù)的原像，以及棋類游戲的最優(yōu)策略，都可以看作一個搜索任務(wù)。

對于經(jīng)典算法來說，在一個沒有加過索引的數(shù)據(jù)庫上，如果數(shù)據(jù)庫的規(guī)模是 n 的話，那么肯定需要線性于 n 的時間。而量子算法可以有開平方量級的加速，它雖然沒有像 Shor 算法那樣能夠達(dá)到一個指數(shù)規(guī)模的加速，但開平方在很多情況下其實也很有意義。比如說在大數(shù)據(jù)處理中，本來有 1 億條的數(shù)據(jù)要處理，Grover 算法可以做到萬這個量級。再比如密碼分析，原本是 2 的 90 次方的一個暴力枚舉算法，我們可以降到 2 的 45 次方左右。對于現(xiàn)在的超算，2 的 45 次方的規(guī)模是可以接受的。

對于 Grover 搜索，它里面要用到一個很重要的模塊——Oracle。我們經(jīng)常會看到這樣一種說法，如果有 50 個量子比特就可以實現(xiàn) 2 的 50 次方的并行加速，這件事情基本上是對的。他其實在說這樣一件事情，如果可以制備 n 個比特的疊加態(tài)，譬如我們記 n 是 logN 的話，那么事先制備 n 個零態(tài)，然后做一個 Hardmard 變換之后，它就可以生成所有的從 1 到 N（或者從 0 到 N-1=2 的 n 次方減 1）個計算基的疊加態(tài)。然后根據(jù)線性性，它經(jīng)過一個 Oracle 之后就可以計算全部的 f(x)（x=1~N），會得到這樣一個態(tài)（圖中包含藍(lán)色的疊加態(tài)）。

這里其實有兩個問題，剩余的報告里也會談到，就是涉及到 Oracle 的制備，它是基于 QRAM 可以實現(xiàn)的角度。但在很多問題當(dāng)中，這個 Oracle 是有具體的意義的，比如像我們剛才介紹過的，它可能是下圖左上角的一個哈希函數(shù)，或者甚至是一個 NP 完全問題，比如一個 SAT 公式等。這樣一個 oracle 該怎么制備呢？其實大家很早（例如 Nielsen 和 Chuang 的《Quantum Computation and Quantum Information》書中）就定性地知道：只要是一個可逆函數(shù)，那么都可以通過量子的方式實現(xiàn)出來。最近，我們在 oracle 的定量實現(xiàn)方面做過這樣一個工作，已經(jīng)上傳到了 arxiv 上。我們針對的是這樣一類函數(shù)，即 CNF 或者 SAT oracle 的制備。論文地址：https://arxiv.org/pdf/2101.05430.pdf

另外一個問題是怎么樣讀出計算結(jié)果？我們知道量子的測不準(zhǔn)原理， 2^n個結(jié)果是不可能一次全部讀出來的，每次讀出來的概率其實只有1/2^n，這意味著如果有50個比特的話，每次只有 1/2^50 的概率看見任何一個結(jié)果。如果想要拿到特定的計算結(jié)果，又要花 2^50 的時間重復(fù)測量，所以這里量子就沒有產(chǎn)生加速。

但是，Grover 算法很巧妙的設(shè)計了一個通過若干次的對稱和反轉(zhuǎn)，然后只需要根號 N 的時間，就能夠以高概率拿到我們想要的結(jié)果。

振幅放大算法

在 Grover 之后，理論工作者又提出了一個被稱為振幅放大的算法，它想要解決的是這樣一個場景：如果現(xiàn)在有一個隨機搜索算法，它的成功率可能比較低，比如萬分之 1。我們希望通過調(diào)用這個算法來拿到一個高的成功概率。

古人常說，「三個臭皮匠頂個諸葛亮」。如果每一個算法的成功概率是萬分之 1，那么我們平均要重復(fù) 1 萬次。但是，使用振幅放大算法的思想（它和 Grover 很像）可以做到開平方，也就是說本來要 1 萬次，其實只需要大約 100 次這個量級就可以做成。

當(dāng)然這需要事先把這個算法變成一個量子算法，然后才可以產(chǎn)生這樣一個加速。比如說我們把它應(yīng)用到剛才說的 NP 完全問題或 SAT 問題上，如果隨機地選一個解，成功的概率是 1/2^n。所以，如果只是簡單粗暴地使用一下 Grover 算法，就可以做到根號 2 的 n 次方，也就 1.414^n。

但是還可以再加一些算法設(shè)計的技巧，這是因為剛才只是簡單地調(diào)用一下 Grover 算法，并沒有任何算法的技術(shù)在里面。假如做一些更好的算法設(shè)計，并使用一些更好的 SAT 求解算法的話，事實上復(fù)雜性可以做到比原來要小很多。

另外還有一些問題，比如在大數(shù)據(jù)里，我們經(jīng)常想在一個社區(qū)里找一個子團(tuán)，哪怕是找一個三角形這樣最簡單的子團(tuán)。其實，這個問題到現(xiàn)在都不知道它最好的量子算法可以做到什么程度。

如果簡單地用 Grover 算法可以做一個 n^1.5 的算法，因為三角形一共最多是 n^3，所以 Grover 就可以做 n^1.5。后來 Szegedy 可以做到 n^10/7，到現(xiàn)在可以做到 n^5/4。但是否還有更好的，我們尚不清楚。

這其實給我們一個啟示，即很多人在問的量子算法為什么設(shè)計起來比較難。在我看來，一個方面的原因是量子確實有一點反直觀，它不像我們經(jīng)典世界那樣看得見摸得著，所以設(shè)計起來是有不小的難度。另一方面目前從事該方向研究的人員還很不足，紐約時報的一個報道稱全世界從事量子計算的專家不超過一千人。

研究成果介紹局部搜索下面介紹我與勝譽以前共同做的一個工作：Grover 搜索可以用來解求全局極值，即需要根號 n 的時間就可以找到一個全局極大值或極小值。如果我們只需要找一個局部極值，譬如在機器學(xué)習(xí)里有很多應(yīng)用，很多時候其實找一個局部極值就可以。Aaronson 最早研究了這一問題并給出了一個基本上可以做到開三次方的算法。勝譽、姚老師和我一起證明了，這個開三次方的加速就是最好的了。

權(quán)重判定

下面分享一下我們最近做的一個小工作，稱為權(quán)重判定問題。它需要區(qū)分這樣兩種情況，即解的個數(shù)或者有 k 個或者有 l 個，k 和 l 是事先給定的兩個數(shù)。其他的情形都不管，只需要能區(qū)分這兩種權(quán)重就行。

我們可以看到一些特例，譬如說 k 等于 0，l 等于 n/2，即恰好有一半解還是一個解都沒有。這個就是最早提出的第一個量子算法，即 Deustch-Josza 算法要做的事情。再譬如 k 等于 0，l 等于 1，區(qū)分有沒有至少一個解，這個就是 Grover 算法做的事情。

其實在我們之前，中山大學(xué)的邱道文老師他們做過一些工作，另外其他研究者也做過一些工作，這里不再一一贅述。

主要結(jié)果接下來直接說一下我們的結(jié)論，我們給出了一個下界和一個上界。這里我用圖來說明上下界分別是什么樣子。右上圖說的是上界，也就是一個量子算法。對于不同的參數(shù) d，我們可以首先生成一批點，譬如之前的工作能做的區(qū)域只有綠色、紅色以及這些點（中間圖）。我們基本上把所有的區(qū)域都解決了，比如說 d=2 的時候有兩個點（右上圖），這兩個點它左上都只需要 1 次量子查詢，就和（左圖）綠色的一樣。

再下一個 Case 有 5 個點，就是下面右上圖中的 4 個紅點和 1 個藍(lán)點。它的左上方的淺藍(lán)色區(qū)域，量子只需要兩步就可以解決，完全覆蓋了之前的一些結(jié)論。同時，這 5 個點的右下方，也就是右下圖淺黃色這片區(qū)域。我們可以證明，它們是不可能用量子兩步解決的，至少要三步。然后，我們進(jìn)一步定義集合 S_3，即有另一批點。它的左上方有一個算法可以 3 步做成，它的右下方任何算法至少要 4 步才能做成，類似可以推廣到任意的d。剛才勝譽的工作也提到了我以前的博士生袁佩，這個工作是和袁佩博士、現(xiàn)在的一個博士生何嘯宇以及前同事楊光一起做的。

量子復(fù)雜性下界同時我們還做了一個下界，也就是說，我們可以證明在一些區(qū)域上量子不能做得特別好。其中最核心的一個定理是 2001 年 Beals 等人證明的一個結(jié)論，對精確量子算法，它的復(fù)雜度可以被這個函數(shù)寫成一個多項式后它的 Degree 除以 2 給出一個下界。所以，我們就可以把這個問題轉(zhuǎn)化成去考慮它的多項式表示的多項式次數(shù)。

研究多項式次數(shù)需要用到一些工具，這里有一個很著名的多項式叫切比雪夫多項式（Chebyshev Polynomials），就是說 cos mθ（m 是一個整數(shù)）都可以寫成 cos θ的一個多項式，比如根據(jù)二倍角公式，cos 3θ可以寫成，等等。

Grover 搜索背后的關(guān)鍵其實也是這樣一個切比雪夫多項式。我們在這個工作中也要用到它，最關(guān)鍵的一點就是切比雪夫多項式構(gòu)成了多項式空間的一組基。接著我們把任何一個多項式展開到這組基上，再利用切比雪夫多項式的一些性質(zhì)證出來一個下界。

帶先驗知識的量子搜索下面介紹我們最近做的另一個工作，稱為帶先驗知識的量子搜索。由于在 Grover 搜索中，我們對想要找的解一無所知，也就是說它是任何一個的概率都是相等的。但在有些搜索問題里，比如α-β剪枝，我們事先知道一定的概率分布，即走哪條路的概率更高一點。

假如我們現(xiàn)在把它建模成 p = (p_1, p_2, …, p_N) 的形式，我們知道 1 是解的概率是 p_1，2 是解的概率是 p_2，N 是解的概率是 p_N。在這種情況下怎樣做一個最好的搜索呢？我們最近研究了這個問題，大概的核心結(jié)論是需要制備一個特殊的初態(tài)，這也是后來我們跟勝譽一起討論初態(tài)制備問題的出發(fā)點之一。制備了這個特殊的初態(tài)之后，后面的算法步驟（對稱、翻轉(zhuǎn)等）跟 Grover 算法很像。我們可以證明，這樣做在漸進(jìn)意義上幾乎是最優(yōu)的。

電路優(yōu)化下面再簡單介紹一下量子電路優(yōu)化方面的工作。最近，量子硬件發(fā)展很快，John Preskill 教授在 2018 年提出了一個概念，叫做 NISQ（含噪聲、中等尺度量子系統(tǒng)）。剛才勝譽也提到 IBM 有個路線圖，稱明年就可以做到 1000 多個比特。但是，它的特點是噪聲很大，所以需要壓縮電路的深度。

之前我們做了這樣一個工作，就是去討論 CNOT 電路的線路深度。眾所周知，CNOT 加上單比特門就是 Universal 的，可以生成任何的量子電路。所以，CNOT 電路有一定的重要性。

下面是一個例子，說明一個 CNOT 電路可以轉(zhuǎn)成一個等價的電路。原來的深度是 7，現(xiàn)在深度是 5。最核心的一點是，CNOT 電路本質(zhì)上可以寫成這些變量的一個線性組合。

CNOT 電路的化簡其實和 F_2 上的可逆矩陣分解有重要聯(lián)系。事實上，我們在每一層上可以放多個 CNOT 門，譬如下面左下圖第一層放了兩個 CNOT 門，它對應(yīng)右下圖第二個矩陣。從線性代數(shù)上，可以將它看作一個行消元，即把第一行加到第二行，第三行加到第四行。

所以，CNOT 電路的化簡可以變成這樣一個數(shù)學(xué)問題，即如果允許并行的高斯消元，要把一個可逆的矩陣化成單位陣，最少需要多少步？注意每一步可以并行地來做。

結(jié)果介紹我們做了如下一些結(jié)果，主線是討論輔助比特和電路深度之間的關(guān)系。這是之前的結(jié)果，輔助比特達(dá)到 n^2 的時候有一個結(jié)果，輔助比特為 0 的時候也有一些結(jié)果。我們可以把兩邊的結(jié)果都加以改進(jìn)，而且還有一個更一般性的結(jié)果，就是如果有 m 個輔助比特，那么這個電路深度可以優(yōu)化到一個緊的界，即下圖右下方的表達(dá)式。特別的當(dāng) m 等于 0 和 m 等于 n^2 的時候，我們的結(jié)果分別可以把原來的兩個界優(yōu)化一些。

團(tuán)隊及書籍介紹下圖中是我們中科院計算所量子計算與算法理論實驗室團(tuán)隊的一部分成員，包括剛才工作中提到的張家琳老師、田國敬老師、袁佩博士、蔣佳卿、何嘯宇和楊帥等。

這次活動我們得到了兩家出版社的大力支持。與尚云教授、李綠周教授、尹璋琦教授、魏朝暉博士、田國敬博士一起，我們花了三年時間翻譯了量子計算領(lǐng)域最經(jīng)典的一本教材，即 Michael A. Nielsen 和 Isaac L. Chuang 合著的《量子計算與量子信息》（10 周年版）（Quantum Computation and Quantum Information 10th Anniversary Edition） ，譯著共 570 多頁。我們覺得它是一本非常優(yōu)秀的教材，即使從現(xiàn)在的角度來看。當(dāng)然，這本書確實缺少一些比較近期的（比如在硬件實現(xiàn)方面）內(nèi)容。但是它作為入門教材對讀者非常友好，特別是如果你從屬于計算機領(lǐng)域，并且想要學(xué)習(xí)量子計算，那么你只需要掌握最基本的線性代數(shù)知識，閱讀這本書就完全沒有問題。