12555
0
2020-11-04
2021-09-14
由中山大學(xué)李綠周、北京郵電大學(xué)高飛、南京大學(xué)姚鵬暉、中科院計(jì)算所田國敬等幾位老師及相關(guān)團(tuán)隊(duì)成員（北郵潘世杰，中大何鍵浩、葉澤坤）共同撰寫的《CCF2019-2020中國計(jì)算機(jī)科學(xué)技術(shù)發(fā)展報(bào)告》之題為“量子算法與復(fù)雜性研究進(jìn)展概述”的章節(jié)近日正式出版。雖然紕漏難免，但愿如文中所言“希望本文能夠讓更多計(jì)算機(jī)、 物理、數(shù)學(xué)等相關(guān)領(lǐng)域的研究人員更好地了解量子計(jì)算理論方面的進(jìn)展，借此也呼吁更多的學(xué)者和青年學(xué)生加入這個(gè)極具挑戰(zhàn)性的研究領(lǐng)域"
以下摘錄引言部分，全文初稿見附件。如果成為CCF會(huì)員，可在中國計(jì)算機(jī)學(xué)會(huì)（CCF）官網(wǎng)訪問機(jī)械工業(yè)出版社正式出版的電子版全文以及更多豐富的學(xué)術(shù)資源。
引用文章內(nèi)容請(qǐng)標(biāo)注：
李綠周，高飛，姚鵬暉，田國敬，何鍵浩，潘世杰，葉澤坤，量子算法與復(fù)雜性研究進(jìn)展概述，CCF2019-2020中國計(jì)算機(jī)科學(xué)技術(shù)發(fā)展報(bào)告/ 中國計(jì)算機(jī)學(xué)會(huì)編，p. 1-59，機(jī)械工業(yè)出版社，2020.10.
毋庸置疑，量子計(jì)算作為一種顛覆性技術(shù)已經(jīng)引起了各界的廣泛關(guān)注。然而需指出是，就可計(jì)算性而言量子計(jì)算并沒有超越經(jīng)典計(jì)算，但就計(jì)算復(fù)雜性來說量子計(jì)算展現(xiàn)出巨大的優(yōu)勢(shì)。例如，Shor量子算法可以在多項(xiàng)式時(shí)間內(nèi)解決大數(shù)因子分解問題，從而在理論上對(duì)現(xiàn)代密碼造成了極大威脅。量子計(jì)算相對(duì)于經(jīng)典計(jì)算在哪些方面有優(yōu)勢(shì)？有多大程度的優(yōu)勢(shì)？這些問題都遠(yuǎn)未搞清楚，需要持續(xù)深入地研究。相比于廣闊的未知領(lǐng)域，目前能展現(xiàn)量子計(jì)算優(yōu)勢(shì)的例證不是太多，而是太少。探尋量子優(yōu)勢(shì)是量子計(jì)算研究的核心問題之一，有待廣大研究者去發(fā)現(xiàn)新的大陸。
從理論計(jì)算機(jī)科學(xué)的角度來看，至少可以從以下一些不同的視角來探尋量子計(jì)算的優(yōu)勢(shì)：
查詢復(fù)雜性。關(guān)注計(jì)算過程調(diào)用某一子過程的次數(shù)，而忽略其他計(jì)算代價(jià)。目前量子計(jì)算相對(duì)于經(jīng)典計(jì)算的優(yōu)勢(shì)很多時(shí)候是通過查詢復(fù)雜度得以體現(xiàn)，例如著名的Grover算法。這方面有一套比較系統(tǒng)的分析查詢復(fù)雜度上下界的方法，并且量子計(jì)算的優(yōu)勢(shì)可以從查詢復(fù)雜性角度得以嚴(yán)格證明。
交互計(jì)算復(fù)雜性。 關(guān)注多個(gè)計(jì)算個(gè)體協(xié)同完成某一個(gè)任務(wù)，由于信息不完備或者計(jì)算個(gè)體不可靠而產(chǎn)生的復(fù)雜性現(xiàn)象，包括交互式證明系統(tǒng)和通信復(fù)雜性。量子計(jì)算在這個(gè)模型中有著獨(dú)特的優(yōu)勢(shì)。這方面目前已經(jīng)取得了一系列重要成果。
時(shí)間復(fù)雜性。關(guān)注計(jì)算過程所耗費(fèi)的時(shí)間，如Shor算法就在時(shí)間復(fù)雜度上展示出相對(duì)于目前最好的經(jīng)典算法的優(yōu)勢(shì)。不過，從時(shí)間復(fù)雜性的角度目前暫時(shí)無法嚴(yán)格證明量子計(jì)算對(duì)于經(jīng)典計(jì)算的優(yōu)勢(shì)，這與計(jì)算復(fù)雜性領(lǐng)域的重大理論問題P是否等于NP緊密相關(guān)。盡管如此，這并不妨礙開展量子計(jì)算研究，因?yàn)榘l(fā)現(xiàn)比目前最好的經(jīng)典算法更好的量子算法總是一件振奮人心的事情。
樣本復(fù)雜性。關(guān)注在學(xué)習(xí)某一個(gè)目標(biāo)函數(shù)的過程中需要用到多少樣本數(shù)據(jù)，這是學(xué)習(xí)理論領(lǐng)域研究的重要問題。近幾年研究人員初步考慮了量子學(xué)習(xí)理論方面的問題，主要是通過比較量子樣本復(fù)雜性與經(jīng)典樣本復(fù)雜性來刻畫量子計(jì)算的優(yōu)勢(shì)?？偟膩碚f，量子計(jì)算在這方面的研究有待加強(qiáng)。
電路深度復(fù)雜性。關(guān)注邏輯電路中邏輯門的層數(shù)，即如何盡可能并行化地完成計(jì)算。量子計(jì)算相對(duì)于經(jīng)典計(jì)算的優(yōu)勢(shì)可以在電路深度復(fù)雜性方面得以展示，例如最近Science上就有工作表明：存在計(jì)算問題能被常數(shù)深度的量子電路解決，而任意常數(shù)深度的經(jīng)典電路不可能以高成功概率解決。
除此之外，還可以考慮有限自動(dòng)機(jī)(狀態(tài)變遷系統(tǒng))的狀態(tài)復(fù)雜性，這方面早就有研究成果表明：量子有限自動(dòng)機(jī)相對(duì)于經(jīng)典自動(dòng)機(jī)在狀態(tài)復(fù)雜性方面可以有指數(shù)性優(yōu)勢(shì)，有興趣的讀者可參考文獻(xiàn)[1][2][3]，本文不對(duì)此進(jìn)行詳細(xì)介紹。
本報(bào)告主要集中關(guān)注與以上五個(gè)方面相關(guān)的量子計(jì)算理論的研究進(jìn)展。同時(shí)必須要指出的是，無論從哪個(gè)角度來展示量子計(jì)算優(yōu)勢(shì)，都離不開量子算法，因?yàn)橐f明量子計(jì)算有優(yōu)勢(shì)，通常需要設(shè)計(jì)一個(gè)量子算法過程去求解問題。由此可見，量子算法是量子計(jì)算的靈魂。從量子計(jì)算的發(fā)展史來看， 正是Shor算法的提出引起了學(xué)術(shù)界對(duì)量子計(jì)算的廣泛關(guān)注。我們也堅(jiān)信，未來必將由于量子算法的新突破帶來量子計(jì)算領(lǐng)域的進(jìn)一步發(fā)展。當(dāng)然，量子算法需要運(yùn)行在量子計(jì)算硬件平臺(tái)上才能發(fā)揮優(yōu)勢(shì)。因此，量子計(jì)算研究要“軟硬兼施”[4]。
圍繞“算法”和“復(fù)雜性”兩個(gè)關(guān)鍵詞，本報(bào)告將從量子查詢算法及復(fù)雜性、量子交互計(jì)算復(fù)雜性、量子機(jī)器學(xué)習(xí)、量子優(yōu)化算法、量子電路優(yōu)化與經(jīng)典模擬等五個(gè)量子計(jì)算理論的主要研究方向進(jìn)行闡述，分析與比較近年國內(nèi)外研究進(jìn)展，并對(duì)未來發(fā)展趨勢(shì)進(jìn)行展望。與本報(bào)告內(nèi)容相關(guān)的中文綜述性文獻(xiàn)可參考[5]。下面對(duì)本文涉及到的主要內(nèi)容進(jìn)行概要性介紹。
量子查詢算法及復(fù)雜性。這方面的主要研究可以概括為兩方面：（1）通過設(shè)計(jì)精巧的量子查詢算法展示量子計(jì)算優(yōu)勢(shì)，目前這方面取得了豐碩研究成果。事實(shí)上關(guān)于量子算法的研究很多時(shí)候都是從查詢復(fù)雜度性角度進(jìn)行討論。（2）分析量子查詢復(fù)雜性下界，目前已經(jīng)得到一系列求解量子查詢復(fù)雜性下界的方法，包括多項(xiàng)式方法、對(duì)手法、半正定規(guī)劃方法等。不少問題都能通過這些方法得到非平凡的查詢復(fù)雜性下界。
量子交互計(jì)算復(fù)雜性。量子交互計(jì)算復(fù)雜性理論包括量子交互式證明系統(tǒng)和量子通信復(fù)雜性。這一方面是經(jīng)典計(jì)算復(fù)雜性在量子計(jì)算時(shí)代的進(jìn)一步發(fā)展，另一方面也是滿足當(dāng)今量子信息與量子計(jì)算科學(xué)發(fā)展的需求。從現(xiàn)有技術(shù)來看，量子計(jì)算機(jī)的研制和維護(hù)成本高昂，未來量子計(jì)算或?qū)⒁栽朴?jì)算的形式給一般用戶提供服務(wù)。通過連接多個(gè)中等規(guī)模量子計(jì)算機(jī)，搭建量子網(wǎng)絡(luò)實(shí)現(xiàn)高效的量子計(jì)算；將經(jīng)典計(jì)算機(jī)或者小規(guī)模量子計(jì)算機(jī)連接到網(wǎng)絡(luò)并與之交互，獲得更強(qiáng)的量子計(jì)算能力是目前量子信息科學(xué)研究的一個(gè)主流方案。荷蘭科學(xué)家Wehner等人在《科學(xué)》期刊撰文[6] 為這個(gè)量子計(jì)算方案給出一個(gè)清晰的發(fā)展綱領(lǐng)。量子交互計(jì)算復(fù)雜性為量子網(wǎng)絡(luò)方案提供了理論框架。
量子機(jī)器學(xué)習(xí)。廣義的來說，量子機(jī)器學(xué)習(xí)的研究包括兩個(gè)方面：（1）利用量子計(jì)算技術(shù)提升經(jīng)典機(jī)器學(xué)習(xí)方法，（2）利用經(jīng)典機(jī)器學(xué)習(xí)方法解決量子力學(xué)領(lǐng)域的問題。目前這兩方面的研究都受到了很大關(guān)注。狹隘的量子機(jī)器學(xué)習(xí)僅指上面第一點(diǎn)，這也是本報(bào)告所關(guān)注的。目前，研究者對(duì)機(jī)器學(xué)習(xí)領(lǐng)域的一些主要模型和方法都進(jìn)行了量子化，即參考經(jīng)典機(jī)器學(xué)習(xí)算法建立對(duì)應(yīng)的量子算法。這些量子機(jī)器學(xué)習(xí)算法有些可以進(jìn)行嚴(yán)格的理論分析，有些則是啟發(fā)式的，依賴于實(shí)驗(yàn)分析。量子機(jī)器學(xué)習(xí)領(lǐng)域早期的發(fā)展很大程度是源于解線性方程組量子算法（HHL算法）的提出，而近期的研究工作更多集中在基于變分量子電路的算法方面。量子計(jì)算與AI的交叉研究值得進(jìn)行深入探索，不過目前一些量子機(jī)器學(xué)習(xí)方面的研究有待更嚴(yán)肅的理論分析。
量子優(yōu)化算法。與其他量子算法類似，量子優(yōu)化的關(guān)注點(diǎn)仍然是量子計(jì)算的優(yōu)勢(shì)，即如何利用量子技術(shù)來對(duì)經(jīng)典優(yōu)化方法進(jìn)行加速。目前量子優(yōu)化領(lǐng)域相對(duì)于經(jīng)典方法的加速效果主要體現(xiàn)在函數(shù)估值的查詢復(fù)雜度上。另一方面，近年陸續(xù)有小規(guī)模或?qū)Ｓ玫牧孔佑?jì)算機(jī)問世，無法嚴(yán)格理論分析優(yōu)勢(shì)的量子啟發(fā)式優(yōu)化算法得到了實(shí)驗(yàn)驗(yàn)證的可能，因此也有針對(duì)這方面的研究。
量子電路優(yōu)化與經(jīng)典模擬。目前由于量子計(jì)算機(jī)尚在實(shí)驗(yàn)研發(fā)階段，量子比特個(gè)數(shù)、可實(shí)現(xiàn)的量子電路深度和規(guī)模都非常有限，所以現(xiàn)階段的研究更應(yīng)該關(guān)注在小規(guī)模量子電路的設(shè)計(jì)與優(yōu)化上。本文將涉及淺層量子電路的優(yōu)勢(shì)、特定量子門構(gòu)成的量子電路復(fù)雜性、受物理硬件結(jié)構(gòu)限制的量子電路優(yōu)化方法、量子隨機(jī)電路的經(jīng)典模擬算法等四個(gè)方面的研究進(jìn)展。
需要指出的是，以上五方面的內(nèi)容并非完全獨(dú)立，本文只是相對(duì)集中的把它們分成五部分以便組織撰寫。首先，量子通信復(fù)雜性與量子查詢復(fù)雜性緊密相關(guān)。相比量子查詢復(fù)雜性，在量子通信復(fù)雜性模型中，我們對(duì)參與方的局部計(jì)算能力不作任何限制，因此這個(gè)模型的表達(dá)能力更強(qiáng)，計(jì)算更加復(fù)雜。其次，量子機(jī)器學(xué)習(xí)和量子優(yōu)化方向的很多算法都是從查詢復(fù)雜性方面體現(xiàn)量子優(yōu)勢(shì)，因此本質(zhì)上他們是量子查詢算法。同時(shí)，從經(jīng)典計(jì)算領(lǐng)域來看，優(yōu)化是機(jī)器學(xué)習(xí)的技術(shù)基礎(chǔ)，因此量子優(yōu)化技術(shù)自然可以用來提升機(jī)器學(xué)習(xí)問題的求解。
另外，以上幾個(gè)方面的研究內(nèi)容也并不完全與前面五個(gè)研究視角一一對(duì)應(yīng)。下面用表1把以上五方面的研究內(nèi)容和五個(gè)研究視角的關(guān)系更清晰的表示出來，其中打勾表示有關(guān)系。例如，量子機(jī)器學(xué)習(xí)既可以從時(shí)間復(fù)雜性方面進(jìn)行分析，也可以從查詢復(fù)雜性角度考慮，還可以討論樣本復(fù)雜性問題。再如量子電路優(yōu)化，如果我們關(guān)注的是基本門的個(gè)數(shù)，那本質(zhì)上體現(xiàn)的是對(duì)應(yīng)算法的時(shí)間復(fù)雜性，如果關(guān)注的是邏輯門的層數(shù)則體現(xiàn)的是電路深度復(fù)雜性。
當(dāng)前，量子技術(shù)已經(jīng)進(jìn)入到NISQ時(shí)代 (帶噪音中等規(guī)模量子技術(shù)，Noisy Intermediate-Scale Quantum Technology)[7]。如何基于現(xiàn)有的量子技術(shù)把量子計(jì)算推上實(shí)用不僅僅是技術(shù)問題，也面臨計(jì)算理論上的挑戰(zhàn)。它給理論計(jì)算機(jī)學(xué)家們提出了這樣一個(gè)科學(xué)問題“如何利用帶噪音的中等規(guī)模量子計(jì)算機(jī)實(shí)現(xiàn)高效和可靠的量子計(jì)算”。同時(shí)，量子計(jì)算領(lǐng)域的遠(yuǎn)期目標(biāo)是實(shí)現(xiàn)通用量子計(jì)算，要達(dá)此目標(biāo)量子糾錯(cuò)是至關(guān)重要且充滿挑戰(zhàn)的一步。目前在量子糾錯(cuò)的理論方面已經(jīng)取得了豐富成果。由于量子糾錯(cuò)的重要性和內(nèi)容的豐富性，需要一篇專門的文章才足以承載，因此本文不對(duì)此進(jìn)行介紹，但我們應(yīng)認(rèn)識(shí)到其重要性所在。
[1] A Ambainis and R Freivalds. 1-way quantum finite automata: strengths, weaknesses and generalizations [C]. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, Palo Alto, 1998. 332–341.
[2] A Ambainis and N Nahimovs. Improved constructions of quantum automata. Theor Comput Sci, 2009, 410: 1916–1922.
[3] D Qiu, L Li, P Mateus and A Sernadas. Exponentially more concise quantum recognition of non-RMM regular languages[J], Journal of Computer and System Sciences. 2015, 81: 359–375.
[4] 李綠周，量子計(jì)算研究要“軟硬兼施”，《中國科學(xué)報(bào)》 (2020-05-07 第3版 信息技術(shù))，http://www.1061937.com/teamwork/showPostMessage.html?id=7871
[5] 孫曉明, 量子計(jì)算若干前沿問題綜述. 中國科學(xué): 信息科學(xué), 2016, 46: 982.
[6] S Wehner, D Elkouss, and R Hanson. Quantum internet: A vision for the road ahead [J]. Science, 2018. 362(6412):eaam9288.
[7] J Preskill. Quantum Computing in the NISQ era and beyond [J]. Quantum, 2018. 2:79.
附件
