年終重磅盤點(diǎn)：2022計(jì)算機(jī)科學(xué)6大突破！破解量子加密、最快矩陣乘法等榜上有名

來源：新智元

編輯：Aeneas 好困

---

【導(dǎo)讀】2022年，計(jì)算機(jī)領(lǐng)域發(fā)生了哪些大事？Quanta Magazine的年終盤點(diǎn)來了。

2022年，計(jì)算機(jī)領(lǐng)域發(fā)生很多劃時(shí)代的大事。

在今年，計(jì)算機(jī)科學(xué)家學(xué)會(huì)了完美傳輸秘密，Transformer的進(jìn)步神速，在AI的幫助下，數(shù)十年歷史的算法被大大改進(jìn)……

2022年計(jì)算機(jī)大事件現(xiàn)在，計(jì)算機(jī)科學(xué)家能解決的問題，范圍是越來越廣了，因此，他們的工作也越來越跨學(xué)科。今年，許多計(jì)算機(jī)科學(xué)領(lǐng)域的成果，還助力了其他科學(xué)家和數(shù)學(xué)家。比如密碼學(xué)問題，這涉及了整個(gè)互聯(lián)網(wǎng)的安全。

密碼學(xué)的背后，往往是復(fù)雜的數(shù)學(xué)問題。曾經(jīng)有一種非常有前途的新密碼方案，被認(rèn)為足以抵御來自量子計(jì)算機(jī)的攻擊，然而，這個(gè)方案被「兩條橢圓曲線的乘積及其與阿貝爾曲面的關(guān)系」這個(gè)數(shù)學(xué)問題推翻了。

以單向函數(shù)的形式出現(xiàn)的一組不同的數(shù)學(xué)關(guān)系，將告訴密碼學(xué)家是否有真正安全的代碼。

計(jì)算機(jī)科學(xué)，尤其是量子計(jì)算，與物理學(xué)也有很大的重疊。

今年理論計(jì)算機(jī)科學(xué)的一件大事，就是科學(xué)家證明了NLTS猜想。

這個(gè)猜想告訴我們，粒子之間幽靈般的量子糾纏，并不像物理學(xué)家曾經(jīng)想象的那樣微妙。

這不僅影響了對(duì)我們對(duì)物理世界的理解，也影響了糾纏所帶來的無數(shù)密碼學(xué)的可能性。

另外，人工智能一直與生物學(xué)相得益彰——事實(shí)上，生物學(xué)領(lǐng)域就是從人腦中汲取靈感，人腦也許是最終極的計(jì)算機(jī)。

長(zhǎng)久以來，計(jì)算機(jī)科學(xué)家和神經(jīng)科學(xué)家都希望了解大腦的工作原理，創(chuàng)造出類腦的人工智能，但這些似乎一直是白日夢(mèng)。

但不可思議的是，Transformer神經(jīng)網(wǎng)絡(luò)似乎可以像大腦一樣處理信息。每當(dāng)我們多了解一些Transformer的工作原理，就更了解大腦一些，反之亦然。

或許這就是為什么Transformer在語言處理和圖像分類上如此出色的原因。

甚至，AI還可以幫我們創(chuàng)造更好的AI，新的超網(wǎng)絡(luò)（hypernetworks）可以幫助研究人員以更低的成本、用更快的速度訓(xùn)練神經(jīng)網(wǎng)絡(luò)，還能幫到其他領(lǐng)域的科學(xué)家。

Top1：量子糾纏的答案

量子糾纏是一種將遙遠(yuǎn)的粒子緊密聯(lián)系起來的特性，可以肯定的是，一個(gè)完全糾纏的系統(tǒng)是無法被完全描述的。

不過物理學(xué)家認(rèn)為，那些接近完全糾纏的系統(tǒng)會(huì)更容易描述。但計(jì)算機(jī)科學(xué)家則認(rèn)為，這些系統(tǒng)同樣不可能被計(jì)算出來，而這就是量子PCP（概率可檢測(cè)證明，Probabilistically Checkable Proof）猜想。

為了幫助證明量子PCP理論，科學(xué)家們提出了一個(gè)更簡(jiǎn)單的假設(shè)，被稱為「非低能平凡態(tài)」（NLTS）猜想。

今年6月，來自哈佛大學(xué)、倫敦大學(xué)學(xué)院和加州大學(xué)伯克利分校對(duì)三位計(jì)算機(jī)科學(xué)家，在一篇論文中首次實(shí)現(xiàn)了NLTS猜想的證明。

論文地址：https://arxiv.org/abs/2206.13228

這意味著存在可在更高的溫度下保持糾纏態(tài)的量子系統(tǒng)，同時(shí)也表明，即使遠(yuǎn)離低溫等極端情況，糾纏粒子系統(tǒng)仍然難以分析，難以計(jì)算基態(tài)能量。

物理學(xué)家們很驚訝，因?yàn)檫@意味著糾纏不一定像他們想象的那樣脆弱，而計(jì)算機(jī)科學(xué)家們很高興離證明一個(gè)被稱為量子PCP（概率可檢測(cè)證明）定理的證明又近了一步。

今年10月，研究人員成功地將三個(gè)粒子在相當(dāng)遠(yuǎn)的距離上糾纏在一起，加強(qiáng)了量子加密的可能性。

Top2：改變AI的理解方式

在過去的五年里，Transformer徹底改變了AI處理信息的方式。

在2017年，Transformer首次出現(xiàn)在一篇論文中。

人們開發(fā)Transformer，是為了理解和生成語言。它可以實(shí)時(shí)處理輸入數(shù)據(jù)中的每一個(gè)元素，讓它們具有「大局觀」。

與其他采取零散方法的語言網(wǎng)絡(luò)相比，這種「大局觀」讓Transformer的速度和準(zhǔn)確性大大提高。

這也使得它具有不可思議的通用性，其他的AI的研究人員，也把Transformer應(yīng)用于自己的領(lǐng)域。

他們已經(jīng)發(fā)現(xiàn)，應(yīng)用同樣的原理，可以用來升級(jí)圖像分類和同時(shí)處理多種數(shù)據(jù)的工具。

論文地址：https://arxiv.org/abs/2010.11929

Transformers迅速成為專注于分析和預(yù)測(cè)文本的單詞識(shí)別等應(yīng)用程序的領(lǐng)跑者。它引發(fā)了一波工具浪潮，例如 OpenAI的GPT-3，它訓(xùn)練數(shù)千億個(gè)單詞并生成一致的新文本，達(dá)到令人不安的程度。

不過，跟非Transformer模型相比，這些好處是以Transformer更多的訓(xùn)練量為代價(jià)的。

在今年3月，研究Transformer工作原理的研究人員發(fā)現(xiàn)，它之所以如此強(qiáng)大，部分原因是它將更大的意義附加到詞語上的能力，而不是簡(jiǎn)單的記憶模式。

事實(shí)上，Transformer的適應(yīng)性如此之強(qiáng)，神經(jīng)科學(xué)家已經(jīng)開始用基于Transformer的網(wǎng)絡(luò)對(duì)人腦功能進(jìn)行建模。

這表明人工智能和人類智能之間，或許是一體同源的。

Top3：破解后量子加密算法

量子計(jì)算的出現(xiàn)，讓很多原本需要消耗超大計(jì)算量的問題都得到了解決，而經(jīng)典加密算法的安全性也因此受到了威脅。于是，學(xué)界便提出了后量子密碼的概念，來抵抗量子計(jì)算機(jī)的破解。

作為備受期待的加密算法，SIKE（Supersingular Isogeny Key Encapsulation）是一種利用橢圓曲線作為定理的加密算法。

然而就在今年7月，兩位來自比利時(shí)魯汶大學(xué)的研究人員發(fā)現(xiàn)，這個(gè)算法可以在短短1個(gè)小時(shí)內(nèi)，用一臺(tái)10年「高齡」的臺(tái)式計(jì)算機(jī)被成功破解。

值得注意的是，研究人員從純數(shù)學(xué)的角度來解決這個(gè)問題，攻擊算法設(shè)計(jì)的核心，而不是任何潛在的代碼漏洞。

論文地址：https://eprint.iacr.org/2022/975

對(duì)此，研究人員表示，只有當(dāng)你能證明「單向函數(shù)」的存在時(shí)，才有可能創(chuàng)建一個(gè)可證明的安全代碼，也就是一個(gè)永遠(yuǎn)不可能失敗的代碼。

雖然現(xiàn)在仍然不知道它們是否存在，但研究人員認(rèn)為，這個(gè)問題等同于另一個(gè)叫做Kolmogorov復(fù)雜性的問題。只有當(dāng)某一版本的Kolmogorov復(fù)雜性難以計(jì)算時(shí)，單向函數(shù)和真正的密碼學(xué)才有可能。

Top4：用AI訓(xùn)練AI

近年來，人工神經(jīng)網(wǎng)絡(luò)的模式識(shí)別技能，為人工智能領(lǐng)域注入了活力。

但在一個(gè)網(wǎng)絡(luò)開始工作之前，研究人員必須首先訓(xùn)練它。

這個(gè)訓(xùn)練過程可能會(huì)持續(xù)數(shù)月，需要大量數(shù)據(jù)，在這個(gè)過程中，需要對(duì)潛在的數(shù)十億個(gè)參數(shù)進(jìn)行微調(diào)。

現(xiàn)在，研究人員有了一個(gè)新的想法——讓機(jī)器替他們來做這件事。

這種新型「超網(wǎng)絡(luò)」叫做GHN-2，它能夠處理和吐出其他網(wǎng)絡(luò)。

論文鏈接：https://arxiv.org/abs/2110.13100

它的速度很快，能夠分析任何指定的網(wǎng)絡(luò)，并迅速提供一組參數(shù)值，這些參數(shù)值和以傳統(tǒng)方式訓(xùn)練的網(wǎng)絡(luò)中的參數(shù)，一樣有效。

盡管GHN-2提供的參數(shù)可能不是最佳的，但它仍然提供了一個(gè)更理想的起點(diǎn)，減少了全面訓(xùn)練所需的時(shí)間和數(shù)據(jù)。

通過在給定的圖像數(shù)據(jù)集和我們的DEEPNETS-1M架構(gòu)數(shù)據(jù)集上預(yù)測(cè)的參數(shù)進(jìn)行反向傳播訓(xùn)練

今年夏天，Quanta雜志還研究了另一種幫助機(jī)器學(xué)習(xí)的新方法——具身人工智能。

它允許算法從響應(yīng)迅速的三維環(huán)境中學(xué)習(xí)，而不是通過靜態(tài)圖像或抽象數(shù)據(jù)。

無論是探索模擬世界的代理，還是真實(shí)世界中的機(jī)器人，這些系統(tǒng)擁有從根本上不同的學(xué)習(xí)方式，而且在許多情況下，這些方式比使用傳統(tǒng)方法訓(xùn)練的系統(tǒng)更好。

Top5：算法的改進(jìn)

提高基礎(chǔ)計(jì)算算法的效率一直都是學(xué)界熱點(diǎn)，因?yàn)樗鼤?huì)影響大量計(jì)算的整體速度，從而對(duì)智能計(jì)算領(lǐng)域產(chǎn)生多米諾骨牌式的效應(yīng)。

今年10月，DeepMind團(tuán)隊(duì)在發(fā)表于Nature上的論文中，提出了第一個(gè)用于為矩陣乘法等基本計(jì)算任務(wù)發(fā)現(xiàn)新穎、高效、正確算法的AI系統(tǒng)——AlphaTensor。

它的出現(xiàn)，為一個(gè)50年來的懸而未決的數(shù)學(xué)問題找到了新答案：找到兩個(gè)矩陣相乘的最快方法。

矩陣乘法，作為矩陣變換的基礎(chǔ)運(yùn)算之一，是許多計(jì)算任務(wù)的核心組成部分。其中涵蓋了計(jì)算機(jī)圖形、數(shù)字通信、神經(jīng)網(wǎng)絡(luò)訓(xùn)練和科學(xué)計(jì)算等等，而AlphaTensor發(fā)現(xiàn)的算法可以使這些領(lǐng)域的計(jì)算效率大大提升。

論文地址：https://www.nature.com/articles/s41586-022-05172-4

今年3月，由六位計(jì)算機(jī)科學(xué)家組成的團(tuán)隊(duì)提出了一種「快得離譜」的算法，讓計(jì)算機(jī)最古老的「最大流問題」獲得了突破性的進(jìn)展。

新算法可在「幾乎線性」的時(shí)間內(nèi)解決這個(gè)問題，也就是說，其運(yùn)行時(shí)間基本與記錄網(wǎng)絡(luò)細(xì)節(jié)所需的時(shí)間正比。

論文地址：https://arxiv.org/abs/2203.00671v2

最大流問題是一種組合最優(yōu)化問題，討論的是如何充分利用裝置的能力使得運(yùn)輸?shù)牧髁孔畲?，進(jìn)而取得最好的效果。

在日常生活中，它在很多方面都有應(yīng)用，如互聯(lián)網(wǎng)數(shù)據(jù)流、航空公司調(diào)度，甚至包含將求職者與空缺職位進(jìn)行匹配等等。

作為論文的作者之一，來自耶魯大學(xué)的Daniel Spielman表示，「我原本堅(jiān)信，這個(gè)問題不可能存在如此高效的算法?！?/span>

Top6：分享信息的新途徑

普林斯頓大學(xué)的理論計(jì)算機(jī)科學(xué)家Mark Braverman，花了一生中超過四分之一的時(shí)間，來研究交互式通信的新理論。

他的工作使研究人員能夠?qū)Α感畔ⅰ购汀钢R(shí)」等術(shù)語進(jìn)行量化，這不僅使人們?cè)诶碚撋蠈?duì)互動(dòng)有了更多的了解，而且還創(chuàng)造了新的技術(shù)，使交流更加高效和準(zhǔn)確。

Braverman最喜歡在辦公室的沙發(fā)上思考量化的難題

由于他的這一成就，以及其他成果，國(guó)際數(shù)學(xué)聯(lián)盟今年7月授予Braverman IMU Abacus獎(jiǎng)?wù)?，這是理論計(jì)算機(jī)科學(xué)領(lǐng)域的最高榮譽(yù)之一。

IMU的頒獎(jiǎng)詞指出，Braverman對(duì)信息復(fù)雜性的貢獻(xiàn)，使人們更深入地了解了當(dāng)兩方相互溝通時(shí)，信息成本的不同衡量標(biāo)準(zhǔn)。

他的工作為不易受傳輸錯(cuò)誤影響的新編碼策略，以及在傳輸和操作過程中壓縮數(shù)據(jù)的新方法，鋪平了道路。

信息復(fù)雜性問題，來自于Claude Shannon的開拓性工作——在1948年，他為一個(gè)人通過通道向另一個(gè)人發(fā)送消息，制定了數(shù)學(xué)框架。

而Braverman最大的貢獻(xiàn)在于，建立了一個(gè)廣泛的框架，該框架闡明了描述交互式通信邊界的通用規(guī)則——這些規(guī)則提出了在通過算法在線發(fā)送數(shù)據(jù)時(shí)，壓縮和保護(hù)數(shù)據(jù)的新策略。

論文地址：https://arxiv.org/abs/1106.3595

「交互式壓縮」問題可以這么理解：如果兩個(gè)人交換一百萬條短信，但只學(xué)習(xí)1,000位信息，交換是否可以壓縮為1,000位守恒？

Braverman和Rao的研究表明，答案是否定的。

而Braverman不僅破解了這些問題，他還引入了一種新的視角，使研究人員能夠首先闡明它們，然后將它們翻譯成數(shù)學(xué)的正式語言。

他的理論為探索這些問題和確定可能出現(xiàn)在未來技術(shù)中的新通信協(xié)議，奠定了基礎(chǔ)。

參考資料：

https://www.quantamagazine.org/the-biggest-discoveries-in-computer-science-in-2022-20221221/

https://mp.weixin.qq.com/s/ALpgkM6jg_-xA8UYg0O5GA

END

歡迎加入Imagination GPU與人工智能交流2群入群請(qǐng)加小編微信：eetrend89

（添加請(qǐng)備注公司名和職稱）

推薦閱讀 對(duì)話Imagination中國(guó)區(qū)董事長(zhǎng)：以GPU為支點(diǎn)加強(qiáng)軟硬件協(xié)同，助力數(shù)字化轉(zhuǎn)型

ICCAD 2022，Imagination邀您共聚廈門！

Imagination Technologies是一家總部位于英國(guó)的公司，致力于研發(fā)芯片和軟件知識(shí)產(chǎn)權(quán)（IP），基于Imagination IP的產(chǎn)品已在全球數(shù)十億人的電話、汽車、家庭和工作場(chǎng)所中使用。獲取更多物聯(lián)網(wǎng)、智能穿戴、通信、汽車電子、圖形圖像開發(fā)等前沿技術(shù)信息，歡迎關(guān)注 Imagination Tech！