我們正在經(jīng)歷一場智能革命，而這場智能革命建立在算法的基礎(chǔ)上。無論是智慧城市、智能制造、智慧醫(yī)療等宏大愿景，還是自動駕駛、智能機器、虛擬現(xiàn)實等前沿應(yīng)用，抑或是智能購物、智慧出行、智能娛樂等生活日常，“智能”的實現(xiàn)都離不開算法。可以說，我們生活在一個算法無所不在的時代。
古代算法思想及其發(fā)展
“算法”一詞的英文“algorithm”源于波斯數(shù)學(xué)家花拉子密（Al Khwarizmi）名字的拉丁化。在數(shù)學(xué)和計算機科學(xué)中，算法是有明確定義、有限步驟且計算機可執(zhí)行的，通常用于計算、數(shù)據(jù)處理和自動推理的一組指令序列。算法作為一個復(fù)雜的體系，是數(shù)學(xué)、邏輯學(xué)和計算機科學(xué)的集合。盡管第一臺計算機誕生距今不過70多年，但是算法思想源遠(yuǎn)流長。
● 算法思想的數(shù)學(xué)源頭
數(shù)學(xué)起源于人類早期的生產(chǎn)活動對計數(shù)、天文、度量甚至貿(mào)易的需要。這些需要可以簡單概括為數(shù)學(xué)對結(jié)構(gòu)、空間和時間的研究。數(shù)學(xué)對結(jié)構(gòu)的研究發(fā)展出算術(shù)和代數(shù)，對空間的研究發(fā)展出幾何，對時間的研究發(fā)展出函數(shù)。人類關(guān)于數(shù)字和算術(shù)的概念從史前時代就已存在，如蘇美爾人用黏土保留數(shù)字信息和我國古人用結(jié)繩計數(shù)都是人類對計算的早期實踐。公元前7世紀(jì)的古希臘數(shù)學(xué)家及天文學(xué)家泰勒斯（Thales of Miletus）被認(rèn)為是最早提出幾何定理的人。公元前4世紀(jì)，古希臘數(shù)學(xué)家歐幾里得（Euclid）所著的《幾何原本》是歷史上第一部系統(tǒng)化的數(shù)學(xué)理論典籍，而求最大公約數(shù)的歐幾里得算法是人類歷史上第一個算法。12世紀(jì)至13世紀(jì)，阿拉伯?dāng)?shù)學(xué)中的代數(shù)思想，尤其是數(shù)字“零”的概念隨著十字軍東征傳入歐洲?；ɡ用芩摹洞鷶?shù)學(xué)》是第一本解決一次方程及一元二次方程的系統(tǒng)著作，他也因此被稱為代數(shù)的開創(chuàng)者，他的著作《印度數(shù)字計算》在12世紀(jì)將十進(jìn)制和算法思想傳入歐洲。函數(shù)的概念最早出現(xiàn)在蘇格蘭數(shù)學(xué)家及天文學(xué)家格雷戈里（James Gregory）發(fā)表于1667年的論文《論圓和雙曲線的求積》中。1673年，德國數(shù)學(xué)家萊布尼茨（Gottfried Wilhelm Leibniz）在其手稿里使用了“函數(shù)”這一概念，后來又引進(jìn)“常量”“變量”和“參變量”的概念。函數(shù)概念的引入使人們可以從數(shù)量上描述運動，伽利略的落體運動定律、牛頓的萬有引力定律和愛因斯坦的質(zhì)能轉(zhuǎn)換公式等都是用函數(shù)概念表達(dá)的。
中國同樣有悠久的數(shù)學(xué)傳統(tǒng)。數(shù)學(xué)在中國歷史上稱為“算學(xué)”，起源于仰韶文化，距今已有5 000多年的歷史。在距今3 000年前的周朝，“數(shù)”是六藝之一。在春秋時代，十進(jìn)位制的籌算已經(jīng)普及。算學(xué)的文獻(xiàn)記載最早見于《周髀算經(jīng)》?！吨荀滤憬?jīng)》是中國流傳至今最早的天文學(xué)和數(shù)學(xué)著作，其中記載了周公曾問商高如何測量天地高遠(yuǎn)，這是勾股定理最早的文字記錄，比古希臘數(shù)學(xué)家畢達(dá)哥拉斯（Pythagoras）的證明早了500多年。中國古代數(shù)學(xué)把利用算籌進(jìn)行計算的算法稱為“術(shù)”，中國古代數(shù)學(xué)的成就多是用術(shù)來表述的，如成書于東漢前期的《九章算術(shù)》中的方程術(shù)、正負(fù)術(shù)、今有術(shù)，三國時期劉徽的割圓術(shù)，南宋數(shù)學(xué)家秦九韶《數(shù)術(shù)九章》中的大衍求一術(shù)等。尤其是大衍求一術(shù)，已經(jīng)是相當(dāng)復(fù)雜的算法，具備了現(xiàn)代算法的基本特征。
● 算法思想的邏輯學(xué)脈絡(luò)
邏輯學(xué)是一門關(guān)于推理或論證的學(xué)問，主要研究推理的有效性和正確性問題。邏輯學(xué)分別發(fā)源于古希臘、中國古代和古印度，其中古希臘邏輯最終發(fā)展成當(dāng)前的國際主流邏輯。古希臘邏輯學(xué)大約誕生于公元前350年，古希臘哲學(xué)家亞里士多德（Aristotle）開創(chuàng)了以“三段論”為核心的詞項邏輯，這是人類歷史上第一個演繹邏輯體系，他關(guān)于邏輯的6篇論文被追隨者匯編成《工具論》，對西方思想史產(chǎn)生了深遠(yuǎn)影響。公元前3世紀(jì)早期，古希臘哲學(xué)家芝諾（Zeno of Citium）創(chuàng)立斯多葛學(xué)派，發(fā)展了命題邏輯，但是與亞里士多德邏輯的主導(dǎo)地位相比影響較小。
1543年，波蘭數(shù)學(xué)家及天文學(xué)家哥白尼（Nicolas Copernicus）的《天體運行論》和比利時醫(yī)生及解剖學(xué)家維薩留斯（Andreas Vesalius）的《人體結(jié)構(gòu)》在同一年出版，標(biāo)志著現(xiàn)代科學(xué)的誕生。自然科學(xué)需要根據(jù)個別現(xiàn)象概括出一般性結(jié)論，以解釋現(xiàn)象間的因果關(guān)系，但亞里士多德邏輯無法處理自然科學(xué)研究中的因果問題。1620年，英國科學(xué)家及哲學(xué)家培根（Francis Bacon）提出以觀察和實驗為基礎(chǔ)的科學(xué)認(rèn)識理論，開創(chuàng)了歸納邏輯。1843年，英國哲學(xué)家穆勒（John S. Mill）在培根歸納法基礎(chǔ)上提出判斷因果聯(lián)系的5種邏輯方法。歸納邏輯在17世紀(jì)歐洲科學(xué)革命中起到了不可估量的作用。1666年，萊布尼茨在《論組合術(shù)》中闡述了以符號運算表述推理過程的思想，開創(chuàng)了符號邏輯和數(shù)理邏輯的研究。符號邏輯是現(xiàn)代邏輯的基礎(chǔ)，包括命題演算和謂詞演算；數(shù)理邏輯是符號邏輯在數(shù)學(xué)中的應(yīng)用。1847年，英國數(shù)學(xué)家布爾（George Boole）提出的布爾邏輯就是一個命題演算系統(tǒng)。1928年，德國數(shù)學(xué)家希爾伯特（David Hilbert）和阿克曼（Wilhelm Ackermann）在《理論邏輯原理》中提出了現(xiàn)在人們常用的命題演算系統(tǒng)。1879年，德國邏輯學(xué)家費雷格通過引入量詞，將命題演算拓展成了謂詞演算系統(tǒng)，最終完成了符號邏輯體系的構(gòu)建。
人工智能時代的算法
1936年，英國數(shù)學(xué)家及計算機科學(xué)家圖靈（Alan Turing）提出被稱為“圖靈機”的計算數(shù)學(xué)模型，其構(gòu)想是將人的計算行為抽象為數(shù)學(xué)邏輯機器。圖靈機是現(xiàn)代通用計算機的理論基礎(chǔ)，如今所有通用計算機都是圖靈機的一種實現(xiàn)。1943年，美國數(shù)學(xué)家香農(nóng)（Claude E. Shannon）和圖靈在貝爾實驗室探討了“人工智能”的可能性。1950年，圖靈在一篇論文中預(yù)言了創(chuàng)造出具有真正智能的機器的可能性，并提出了判斷機器是否具有智能的思想實驗——圖靈測試。1956年，明斯基（Marvin Minsky）、麥卡錫（John McCarthy）、香農(nóng)等13位科學(xué)家在美國達(dá)特茅斯學(xué)院召開會議，標(biāo)志著人工智能學(xué)科的誕生，算法也由此進(jìn)入人工智能時代。
● 機器學(xué)習(xí)
機器學(xué)習(xí)是人工智能和計算機科學(xué)的重要分支，是基于樣本數(shù)據(jù)構(gòu)建模型并利用模型在沒有明確編程的情況下做出預(yù)測或決策的一類算法。監(jiān)督學(xué)習(xí)、無監(jiān)督和強化學(xué)習(xí)是機器學(xué)習(xí)的基本方法。
監(jiān)督學(xué)習(xí)使用人工標(biāo)記的訓(xùn)練樣本將已有知識應(yīng)用于新數(shù)據(jù)，以預(yù)測未來事件。1936年，英國數(shù)學(xué)家費希爾（Ronald Fisher）提出的線性判別分析是最早的監(jiān)督學(xué)習(xí)算法。20世紀(jì)50年代，基于貝葉斯決策理論的貝葉斯分類器開始被用于分類問題。1958年，美國認(rèn)知心理學(xué)家羅森布拉特（Frank Rosenblatt）發(fā)明感知器算法，它被認(rèn)為是人工神經(jīng)網(wǎng)絡(luò)的前身。1967年，美國信息理論家科弗（Thomas Cover）和計算機科學(xué)家哈特（Peter Hart）提出基于模板匹配思想的K-最近鄰算法。20世紀(jì)八九十年代，決策樹和神經(jīng)網(wǎng)絡(luò)算法開始興起。1995年，兩種重要算法——支持向量機和AdaBoost誕生。支持向量機是處理線性分類和非線性分類問題的主要方法，而AdaBoost可以將許多其他類型的算法集成起來使用以達(dá)到最佳性能。1995年至1997年，德國計算機科學(xué)家霍赫賴特（Sepp Hochreiter）和施米德胡貝（Juergen Schmidhuber）提出長短期記憶算法，可以部分處理梯度消失問題。2013年，長短期記憶算法與深度循環(huán)神經(jīng)網(wǎng)絡(luò)結(jié)合成功應(yīng)用于語音識別。2001年，美國統(tǒng)計學(xué)家布賴曼（Leo Breiman）提出優(yōu)化的隨機森林算法。隨機森林是一個用隨機方式建立的包含多個決策樹的分類器，對多數(shù)據(jù)集和高維數(shù)據(jù)的處理有很大優(yōu)勢。監(jiān)督學(xué)習(xí)的常見應(yīng)用場景包括評估信用分?jǐn)?shù)、手寫識別、語音識別、信息檢索、財務(wù)分析、偵測垃圾郵件等。
無監(jiān)督學(xué)習(xí)是基于統(tǒng)計的學(xué)習(xí)方法，通過對未知數(shù)據(jù)進(jìn)行分析來發(fā)現(xiàn)數(shù)據(jù)隱藏特征。無監(jiān)督學(xué)習(xí)包括聚類和數(shù)據(jù)降維兩種主要算法類型。1963年，美國空軍研究員沃德（Joe Ward）根據(jù)方差分析提出了最早的聚類算法——層次聚類算法。1967年，美國數(shù)學(xué)家麥奎因（James MacQueen）提出的k均值算法是聚類算法中知名度最高的算法，在此基礎(chǔ)上出現(xiàn)了大量的改進(jìn)算法和成功應(yīng)用。1977年，美國統(tǒng)計學(xué)家登普斯特（Arthur Dempster）提出最大期望算法，被用于聚類問題和極大似然估計問題。1995年，美國辛辛那提大學(xué)教授程（Yizong Cheng）提出可用于計算機視覺和圖像處理的均值漂移算法。2000年，美國計算機科學(xué)家史建波（Jianbo Shi）推廣了譜聚類算法，可以將聚類問題轉(zhuǎn)化為圖的最優(yōu)切割問題。最早的數(shù)據(jù)降維算法是1901年英國數(shù)學(xué)家及生物統(tǒng)計學(xué)家皮爾遜（Karl Pearson）提出的主成分分析法，比第一臺真正的計算機的誕生早了40多年。然而，在此后的近100年里數(shù)據(jù)降維算法在機器學(xué)習(xí)領(lǐng)域沒有出現(xiàn)重量級成果。1998年，德國計算機科學(xué)家舍爾科普夫（Bernhard Sch?lkopf）提出基于核方法的核主成分分析算法，可以實現(xiàn)高維數(shù)據(jù)的非線性降維。2000年以后，流形學(xué)習(xí)開始成為熱點，它的主要思想是將高維的數(shù)據(jù)映射到低維，使該低維的數(shù)據(jù)能夠反映原高維數(shù)據(jù)的某些本質(zhì)結(jié)構(gòu)特征?；诹餍袑W(xué)習(xí)出現(xiàn)了局部線性嵌入、拉普拉斯特征映射、局部保持投影等距映射等新算法。2008年出現(xiàn)的t-分布式隨機鄰居嵌入算法是降維算法中最年輕的成員。無監(jiān)督學(xué)習(xí)的常見應(yīng)用場景包括反洗錢、客戶分組、廣告推薦、銷售趨勢預(yù)測等。
強化學(xué)習(xí)源于心理學(xué)中的行為主義理論，強調(diào)智能體在獎勵或懲罰的環(huán)境刺激下如何做出能取得最大化預(yù)期利益的行動，也就是說，讓智能體在環(huán)境中自我學(xué)習(xí)。早在1954年，明斯基就提出了“強化學(xué)習(xí)”的概念和術(shù)語。1965年，美國普渡大學(xué)教授傅京孫（King-Sun Fu）在研究控制論時提出“智能控制”的概念，明確了“試錯”作為強化學(xué)習(xí)的核心機制。1957年，美國應(yīng)用數(shù)學(xué)家貝爾曼（Richard Bellman）為了求解最優(yōu)控制問題的馬爾可夫決策過程提出了動態(tài)規(guī)劃法，這一方法采用了類似強化學(xué)習(xí)的試錯迭代求解機制。最早的強化學(xué)習(xí)算法是1988年加拿大計算機科學(xué)家薩頓（Richard Sutton）提出的時序差分學(xué)習(xí)，它不需要獲知環(huán)境的全部信息就可以直接從實際經(jīng)驗來獲取信息，同時不需要完整的收益反饋信息就可以實時更新決策。1989年，英國計算機科學(xué)家沃特金斯（Chris Watkins）提出的Q學(xué)習(xí)進(jìn)一步拓展了強化學(xué)習(xí)的應(yīng)用，使得強化學(xué)習(xí)不再依賴于問題模型，Q學(xué)習(xí)也因此成為最廣泛使用的強化學(xué)習(xí)方法之一。此后近20年的時間里，強化學(xué)習(xí)被監(jiān)督學(xué)習(xí)的光芒所遮掩而發(fā)展緩慢。2010年以后，強化學(xué)習(xí)結(jié)合神經(jīng)網(wǎng)絡(luò)發(fā)展出深度強化學(xué)習(xí)算法，強化學(xué)習(xí)由此迎來大發(fā)展時期。2013年，谷歌公司旗下的深度思維公司（DeepMind）發(fā)表了利用強化學(xué)習(xí)玩雅達(dá)利（Atari）游戲的論文。2015年，深度思維公司開發(fā)的AlphaGo程序擊敗了圍棋二段選手樊麾，成為第一個無須讓子即可以擊敗圍棋職業(yè)棋手的計算機圍棋程序。2016年，AlphaGo在一場五番棋比賽中以4:1擊敗頂尖圍棋職業(yè)棋手李世石。強化學(xué)習(xí)的常見應(yīng)用場景包括無人駕駛、機器翻譯、醫(yī)療保健、新聞定制、廣告營銷、機器人控制等。
● 深度學(xué)習(xí)
深度學(xué)習(xí)是機器學(xué)習(xí)的一個分支，是一種模擬大腦神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)對數(shù)據(jù)進(jìn)行表征學(xué)習(xí)的方法。深度學(xué)習(xí)源于對人腦工作機制的研究。獲得1981年諾貝爾生理學(xué)或醫(yī)學(xué)獎的美國神經(jīng)生理學(xué)家休伯爾（David Hubel）和維澤爾（Torsten Wiesel）發(fā)現(xiàn)人的視覺系統(tǒng)的信息處理是分級的，人類對高層特征的感知基于低層特征的組合。例如，對人臉的識別經(jīng)過瞳孔攝入像素（形狀判斷）抽象出人臉概念——識別為人臉的過程，從低層到高層的特征表達(dá)越來越抽象和概念化。這一發(fā)現(xiàn)意味著大腦是一個深度架構(gòu)，認(rèn)知過程也是深度的，而深度學(xué)習(xí)恰恰就是通過組合低層特征形成更加抽象的高層特征。深度學(xué)習(xí)的發(fā)展可以分為感知器、神經(jīng)網(wǎng)絡(luò)和深度學(xué)習(xí)等3個階段。
1943年，美國心理學(xué)家麥卡洛克（Warren S. McCulloch）和數(shù)理邏輯學(xué)家皮茨（Walter Pitts）提出人工神經(jīng)網(wǎng)絡(luò)的概念，并構(gòu)建了人工神經(jīng)元的數(shù)學(xué)模型，即MCP模型，從而開創(chuàng)了人工神經(jīng)網(wǎng)絡(luò)研究的時代。1949年，加拿大心理學(xué)家赫布（Donald Hebb）描述了突觸可塑性的基本原理，從神經(jīng)科學(xué)理論上解釋了學(xué)習(xí)過程中大腦神經(jīng)細(xì)胞所發(fā)生的變化。赫布理論是人工神經(jīng)網(wǎng)絡(luò)的生物學(xué)基礎(chǔ)。1958年，羅森布拉特在康奈爾航空實驗室發(fā)明感知器算法，這是世界上第一個具有完整算法描述的神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法。感知器算法是簡單配置的單層神經(jīng)網(wǎng)絡(luò)，可以區(qū)分三角形等基本形狀。但是，受限于計算機硬件，感知器算法在當(dāng)時無法被廣泛應(yīng)用。1969年，明斯基和佩珀特（Seymour Papert）證明感知器不能解決簡單的異或（XOR）等線性不可分問題，感知器研究隨之在20世紀(jì)70年代陷入低谷。
1959年，休伯爾和維澤爾在研究貓的視覺神經(jīng)系統(tǒng)時發(fā)現(xiàn)，在大腦的初級視覺皮層中存在兩種細(xì)胞：簡單細(xì)胞和復(fù)雜細(xì)胞，其中，簡單細(xì)胞感知光照信息，復(fù)雜細(xì)胞感知運動信息。受此啟發(fā)，1980年日本計算機科學(xué)家福島邦彥（Kunihiko Fukushima）提出了一個網(wǎng)絡(luò)模型——“神經(jīng)認(rèn)知機”（Neocognitron）。這種網(wǎng)絡(luò)分成多層，每層由一種神經(jīng)元組成。在網(wǎng)絡(luò)內(nèi)部，兩種神經(jīng)元交替出現(xiàn)，分別用來提取圖形信息和組合圖形信息。這兩種神經(jīng)元后來分別演化成卷積層（Convolution Layer）和提取層（Pooling Layer）。然而，這個網(wǎng)絡(luò)的神經(jīng)元都是人工設(shè)計的而不能根據(jù)計算結(jié)果自動調(diào)整，所以只能識別少量簡單數(shù)字而不具備學(xué)習(xí)能力。
1982年，美國物理學(xué)家霍普菲爾德（John J. Hopfield）基于統(tǒng)計物理提出了有少量記憶能力的霍普菲爾德神經(jīng)網(wǎng)絡(luò)模型，開創(chuàng)性地論證了按照赫布法則設(shè)計權(quán)重的神經(jīng)網(wǎng)絡(luò)穩(wěn)定性問題。同年，芬蘭計算機科學(xué)家科霍寧（Teuvo Kohonen）通過模擬大腦神經(jīng)元的信號處理機制，提出了自組織映射網(wǎng)絡(luò)，被用于數(shù)據(jù)分析和數(shù)據(jù)探索，其第一個應(yīng)用領(lǐng)域是語音分析?？苹魧幍年P(guān)鍵發(fā)明是引入了一個系統(tǒng)模型，包含一個實現(xiàn)贏家通吃功能的競爭性神經(jīng)網(wǎng)絡(luò)和一個實現(xiàn)可塑性控制的子系統(tǒng)。1987年，美國科學(xué)家格羅斯伯格（Stephen Grossberg）和卡彭特（Gail Carpenter）提出了自適應(yīng)共振理論網(wǎng)絡(luò)，通過讓已知信息和未知信息發(fā)生“共振”，從已知信息推測未知信息來實現(xiàn)類比學(xué)習(xí)。然而，這些神經(jīng)網(wǎng)絡(luò)存在學(xué)習(xí)效率不高、需要不斷優(yōu)化設(shè)計、網(wǎng)絡(luò)記憶容量小等不足，實際應(yīng)用范圍有限。
1986年，美國心理學(xué)家魯姆哈特（David Rumelhart）、計算機科學(xué)家威廉姆斯（Ronald Williams）和加拿大認(rèn)知心理學(xué)家及計算機科學(xué)家欣頓（Geoffrey Hinton）共同提出反向傳播算法（BP算法）。BP算法通過梯度的鏈?zhǔn)椒▌t使輸出結(jié)果和真實值之間的差異反饋到每一層的權(quán)重中，從而讓每一層函數(shù)都能像感知機那樣得到訓(xùn)練。BP算法階段性解決了神經(jīng)網(wǎng)絡(luò)自適應(yīng)、自主學(xué)習(xí)的難題。1989年，貝爾實驗室的法國計算機科學(xué)家楊立昆（Yann LeCun）第一次成功實現(xiàn)了神經(jīng)網(wǎng)絡(luò)的實踐應(yīng)用。他將卷積神經(jīng)網(wǎng)絡(luò)與BP算法結(jié)合，提出LeNet網(wǎng)絡(luò)。20世紀(jì)90年代，美國郵政署將LeNet網(wǎng)絡(luò)用于自動讀取信封上的郵政編碼。然而，基于BP算法的神經(jīng)網(wǎng)絡(luò)僅能求解局部最優(yōu)，而且這種情況隨著網(wǎng)絡(luò)層數(shù)的增加越來越嚴(yán)重，這一問題制約了神經(jīng)網(wǎng)絡(luò)的發(fā)展。
2006年，欣頓提出深度學(xué)習(xí)算法，通過無監(jiān)督學(xué)習(xí)和逐層預(yù)訓(xùn)練的方式有效降低了訓(xùn)練難度，從而解決了BP神經(jīng)網(wǎng)絡(luò)難以達(dá)到全局最優(yōu)的問題。2012年，欣頓的研究小組采用深度學(xué)習(xí)贏得了ImageNet圖像分類比賽的冠軍，準(zhǔn)確率超出第二名10%以上，在計算機視覺領(lǐng)域產(chǎn)生極大震動，引發(fā)了深度學(xué)習(xí)的熱潮。2013年，《麻省理工科技評論》將深度學(xué)習(xí)列為年度世界十大技術(shù)突破之首。如今，深度學(xué)習(xí)已經(jīng)被廣泛用于搜索引擎、語音識別、自動機器翻譯、自然語言處理、自動駕駛、人臉識別等領(lǐng)域，是人工智能最熱門的研究方向之一。
量子時代算法的發(fā)展
根據(jù)摩爾定律，計算機芯片的性能每18個月翻1番。然而，隨著摩爾定律逼近極限，經(jīng)典計算的算力增長即將遭遇瓶頸。量子計算是利用量子態(tài)的相干性、疊加性、糾纏性等量子力學(xué)特性進(jìn)行信息運算、保存和處理操作的新型計算模式。量子計算可以突破經(jīng)典計算機的算力極限，被認(rèn)為是未來30年最有可能改變世界的顛覆性技術(shù)之一。
● 量子計算理論
1979年，美國阿貢國家實驗室物理學(xué)家貝尼奧夫（Paul Benioff）提出了第一個量子計算機模型。1980年，蘇聯(lián)數(shù)學(xué)家馬寧（Yuri Manin）在其著作《可計算與不可計算》中同樣闡述了量子計算的概念。1981年，貝尼奧夫和美國物理學(xué)家費恩曼（Richard Faynman）在麻省理工學(xué)院舉行的第一屆計算物理會議上就量子計算發(fā)表演講。貝尼奧夫表示計算機可以在量子力學(xué)定律下運行，費恩曼表示使用經(jīng)典計算機難以有效模擬量子系統(tǒng)的演化，并提出了量子計算機的基本模型。貝尼奧夫、馬寧和費曼奠定了量子計算的理論基礎(chǔ)。
1985年，英國牛津大學(xué)教授多伊奇（David Deutsch）首次提出了量子圖靈機模型，并設(shè)計了第一個量子算法Deustch算法。然而，Deustch算法沒有確定性，其成功的概率僅有50%。1992年，多伊奇和英國劍橋大學(xué)教授喬薩（Richard Jozsa）在早期Deustch算法基礎(chǔ)上提出了有確定性的Deutsch-Jozsa算法，并將其推廣到n個量子比特的Deutsch問題。Deutsch-Jozsa算法首次實現(xiàn)了對經(jīng)典算法的指數(shù)級加速，奠定了量子算法的基本思想。然而，限于當(dāng)時的理論和技術(shù)水平，此時量子算法還停留在紙面設(shè)想階段。
● 量子計算核心算法
Shor算法、Grover算法和以HHL算法為代表的對偶量子算法是量子計算的三大核心算法。1994年，貝爾實驗室的美國數(shù)學(xué)家肖爾（Peter Shor）基于量子傅里葉變換提出了針對整數(shù)分解問題的大數(shù)質(zhì)因子分解算法（又稱為Shor算法）。Shor算法從理論上展示了量子計算機能夠把質(zhì)因數(shù)分解問題的求解從指數(shù)時間降到多項式時間，可用于破解目前通用的計算機加密方案——RSA加密算法。假如超級計算機破解一個2048位的RSA密鑰需要數(shù)十億年，那么使用Shor算法的量子計算機僅需要幾分鐘。這意味著依賴RSA密鑰機制的銀行、網(wǎng)絡(luò)和電子商務(wù)系統(tǒng)在理論上不再安全。然而，Shor算法在量子計算機上的實驗實現(xiàn)一直是國際公認(rèn)難題。2008年，中國科技大學(xué)教授潘建偉的團隊與英國牛津大學(xué)合作，首次在光量子計算機上實現(xiàn)了Shor量子分解算法，標(biāo)志著我國光學(xué)量子計算研究達(dá)到了國際領(lǐng)先水平。
1996年，貝爾實驗室的美國計算機科學(xué)家格羅弗（Lov K. Grover）基于量子黑盒加速工具提出了針對亂序數(shù)據(jù)庫的量子搜索算法（又稱為Grover算法）。Grover算法從本質(zhì)上解決了函數(shù)求逆的任務(wù)，使無序數(shù)據(jù)庫中“大海撈針”成為可能，其在密碼學(xué)上的應(yīng)用可以加速對稱密鑰算法的破解。然而，原始的Grover算法只能以一定概率輸出正確結(jié)果，在一些特殊情況下輸出錯誤結(jié)果的概率較大。2001年，清華大學(xué)教授龍魯桂利用相位匹配的技巧將Grover算法的成功概率提高到100%，即龍算法。
Shor算法和Grover算法提出之后，量子算法研究進(jìn)展緩慢。2003年，肖爾發(fā)出著名的“肖爾之問”，即為什么難以發(fā)現(xiàn)更多的量子算法。肖爾對這一問題的解釋是，量子計算機的運行模式與經(jīng)典計算機不同，以至于經(jīng)典算法中的構(gòu)造設(shè)計技巧和直覺在量子計算過程中不再成立。
2002年，龍魯桂提出酉算符線性疊加的對偶量子算法。酉算符是泛函分析中定義在希爾伯特空間上的有界線性算符，Shor算法和Grover算法都是通過酉算符對信息進(jìn)行處理。由于酉算符只允許乘除運算，經(jīng)典計算中的許多技巧不能用于量子計算。對偶量子算法通過引入輔助比特以實現(xiàn)非酉操作，這使酉算符的加減乘除四則運算成為可能，從而解決了經(jīng)典算法轉(zhuǎn)化為量子算法的問題。2009年，美國麻省理工學(xué)院的哈羅（Aram W. Harrow）、哈希迪姆（Avinatan Hassidim）和勞埃德（Seth Lloyd）基于酉算符線性疊加提出可求解線性方程組的HHL算法。求解線性方程組是很多科學(xué)和工程問題的核心，HHL算法相對于經(jīng)典計算有指數(shù)加速的效果，因此在機器學(xué)習(xí)、數(shù)據(jù)擬合等多種場景中展示出巨大優(yōu)勢。
● 量子人工智能算法
量子疊加和量子糾纏等量子力學(xué)特性使量子算法非常適于解決人工智能和機器學(xué)習(xí)研究中核心的最優(yōu)化問題。所謂“最優(yōu)化”是指在給定預(yù)期結(jié)果和約束條件的情況下，從一組可能選項中找到問題最優(yōu)解的過程。最優(yōu)化問題是應(yīng)用數(shù)學(xué)和計算機科學(xué)領(lǐng)域的重要基礎(chǔ)研究之一，其理論與方法廣泛用于工業(yè)生產(chǎn)、工程設(shè)計與管理、交通運輸、經(jīng)濟決策、市場管理等關(guān)乎國計民生的重要領(lǐng)域。1995年，美國計算機科學(xué)家卡克（Subhash Kak）首先提出量子神經(jīng)計算的概念。同年，英國科學(xué)家米尼爾（Tamaryn Menneer）和納拉亞南（Ajit Narayanan）將量子信息學(xué)中的多體觀點應(yīng)用到單層人工神經(jīng)網(wǎng)絡(luò)，提出了量子衍生神經(jīng)網(wǎng)絡(luò)，顯示出在處理分類問題上的有效性。2000年，韓國科學(xué)家韓國賢（Kuk-Hyun Han）等采用量子比特編碼染色體，提出了具有更強并行搜索能力的量子遺傳算法。2005年，日本科學(xué)家幸田典明（Noriaki Kouda）等將量子位引進(jìn)神經(jīng)元定義，提出了量子位神經(jīng)網(wǎng)絡(luò)，仿真試驗表明該神經(jīng)網(wǎng)絡(luò)具有良好的學(xué)習(xí)能力。2006年，谷歌眼鏡項目聯(lián)合創(chuàng)始人奈文（Hartmut Neven）在D-Wave量子計算機上開發(fā)了第一個結(jié)合了量子算法和機器學(xué)習(xí)的圖像識別系統(tǒng)。近年來，量子人工智能算法發(fā)展迅速，出現(xiàn)了量子卷積網(wǎng)絡(luò)、量子自然語言處理、量子生成模型等新型算法。以IBM、谷歌為代表的科技企業(yè)紛紛加強了量子人工智能在新材料設(shè)計、藥物設(shè)計以及化學(xué)反應(yīng)模擬等領(lǐng)域的算法研究。2017年至2020年，IBM、IonQ和谷歌公司先后利用量子計算模擬出氫化鈹、水分子和二氮烯分子，標(biāo)志著量子計算在模擬和發(fā)現(xiàn)小分子化合物上邁出重要一步。2021年1月，谷歌公司與德國醫(yī)藥企業(yè)勃林格殷格翰聯(lián)合成立量子實驗室，致力于實現(xiàn)對蛋白質(zhì)、核酸、多糖等生物大分子的模擬，有望開啟在原子、分子層面理解生命和研發(fā)新藥的新模式。
算法是人工智能的基礎(chǔ)。當(dāng)前，數(shù)據(jù)和算力已經(jīng)不再是人工智能發(fā)展的主要瓶頸，人工智能的創(chuàng)新主要就是算法的創(chuàng)新。隨著人工智能在國家治理、經(jīng)濟發(fā)展、科技創(chuàng)新、醫(yī)療保健、教育培訓(xùn)，乃至日常生活的應(yīng)用日益廣泛和深入，算法越來越重要。在這樣的背景下，只有不斷探索新的算法機制，發(fā)展新的算法應(yīng)用，開發(fā)新的算法模型，發(fā)掘和培養(yǎng)算法人才，才能為推動智能社會發(fā)展提供強勁動力。
聯(lián)系客服
