当前位置: 首页 > 科技观察

年终重磅盘点:2022年计算机科学6大突破!破解量子加密、最快矩阵乘法等榜单

时间:2023-03-16 20:26:53 科技观察

2022年,计算机领域将发生许多划时代的事件。这一年,计算机科学家学会了完美传递秘密,Transformer取得了突飞猛进的进步,在AI的帮助下,几十年的算法有了很大的改进……2022年的计算机大事件,现在,计算机所面临的问题范围科学家们可以解决的问题越来越广泛,因此他们的工作越来越跨学科。今年,计算机科学的许多成就也帮助了其他科学家和数学家。比如密码学问题,这涉及到整个互联网的安全。密码学的背后,往往隐藏着复杂的数学问题。曾经有一个非常有前途的新密码方案,被认为足以抵抗来自量子计算机的攻击,然而,这个方案被“两条椭圆曲线的乘积及其与阿贝尔曲面的关系”的数学问题推翻了。一组不同的数学关系,以单向函数的形式,将告诉密码学家他们是否拥有真正安全的代码。计算机科学,尤其是量子计算,也与物理学有很大的重叠。今年理论计算机科学界的一件大事是科学家证明了NLTS猜想。这个猜想告诉我们,粒子之间令人毛骨悚然的量子纠缠并不像物理学家曾经认为的那样微妙。这不仅会影响我们对物理世界的理解,还会影响纠缠打开的无数密码学可能性。此外,人工智能一直是生物学的重要补充——事实上,生物学领域的灵感来自人脑,也许是终极计算机。长期以来,计算机科学家和神经科学家都希望了解大脑的工作原理,创造类脑人工智能,但这些似乎始终是一个白日梦。但神奇的是,Transformer神经网络似乎能像大脑一样处理信息。每当我们更多地了解变形金刚的工作原理时,我们就会更多地了解大脑,反之亦然。或许这就是Transformer如此擅长语言处理和图像分类的原因。甚至,人工智能可以帮助我们创造更好的人工智能。新的超网络可以帮助研究人员以更低的成本和更快的速度训练神经网络,也可以帮助其他领域的科学家。顶部1:量子纠缠的答案量子纠缠是一种将远距离粒子紧密联系在一起的特性。可以肯定的是,无法完全描述一个完全纠缠的系统。但物理学家认为接近完全纠缠的系统更容易描述。但计算机科学家认为,这些系统也是无法计算的,这就是量子PCP(ProbabilisticallyCheckableProof)猜想。为了帮助证明量子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.11929Transformers迅速成为专注于分析和预测文本的文字识别等应用领域的领导者。它推出了一波工具,例如OpenAI的GPT-3,可以训练数千亿个单词并生成一致到令人不安的程度的新文本。然而,与非Transformer模型相比,这些好处是以在Transformer上进行更多培训为代价的。这些面孔是由一个基于Transformer的网络创建的,该网络在超过200,000个名人面孔的数据集上进行训练。今年3月,研究Transformer工作原理的研究人员发现,它之所以如此强大,部分原因在于它能够赋予单词更多的意义,而不是简单地记忆模式。事实上,Transformer的适应性如此之强,以至于神经科学家已经开始使用基于Transformer的网络对人脑功能进行建模。这表明人工智能和人类智能可能是同源的。Top3:破解量子加密算法后量子计算的出现,解决了很多原本需要大量计算的问题,经典加密算法的安全性也受到了威胁。因此,学术界提出了后量子密码学的概念来抵抗量子计算机的破解。SIKE(SupersingularIsogenyKeyEncapsulation)作为一种备受期待的加密算法,是一种以椭圆曲线为定理的加密算法。然而,就在今年7月,比利时鲁汶大学的两名研究人员发现,用一台使用了10年的台式电脑,只需一个小时就可以成功破解该算法。值得注意的是,研究人员从纯粹的数学角度来解决这个问题,攻击算法设计的核心而不是任何底层代码漏洞。论文地址:https://eprint.iacr.org/2022/975对此,研究人员表示,只有能够证明“单向函数”的存在,才有可能创建可证明安全的代码,即,一个永远不会失败的代码。虽然目前还不知道它们是否存在,但研究人员认为这个问题等同于另一个称为Kolmogorov复杂性的问题。单向函数和真正的密码学只有在某些版本的Kolmogorov复杂度难以计算时才有可能。Top4:用AI训练AI近年来,人工神经网络的模式识别技能为人工智能领域注入了活力。但在网络运行之前,研究人员必须首先对其进行训练。这个训练过程可能需要几个月的时间,并且需要大量数据,在此期间可能需要对数十亿个参数进行微调。现在,研究人员有了一个新想法——让机器为他们做这件事。这个新的“超网络”被称为GHN-2,它可以处理和吐出其他网络。论文链接:https://arxiv.org/abs/2110.13100速度快,能够分析任何指定的网络,并快速提供一组参数值,与传统训练的网络一样高效。虽然GHN-2提供的参数可能不是最优的,但它仍然提供了一个更理想的起点,减少了完全训练所需的时间和数据。通过在给定图像数据集和我们的DEEPNETS-1M架构数据集上预测的参数的反向传播进行训练今年夏天,QuantaMagazine还研究了另一种辅助机器学习的新方法——具身AI。它允许算法从响应式三维环境中学习,而不是从静态图像或抽象数据中学习。无论是探索模拟世界的代理人还是现实世界中的机器人,这些系统都以根本不同的方式学习,并且在许多情况下,比使用传统方法训练的系统更好。Top5:算法的改进和基础计算算法效率的提升一直是学术界的热门话题,因为它会影响大量计算的整体速度,从而在计算领域产生多米诺骨牌效应智能计算。今年10月,DeepMind团队在Nature发表的一篇论文中提出了第一个AI系统AlphaTensor,用于为矩阵乘法等基本计算任务发现新颖、高效、正确的算法。它的出现为一个存在了50年的数学问题找到了新的答案:找到两个矩阵相乘的最快方法。矩阵乘法作为矩阵变换的基本运算之一,是许多计算任务的核心组成部分。它涵盖了计算机图形学、数字通信、神经网络训练和科学计算等领域,而AlphaTensor发现的算法可以大大提高这些领域的计算效率。论文地址:https://www.nature.com/articles/s41586-022-05172-4今年三月,一个由六名计算机科学家组成的团队提出了一个“快得离谱”的算法,使最古老的计算机成为“最大流量问题””取得了突破。新算法以“几乎线性”的时间解决了这个问题,即它的运行时间与记录网络细节所需的时间大致成正比。论文地址:https://arxiv.org/abs/2203.00671v2最大流量问题是一个组合优化问题,讨论如何充分利用设备的容量来最大化传输流量,达到最佳效果。在日常生活中,它被用在很多方面,比如互联网数据流、航班时刻表,甚至匹配职位空缺等等。作为该论文的作者之一,来自耶鲁大学的DanielSpielman表示,“我最初认为对于这个问题不可能存在如此高效的算法。”Top6:一种新的信息共享方式普林斯顿大学理论计算机科学家马克·布雷弗曼(MarkBraverman)一生中有超过四分之一的时间致力于研究交互式通信的新理论。他的工作使研究人员能够量化诸如“信息”和“知识”之类的术语,这不仅导致了对相互作用的更多理论理解,而且还创造了使交流更加高效和准确的新技术。Braverman最喜欢做的事情是在他办公室的沙发上思考可量化的难题。为了这一成就,国际数学联合会于7月授予BravermanIMU珠算奖章,这是理论计算机科学领域的最高荣誉之一。IMU的引文指出,Braverman对信息复杂性的贡献导致了对两方相互通信时信息成本的不同度量的更深入理解。他的工作为不易受传输错误影响的新编码策略以及在传输和操作过程中压缩数据的新方法铺平了道路。信息复杂性问题源于克劳德·香农的开创性工作——1948年,他制定了通过通道从一个人向另一个人发送消息的数学框架。然而,Braverman最大的贡献是建立了一个广泛的框架,该框架阐明了描述交互式通信边界的一般规则——这些规则提出了在数据通过算法通过网络发送时压缩和保护数据的新策略。论文地址:https://arxiv.org/abs/1106.3595“交互式压缩”问题可以这样理解:如果两个人交换了一百万条短信,但只学到了1,000比特的信息,那么交换是否可以压缩到1,000保护位?Braverman和Rao的研究表明答案是否定的。Braverman不仅破解了这些问题,他还引入了一个新的视角,使研究人员能够首先阐明它们,然后将它们转化为数学的形式语言。他的理论为探索这些问题和识别未来技术中可能出现的新通信协议提供了基础。