亚洲之星：新闻界人物广告

tigongmeishicankaomeishiyuyuegongneng，youyixiedifangshixuyaoyuyuede，zhijiezaizhelijiunengyuyue。zhanjiangzuhejiqiwuxiazuiqiangzhensuishidoukeyiqujinxingqingli，erqiehaikeyiqujianceshoujineideanquanhuanjing。【naodongtucao】zuixinwenzhangzixun年(nian)終(zhong)重(zhong)磅(bang)盤(pan)點(dian)：2022計(ji)算(suan)機(ji)科(ke)學(xue)6大(da)突(tu)破(po)！破解(jie)量(liang)子(zi)加(jia)密(mi)、最(zui)快(kuai)矩(ju)陣(zhen)乘(cheng)法(fa)等(deng)榜(bang)上(shang)有(you)名(ming)

新(xin)智(zhi)元(yuan)報(bao)道(dao)

編(bian)輯(ji)：Aeneas 好(hao)困(kun)

【新智元導(dao)讀(du)】2022年，计算机領(ling)域(yu)發(fa)生(sheng)了(le)哪(na)些(xie)大事(shi)？Quanta Magazine的(de)年终盘点來(lai)了。

2022年，计算机领域发生很(hen)多(duo)劃(hua)時(shi)代(dai)的大事。

在(zai)今(jin)年，计算机科学家(jia)学會(hui)了完(wan)美(mei)傳(chuan)輸(shu)秘(mi)密，Transformer的進(jin)步(bu)神(shen)速(su)，在AI的幫(bang)助(zhu)下(xia)，數(shu)十(shi)年歷(li)史(shi)的算法被(bei)大大改(gai)进……

2022年计算机大事件(jian)

現(xian)在，计算机科学家能(neng)解決(jue)的問(wen)題(ti)，範(fan)圍(wei)是(shi)越(yue)来越廣(guang)了，因(yin)此(ci)，他(ta)們(men)的工(gong)作(zuo)也(ye)越来越跨(kua)学科。

今年，許(xu)多计算机科学领域的成(cheng)果(guo)，還(hai)助力(li)了其(qi)他科学家和(he)数学家。

比(bi)如(ru)密碼(ma)学问题，這(zhe)涉(she)及(ji)了整(zheng)個(ge)互(hu)聯(lian)網(wang)的安(an)全(quan)。

密码学的背(bei)後(hou)，往(wang)往是復(fu)雜(za)的数学问题。曾(zeng)經(jing)有壹(yi)種(zhong)非(fei)常(chang)有前(qian)途(tu)的新密码方(fang)案(an)，被認(ren)為(wei)足(zu)以(yi)抵(di)禦(yu)来自(zi)量子计算机的攻(gong)擊(ji)，然(ran)而(er)，这个方案被「兩(liang)條(tiao)橢(tuo)圓(yuan)曲(qu)線(xian)的乘積(ji)及其與(yu)阿(e)貝(bei)爾(er)曲面(mian)的關(guan)系(xi)」这个数学问题推(tui)翻(fan)了。

以單(dan)向(xiang)函(han)数的形(xing)式(shi)出(chu)现的一組(zu)不(bu)同(tong)的数学关系，將(jiang)告(gao)訴(su)密码学家是否(fou)有真(zhen)正(zheng)安全的代码。

计算机科学，尤(you)其是量子计算，与物(wu)理(li)学也有很大的重疊(die)。

今年理論(lun)计算机科学的一件大事，就(jiu)是科学家證(zheng)明(ming)了NLTS猜(cai)想(xiang)。

这个猜想告诉我(wo)们，粒(li)子之(zhi)間(jian)幽(you)靈(ling)般(ban)的量子糾(jiu)纏(chan)，並(bing)不像(xiang)物理学家曾经想象(xiang)的那(na)樣(yang)微(wei)妙(miao)。

这不僅(jin)影(ying)響(xiang)了對(dui)我们对物理世(shi)界(jie)的理解，也影响了纠缠所(suo)帶(dai)来的無(wu)数密码学的可(ke)能性(xing)。

另(ling)外(wai)，人(ren)工智能一直(zhi)与生物学相(xiang)得(de)益(yi)彰(zhang)——事實(shi)上，生物学领域就是從(cong)人腦(nao)中(zhong)汲(ji)取(qu)灵感(gan)，人脑也许是最终極(ji)的计算机。

長(chang)久(jiu)以来，计算机科学家和神经科学家都(dou)希(xi)望(wang)了解大脑的工作原(yuan)理，創(chuang)造(zao)出類(lei)脑的人工智能，但(dan)这些似(si)乎(hu)一直是白(bai)日(ri)夢(meng)。

但不可思(si)議(yi)的是，Transformer神经网絡(luo)似乎可以像大脑一样處(chu)理信(xin)息(xi)。每(mei)當(dang)我们多了解一些Transformer的工作原理，就更(geng)了解大脑一些，反(fan)之亦(yi)然。

或(huo)许这就是为什(shen)麽(me)Transformer在語(yu)言(yan)处理和圖(tu)像分(fen)类上如此出色(se)的原因。

甚(shen)至(zhi)，AI还可以帮我们创造更好的AI，新的超(chao)网络（hypernetworks）可以帮助研(yan)究(jiu)人員(yuan)以更低(di)的成本(ben)、用(yong)更快的速度(du)訓(xun)練(lian)神经网络，还能帮到(dao)其他领域的科学家。

Top1：量子纠缠的答(da)案

量子纠缠是一种将遙(yao)遠(yuan)的粒子緊(jin)密联系起(qi)来的特(te)性，可以肯(ken)定(ding)的是，一个完全纠缠的系統(tong)是无法被完全描(miao)述(shu)的。

不過(guo)物理学家认为，那些接(jie)近(jin)完全纠缠的系统会更容(rong)易(yi)描述。但计算机科学家則(ze)认为，这些系统同样不可能被计算出来，而这就是量子PCP（概(gai)率(lv)可檢(jian)測(ce)证明，Probabilistically Checkable Proof）猜想。

为了帮助证明量子PCP理论，科学家们提(ti)出了一个更簡(jian)单的假(jia)設(she)，被稱(cheng)为「非低能平(ping)凡(fan)態(tai)」（NLTS）猜想。

今年6月(yue)，来自哈(ha)佛(fo)大学、倫(lun)敦(dun)大学学院(yuan)和加州(zhou)大学伯(bo)克(ke)利(li)分校(xiao)对三(san)位(wei)计算机科学家，在一篇(pian)论文(wen)中首(shou)次(ci)实现了NLTS猜想的证明。

论文地(di)址(zhi)：https://arxiv.org/abs/2206.13228

这意(yi)味(wei)著(zhe)存(cun)在可在更高(gao)的溫(wen)度下保(bao)持(chi)纠缠态的量子系统，同时也表(biao)明，即(ji)使(shi)远離(li)低温等极端(duan)情(qing)況(kuang)，纠缠粒子系统仍(reng)然難(nan)以分析(xi)，难以计算基(ji)态能量。

物理学家们很驚(jing)訝(ya)，因为这意味着纠缠不一定像他们想象的那样脆(cui)弱(ruo)，而计算机科学家们很高興(xing)离证明一个被称为量子PCP（概率可检测证明）定理的证明又(you)近了一步。

今年10月，研究人员成功(gong)地将三个粒子在相当远的距(ju)离上纠缠在一起，加強(qiang)了量子加密的可能性。

Top2：改變(bian)AI的理解方式

在过去(qu)的五(wu)年裏(li)，Transformer徹(che)底(di)改变了AI处理信息的方式。

在2017年，Transformer首次出现在一篇论文中。

人们開(kai)发Transformer，是为了理解和生成语言。它(ta)可以实时处理输入(ru)数據(ju)中的每一个元素(su)，讓(rang)它们具(ju)有「大局(ju)觀(guan)」。

与其他采(cai)取零(ling)散(san)方法的语言网络相比，这种「大局观」让Transformer的速度和準(zhun)確(que)性大大提高。

这也使得它具有不可思议的通(tong)用性，其他的AI的研究人员，也把(ba)Transformer應(ying)用於(yu)自己(ji)的领域。

他们已(yi)经发现，应用同样的原理，可以用来升(sheng)級(ji)图像分类和同时处理多种数据的工具。

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

Transformers迅(xun)速成为專(zhuan)註(zhu)于分析和預(yu)测文本的单詞(ci)識(shi)別(bie)等应用程(cheng)序(xu)的领跑(pao)者(zhe)。它引(yin)发了一波(bo)工具浪(lang)潮(chao)，例(li)如 OpenAI的GPT-3，它训练数千(qian)億(yi)个单词并生成一致(zhi)的新文本，達(da)到令(ling)人不安的程度。

不过，跟(gen)非Transformer模(mo)型(xing)相比，这些好处是以Transformer更多的训练量为代價(jia)的。

这些人臉(lian)是由(you)基于Transformer的网络，在对超过20萬(wan)張(zhang)名人面孔(kong)的数据集(ji)进行(xing)训练后创建(jian)的

在今年3月，研究Transformer工作原理的研究人员发现，它之所以如此强大，部(bu)分原因是它将更大的意義(yi)附(fu)加到词语上的能力，而不是简单的記(ji)憶(yi)模式。

事实上，Transformer的適(shi)应性如此之强，神经科学家已经开始(shi)用基于Transformer的网络对人脑功能进行建模。

这表明人工智能和人类智能之间，或许是一體(ti)同源(yuan)的。

Top3：破解后量子加密算法

量子计算的出现，让很多原本需(xu)要(yao)消(xiao)耗(hao)超大计算量的问题都得到了解决，而经典(dian)加密算法的安全性也因此受(shou)到了威(wei)脅(xie)。于是，学界便(bian)提出了后量子密码的概念(nian)，来抵抗(kang)量子计算机的破解。

作为備(bei)受期(qi)待(dai)的加密算法，SIKE（Supersingular Isogeny Key Encapsulation）是一种利用椭圆曲线作为定理的加密算法。

然而就在今年7月，两位来自比利时魯(lu)汶(wen)大学的研究人员发现，这个算法可以在短(duan)短1个小(xiao)时內(nei)，用一臺(tai)10年「高齡(ling)」的台式计算机被成功破解。

值(zhi)得注意的是，研究人员从純(chun)数学的角(jiao)度来解决这个问题，攻击算法设计的核(he)心(xin)，而不是任(ren)何(he)潛(qian)在的代码漏(lou)洞(dong)。

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

对此，研究人员表示(shi)，只(zhi)有当妳(ni)能证明「单向函数」的存在时，才(cai)有可能创建一个可证明的安全代码，也就是一个永(yong)远不可能失(shi)敗(bai)的代码。

雖(sui)然现在仍然不知(zhi)道它们是否存在，但研究人员认为，这个问题等同于另一个叫(jiao)做(zuo)Kolmogorov复杂性的问题。只有当某(mou)一版(ban)本的Kolmogorov复杂性难以计算时，单向函数和真正的密码学才有可能。

Top4：用AI训练AI

近年来，人工神经网络的模式识别技(ji)能，为人工智能领域注入了活(huo)力。

但在一个网络开始工作之前，研究人员必(bi)須(xu)首先(xian)训练它。

这个训练过程可能会持續(xu)数月，需要大量数据，在这个过程中，需要对潜在的数十亿个參(can)数进行微調(tiao)。

现在，研究人员有了一个新的想法——让机器(qi)替(ti)他们来做这件事。

这种新型「超网络」叫做GHN-2，它能夠(gou)处理和吐(tu)出其他网络。

论文鏈(lian)接：https://arxiv.org/abs/2110.13100

它的速度很快，能够分析任何指(zhi)定的网络，并迅速提供(gong)一组参数值，这些参数值和以传统方式训练的网络中的参数，一样有效(xiao)。

盡(jin)管(guan)GHN-2提供的参数可能不是最佳(jia)的，但它仍然提供了一个更理想的起点，減(jian)少(shao)了全面训练所需的时间和数据。

通过在給(gei)定的图像数据集和我们的DEEPNETS-1M架(jia)構(gou)数据集上预测的参数进行反向传播(bo)训练

今年夏(xia)天(tian)，Quanta杂誌(zhi)还研究了另一种帮助机器学習(xi)的新方法——具身(shen)人工智能。

它允(yun)许算法从响应迅速的三維(wei)環(huan)境(jing)中学习，而不是通过靜(jing)态图像或抽(chou)象数据。

无论是探(tan)索(suo)模擬(ni)世界的代理，还是真实世界中的机器人，这些系统擁(yong)有从根(gen)本上不同的学习方式，而且(qie)在许多情况下，这些方式比使用传统方法训练的系统更好。

Top5：算法的改进

提高基礎(chu)计算算法的效率一直都是学界熱(re)点，因为它会影响大量计算的整体速度，从而对智能计算领域產(chan)生多米(mi)諾(nuo)骨(gu)牌(pai)式的效应。

今年10月，DeepMind團(tuan)隊(dui)在发表于Nature上的论文中，提出了第(di)一个用于为矩阵乘法等基本计算任務(wu)发现新穎(ying)、高效、正确算法的AI系统——AlphaTensor。

它的出现，为一个50年来的懸(xuan)而未(wei)决的数学问题找(zhao)到了新答案：找到两个矩阵相乘的最快方法。

矩阵乘法，作为矩阵变換(huan)的基础運(yun)算之一，是是许多计算任务的核心组成部分。其中涵(han)蓋(gai)了计算机图形、数字(zi)通信、神经网络训练和科学计算等等，而AlphaTensor发现的算法可以使这些领域的计算效率大大提升。

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

今年3月，由六(liu)位计算机科学家组成的团队提出了一种「快得离譜(pu)」的算法，让计算机最古(gu)老(lao)的「最大流(liu)问题」獲(huo)得了突破性的进展(zhan)。

新算法可在「幾(ji)乎线性」的时间内解决这个问题，也就是說(shuo)，其运行时间基本与记錄(lu)网络細(xi)節(jie)所需的时间正比。

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

最大流问题是一种组合(he)最優(you)化(hua)问题，討(tao)论的是如何充(chong)分利用裝(zhuang)置(zhi)的能力使得运输的流量最大，进而取得最好的效果。

在日常生活中，它在很多方面都有应用，如互联网数据流、航(hang)空(kong)公(gong)司(si)调度，甚至包(bao)含(han)将求(qiu)職(zhi)者与空缺(que)职位进行匹(pi)配(pei)等等。

作为论文的作者之一，来自耶(ye)鲁大学的Daniel Spielman表示，「我原本堅(jian)信，这个问题不可能存在如此高效的算法。」

Top6：分享(xiang)信息的新途徑(jing)

普(pu)林(lin)斯(si)頓(dun)大学的理论计算机科学家Mark Braverman，花(hua)了一生中超过四(si)分之一的时间，来研究交(jiao)互式通信的新理论。

他的工作使研究人员能够对「信息」和「知识」等術(shu)语进行量化，这不仅使人们在理论上对互動(dong)有了更多的了解，而且还创造了新的技术，使交流更加高效和准确。

Braverman最喜(xi)歡(huan)在辦(ban)公室(shi)的沙(sha)发上思考(kao)量化的难题

由于他的这一成就，以及其他成果，國(guo)際(ji)数学联盟(meng)今年7月授(shou)予(yu)Braverman IMU Abacus獎(jiang)章(zhang)，这是理论计算机科学领域的最高榮(rong)譽(yu)之一。

IMU的頒(ban)奖词指出，Braverman对信息复杂性的貢(gong)獻(xian)，使人们更深(shen)入地了解了当两方相互溝(gou)通时，信息成本的不同衡(heng)量標(biao)准。

他的工作为不易受传输錯(cuo)誤(wu)影响的新编码策(ce)略(lve)，以及在传输和操(cao)作过程中壓(ya)縮(suo)数据的新方法，鋪(pu)平了道路(lu)。

信息复杂性问题，来自于Claude Shannon的开拓(tuo)性工作——在1948年，他为一个人通过通道向另一个人发送(song)消息，制(zhi)定了数学框(kuang)架。

而Braverman最大的贡献在于，建立(li)了一个广泛(fan)的框架，該(gai)框架闡(chan)明了描述交互式通信邊(bian)界的通用規(gui)则——这些规则提出了在通过算法在线发送数据时，压缩和保護(hu)数据的新策略。

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

「交互式压缩」问题可以这么理解：如果两个人交换一百(bai)万条短信，但只学习1,000位信息，交换是否可以压缩为1,000位守(shou)恒(heng)？

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

而Braverman不仅破解了这些问题，他还引入了一种新的視(shi)角，使研究人员能够首先阐明它们，然后将它们翻譯(yi)成数学的正式语言。

他的理论为探索这些问题和确定可能出现在未来技术中的新通信協(xie)议，奠(dian)定了基础。

参考資(zi)料(liao)：

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

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

向雲(yun)新生，终端进化的未来进行时 返(fan)回(hui)搜(sou)狐(hu)，查(zha)看(kan)更多

責(ze)任编辑：