盡管對于絕大多數(shù)人來說，“量子計算”是一個屬于科幻世界的遙遠詞匯，但實際上它已經(jīng)走過了近四十年的歷史。在這四十年里，量子計算及其算法從無到有，從理論概念逐漸變成了現(xiàn)實。我們從量子算法發(fā)展的角度來看，大體上可以分成四個階段。

理論提出及探索階段(1980-1994)

早在1981年，電子計算機還是非常新鮮的事物，個人電腦尚未進入家庭，就已經(jīng)有科學(xué)家提出了“量子計算機”的概念。曾經(jīng)參與過美國原子彈研制的“曼哈頓計劃”諾貝爾獎得主，著名科學(xué)家理查德·費曼（Richard Feynman）在麻省理工大學(xué)舉辦的計算物理第一屆會議上，發(fā)表了論文《用計算機模擬物理學(xué)》，論文里費曼首次提出了“量子計算機的概念”，指出使用經(jīng)典計算機難以有效模擬量子系統(tǒng)的演化，而使用量子計算機能夠?qū)α孔酉到y(tǒng)的演化進行有效模擬。

1985年,英國牛津大學(xué)教授大衛(wèi)·德伊奇David Deutsch首次提出了量子圖靈機模型,并且設(shè)計了第一個量子算法Deutsch算法。1992年，德伊奇又和英國劍橋大學(xué)教授理查德·喬薩Richard Jozsa對早期Deutsch算法進行了拓展，給出了它在n個量子比特下的算法。這是人類歷史上首個利用量子特性設(shè)計出來，專門針對量子計算機的算法，開創(chuàng)了量子算法的先河，為后面的Shor算法、Grover算法等量子算法的設(shè)計提供了思路。同時，Deutsch-Jozsa算法還說明了比起經(jīng)典計算機，量子計算機能夠更快速、更有效地解決一些特定的問題，顯示出了量子計算機巨大的潛力。

但是，當(dāng)時的技術(shù)水平和工程能力還十分低下，且理論物理學(xué)家對于量子的特性也尚未完全了解，這些量子算法還停留在紙面設(shè)想階段。

通用量子算法發(fā)展階段(1994-2009)

從20世紀(jì)90年代開始，很多大學(xué)和企業(yè)已經(jīng)在開始探索不同物理體系中實現(xiàn)量子計算的實驗驗證，但是這個時代大家都只能實現(xiàn)單比特和兩比特的量子計算。另一方面，量子計算的算法得到很大發(fā)展，以Shor算法為代表的三大通用量子計算的算法陸續(xù)涌現(xiàn)，標(biāo)志著這一時代研究的焦點是研發(fā)通用量子算法。

1994年，美國貝爾實驗室的彼得·肖爾（Peter Shor）?提出了Shor算法，在算法界引起了轟動，它從理論上展示了量子計算機能夠把質(zhì)因數(shù)分解問題的求解，從指數(shù)時間降到多項式時間。目前通用的計算機加密方案——RSA加密，利用的就是質(zhì)因數(shù)分解的時間復(fù)雜性：用目前最快的算法對一個大整數(shù)進行質(zhì)因數(shù)分解，需要花費的時間都在數(shù)年以上。但通過Shor算法，一臺量子比特數(shù)足夠多的量子計算機，能夠“輕易”破解RSA模型下的任何大整數(shù)。彼得·肖爾因此榮獲1999 年理論計算機科學(xué)的最高獎——哥德爾獎。

1996年，Lov Grover提出了Grover量子搜索算法，該算法被公認為繼Shor算法后的第二大算法，它解決的是無序數(shù)據(jù)庫搜索問題，也是第一個被完整地實驗實現(xiàn)的量子算法。時至今日，Grover算法仍是不同量子計算平臺的基準(zhǔn)實驗之一。?

2009年，MIT三位科學(xué)家阿朗·哈羅（Aram Harrow）、阿維那坦·哈西迪姆（Avinatan Hassidim）和賽斯·勞埃德（Seth Lloyd）聯(lián)合開發(fā)了HHL算法。用于求解線性方程組，比起經(jīng)典算法有指數(shù)加速的效果。線性方程組是很多科學(xué)和工程領(lǐng)域的核心，所以HHL算法可在機器學(xué)習(xí)、數(shù)據(jù)擬合等多種場景中展現(xiàn)出量子計算的優(yōu)勢。

專用量子算法繁榮階段(2009-2018)

從2009年開始，以谷歌、IBM為代表的一些企業(yè)，開始把規(guī)?；孔佑嬎銠C的工程化作為主要的發(fā)展方向。他們從兩個比特開始，后來逐漸做到幾十量子比特的規(guī)模。隨著研究的深入，大家意識到實現(xiàn)大規(guī)模圖靈完備的通用量子計算機是一個超出目前工程化水平太多的技術(shù)。在規(guī)?；€沒有達到足夠大的情況下，很多科學(xué)家轉(zhuǎn)而研究非圖靈完備的專用量子計算架構(gòu)。此類專用量子架構(gòu)舍棄了邏輯門，但比起通用量子計算更加容易實用化，可以在一些專業(yè)領(lǐng)域，解決某種特定類型的問題。

在此過程中，很多專用的量子算法出現(xiàn)了。這其中包括一些優(yōu)化的算法：如變分量子特征值求解算法（Variational Quantum Eigensolver，VQE）、量子近似優(yōu)化算法（Quantum Approximation Optimization Algorithm，QAOA）等；還有一些采樣的算法，包括玻色采樣（Boson Sampling）、量子隨機游走（Quantum Walk）等算法，此外還有美國斯坦福大學(xué)提出的CIM相干伊辛機（Coherent Ising Machine）、以D-Wave公司為代表的量子退火算法（Quantum annealing）等。

量子AI探索階段(2018至今)

基于量子的疊加和糾纏等原理，使得量子算法非常適于解決人工智能和機器學(xué)習(xí)中核心的優(yōu)化（Optimization）過程類問題，所以從2018年開始，以谷歌為代表的企業(yè)紛紛開始投入量子人工智能，特別是與深度學(xué)習(xí)相結(jié)合的領(lǐng)域。具有代表性的成果包括Google公司在2020年提出的Tensorflow Quantum（TFQ）框架。TFQ是一種量子-經(jīng)典混合機器學(xué)習(xí)的開放源代碼庫，允許研發(fā)人員在設(shè)計、訓(xùn)練和測試混合量子經(jīng)典模型時，可以模擬量子處理器的算法，在最終聯(lián)機時，還可以在真實量子處理器上運行這些模型的量子部分。TFQ可用于量子分類、量子控制和量子近似優(yōu)化等功能。

此外量子人工智能的研究范疇還包括量子卷積網(wǎng)絡(luò)QCNN、量子自然語言處理QNLP、量子生成模型QGM等。包括斯坦福大學(xué)等在內(nèi)的單位還在進行量子神經(jīng)元（CIM Quantum Neuron）方向的研究。預(yù)計在未來3到5年中，將會有更多的企業(yè)、資源投入到量子人工智能方向的算法研究，成果不斷涌現(xiàn)，將量子AI推向一個新的高潮。

文：袁為?田靜秀?

編輯：慕一