年終重磅盤點：2022電腦科學6大突破！破解量子加密、最快矩陣乘法等榜上有名

2022年，電腦領域發生許多劃時代的大事。

在今年，電腦科學家學會了完美傳輸秘密，Transformer的進步神速，在AI的幫助下，數十年歷史的演算法被大大改進…

2022年電腦大事件

現在，電腦科學家能解決的問題，範圍是越來越廣了，因此，他們的工作也越來越跨學科。

今年，許多電腦科學領域的成果，也協助了其他科學家和數學家。

例如密碼學問題，這涉及了整個網路的安全。

密碼學的背後，往往是複雜的數學問題。曾經有一個非常有前途的新密碼方案，被認為足以抵禦來自量子電腦的攻擊，然而，這個方案被「兩條橢圓曲線的乘積及其與阿貝爾曲面的關係」這個數學問題推翻了。

以單向函數的形式出現的一組不同的數學關係，將告訴密碼學家是否有真正安全的程式碼。

電腦科學，尤其是量子運算，與物理學也有很大的重疊。

今年理論計算機科學的一件大事，就是科學家證明了NLTS猜想。

這個猜想告訴我們，粒子之間幽靈般的量子糾纏，並不像物理學家曾經想的那樣微妙。

這不僅影響了對我們對物理世界的理解，也影響了糾纏所帶來的無數密碼學的可能性。

另外，人工智慧一直與生物學相得益彰——事實上，生物學領域就是從人腦中汲取靈感，人腦也許是最終極的計算機。

長久以來，電腦科學家和神經科學家都希望了解大腦的工作原理，創造出類腦的人工智慧，但這些似乎一直是白日夢。

但不可思議的是，Transformer神經網路似乎可以像大腦一樣處理資訊。每當我們多了解一些Transformer的工作原理，就更了解大腦一些，反之亦然。

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

甚至，AI還可以幫我們創造更好的AI，新的超網絡（hypernetworks）可以幫助研究人員以更低的成本、用更快的速度訓練神經網絡，還能幫到其他領域的科學家。

Top1：量子糾纏的答案

#量子糾纏是一種將遙遠的粒子緊密聯繫起來的特性，可以肯定的是，一個完全糾纏的系統是無法被完全描述的。

不過物理學家認為，那些接近完全糾纏的系統會比較容易描述。但電腦科學家則認為，這些系統同樣不可能被計算出來，而這就是量子PCP（機率可檢測證明，Probabilistically Checkable Proof）猜想。

為了幫助證明量子PCP理論，科學家提出了一個更簡單的假設，稱為「非低能平凡態」（NLTS）猜想。

今年6月，來自哈佛大學、倫敦大學學院和加州大學柏克萊分校對三位電腦科學家，在一篇論文中首次實現了NLTS猜想的證明。

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

這意味著存在可在更高的溫度下保持糾纏態的量子系統，同時也表明，即使遠離低溫等極端情況，糾纏粒子系統仍然難以分析，難以計算基態能量。

物理學家們很驚訝，因為這意味著糾纏不一定像他們想像的那樣脆弱，而電腦科學家們很高興離證明一個被稱為量子PCP（機率可檢測證明）定理的證明又更近了一步。

今年10月，研究人員成功地將三個粒子在相當遠的距離上糾纏在一起，加強了量子加密的可能性。

Top2：改變AI的理解方式

#在過去的五年裡，Transformer徹底改變了AI處理資訊的方式。

在2017年，Transformer首次出現在一篇論文中。

人們開發Transformer，是為了理解和生成語言。它可以即時處理輸入資料中的每一個元素，讓它們具有「大局觀」。

與其他採取零散方法的語言網路相比，這種「大局觀」讓Transformer的速度和準確性大大提高。

這也使得它具有不可思議的通用性，其他的AI的研究人員，也把Transformer應用在自己的領域。

他們已經發現，應用同樣的原理，可以用來升級影像分類和同時處理多種資料的工具。

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

Transformers迅速成為專注於分析和預測文字的單字辨識等應用程式的領導者。它引發了一波工具浪潮，例如 OpenAI的GPT-3，它訓練數千億個單字並產生一致的新文本，達到令人不安的程度。

不過，跟非Transformer模型相比，這些好處是以Transformer更多的訓練量為代價的。

這些人臉是由基於Transformer的網絡，在對超過20萬張名人面孔的資料集進行訓練後創建的

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

#

事實上，Transformer的適應性如此之強，神經科學家已經開始用基於Transformer的網路對人腦功能進行建模。

這顯示人工智慧和人類智慧之間，或許是一體同源的。

Top3：破解後量子加密演算法

量子運算的出現，讓許多原本需要消耗超大運算量的問題都得到了解決，而經典加密演算法的安全性也因此受到了威脅。於是，學界便提出了後量子密碼的概念，來抵抗量子電腦的破解。

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

然而就在今年7月，兩位來自比利時魯汶大學的研究人員發現，這個演算法可以在短短1個小時內，用一台10年「高齡」的桌上型計算機被成功破解。

值得注意的是，研究人員從純數學的角度來解決這個問題，攻擊演算法設計的核心，而不是任何潛在的程式碼漏洞。

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

對此，研究人員表示，只有當你能證明「單向函數」的存在時，才有可能創建一個可證明的安全程式碼，也就是一個永遠不可能失敗的程式碼。

雖然現在仍然不知道它們是否存在，但研究人員認為，這個問題等同於另一個叫做Kolmogorov複雜性的問題。只有當某一版本的Kolmogorov複雜性難以計算時，單向函數和真正的密碼學才有可能。

Top4：用AI訓練AI

#近年來，人工神經網路的模式辨識技能，為人工智慧領域注入了活力。

但在一個網路開始工作之前，研究人員必須先訓練它。

這個訓練過程可能會持續數月，需要大量數據，在這個過程中，需要對潛在的數十億個參數進行微調。

現在，研究人員有了一個新的想法──讓機器替他們來做這件事。

這種新型「超網路」叫做GHN-2，它能夠處理和吐出其他網路。

論文連結：https://arxiv.org/abs/2110.13100

它的速度很快，能夠分析任何指定的網絡，並迅速提供一組參數值，這些參數值和以傳統方式訓練的網絡中的參數，一樣有效。

儘管GHN-2提供的參數可能不是最佳的，但它仍然提供了一個更理想的起點，減少了全面訓練所需的時間和資料。

透過在給定的圖像資料集和我們的DEEPNETS-1M架構資料集上預測的參數進行反向傳播訓練

今年夏天，Quanta雜誌也研究了另一種幫助機器學習的新方法－具身人工智慧。

它允許演算法從快速回應的三維環境中學習，而不是透過靜態圖像或抽象資料。

無論是探索模擬世界的代理，還是真實世界中的機器人，這些系統擁有從根本上不同的學習方式，而且在許多情況下，這些方式比使用傳統方法訓練的系統更好。

Top5：演算法的改進

提高基礎運算演算法的效率一直都是學界熱點，因為它會影響大量運算的整體速度，從而對智慧運算領域產生骨牌式的效應。

今年10月，DeepMind團隊在發表於Nature上的論文中，提出了第一個用於為矩陣乘法等基本計算任務發現新穎、高效、正確演算法的AI系統——AlphaTensor。

它的出現，為一個50年來的懸而未決的數學問題找到了新答案：找到兩個矩陣相乘的最快方法。

矩陣乘法，作為矩陣變換的基礎運算之一，是許多計算任務的核心組成部分。其中涵蓋了電腦圖形、數位通訊、神經網路訓練和科學計算等等，而AlphaTensor發現的演算法可以使這些領域的計算效率大大提升。

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

今年3月，由六位電腦科學家組成的團隊提出了一個「快得離譜」的演算法，讓電腦最古老的「最大流問題」獲得了突破性的進展。

新演算法可在「幾乎線性」的時間內解決這個問題，也就是說，其運行時間基本上與記錄網路細節所需的時間正比。

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

#最大流問題是一種組合最優化問題，討論的是如何充分利用裝置的能力使得運輸的流量最大，進而取得最好的效果。

在日常生活中，它在許多方面都有應用，如網路資料流、航空公司調度，甚至包含將求職者與職缺進行配對等等。

作為論文的作者之一，來自耶魯大學的Daniel Spielman表示，「我原本堅信，這個問題不可能存在如此高效的演算法。」

Top6：分享資訊的新途徑

普林斯頓大學的理論計算機科學家Mark Braverman，花了一生中超過四分之一的時間，來研究互動式通訊的新理論。

他的工作使研究人員能夠對「資訊」和「知識」等術語進行量化，這不僅使人們在理論上對互動有了更多的了解，而且還創造了新的技術，使交流更有效率和準確。

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

由於他的這一成就，以及其他成果，國際數學聯盟今年7月授予Braverman IMU Abacus獎章，這是理論計算機科學領域的最高榮譽之一。

IMU的頒獎詞指出，Braverman對資訊複雜性的貢獻，使人們更深入地了解了當兩方相互溝通時，資訊成本的不同衡量標準。

他的工作為不易受傳輸錯誤影響的新編碼策略，以及在傳輸和操作過程中壓縮資料的新方法，鋪平了道路。

資訊複雜性問題，來自於Claude Shannon的開創性工作——在1948年，他為一個人透過通道向另一個人發送訊息，制定了數學框架。

而Braverman最大的貢獻在於，建立了一個廣泛的框架，該框架闡明了描述互動式通訊邊界的通用規則——這些規則提出了在透過演算法在線發送數據時，壓縮和保護資料的新策略。

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

「互動式壓縮」問題可以這麼理解：如果兩個人交換一百萬條短信，但只學習1,000位信息，交換是否可以壓縮為1,000位守恆？

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

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

他的理論為探索這些問題和確定可能出現在未來技術中的新通訊協議，奠定了基礎。

以上是年終重磅盤點：2022電腦科學6大突破！破解量子加密、最快矩陣乘法等榜上有名的詳細內容。更多資訊請關注PHP中文網其他相關文章！