2022年计算机科学的六大突破

前言

The Year in Computer Science(2022) 这篇来源于量子杂志(quantamagazine)的文章介绍了2022计算机科学的六大突破。参考资料中也有中文翻译。本着对计算机科学技术未来发展的关注,抽空看了下其中的技术。

量子PCP(概率可检测证明,Probabilistically Checkable Proof)的可行性

为了理解这个2022的突破点,我特地了解了如下知识,其实主要是计算机理论、计算复杂性领域相关的知识,否则的话可能看不懂他们到底搞了点啥。

这个突破其实主要是计算机科学的理论突破。围绕NP问题的形式化证明,可以从理论上证明问题复杂度和可解性。以前是NP问题,现在引入了交互式系统和PCP可以更好的完善NP理论,提供更加高效证明或者求解问题的方式。现在计算机科学理论研究的主要目的还是给计算机应用科学提供一个扎实的理论基础,比如问题是否能在多项式时间内求解,以及如何高效求解。关于NP到NCP,知乎这篇回答可以方便理解为什么NP会过度到PCP以及引入交互式证明:

1
2
3
4
5
6
7
8
回顾一下NP的定义, 说的是如果一个问题在NP中, 那么对于这个问题的解, 存在一个确定性多项式时间算法验证它的正确性.
换一个角度看, 对于NP中的问题, 这里有一个无所不能的证明者 (prover), 和一个计算能力受限 (确定性多项式时间) 的验证者 (verifier),
仅仅使用一次通信 (非交互式证明). 这里有几个地方可以放宽,
其一是我们可以允许验证者使用随机性, 其二是允许更多的通信次数(轮数).
因而, NP把一般化意味着我们所讨论的证明系统从非交互式变成了交互式, 在我们的印象中满堂灌式教学效果往往不如师生大量交互的课堂
直觉上来说这样的交互会提高证明系统的计算能力, 但是能提高多少呢?


然后我们回到这个突破发展本身,主要是因为量子计算的发展。验证者变成了一个量子计算机,证明者和验证者通信是量子态的,这时候求解问题的复杂度发生了怎样的变化呢?之前一些研究其实有一些结论:

1
2
 在量子交互式证明 (即允许多轮交互) 中, 只有量子纠缠(例如使得证明者之间就有量子纠缠)才会带来计算能力的惊人提升, 
证明者和验证者之间使用量子态通信并没有任何优势!

而本次的论文NLTS Hamiltonians from good quantum codes,主要贡献是:

  • 说明存在可在更高的温度下保持纠缠态的量子系统
  • 量子纠缠不一定像科学家们想象的那样脆弱

所以量子计算对于计算复杂度理论的贡献还是得关注如何更好保持纠缠态,然后利用量子系统提升系统解决复杂问题的能力。

有兴趣关注计算机科学最前沿突破的话可以多关注哥德尔奖的获得者成果

Transformer的更多应用场景

机器学习领域包含多种学习模式和实现方式。从最早的经典机器学习方式到后面引入了多层神经网络的深度学习,再到NLP的transformer。现在机器领域学习基于transformer的研究和应用较多。transformer通过引入attention赋予词更多上下文信息使得自然语言的处理更加精准。transformer模型不是图灵完备的,但是在很多领域确实可以更加通用和大放异彩。除了在其擅长的NLP领域,该模式在图片处理识别、人脑功能建模等都有应用。相关论文例如:An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale

寻找绝对安全代码的方式

可以看文章Researchers Identify ‘Master Problem’ Underlying All Cryptography。大意是研究人员发现:

总结:这个突破不能get到价值点。因为该论文只是证明了寻找one-way-function可以等价于解决另外一个问题,离真的找到one-way function还差十万八千里。如果真的能找到one way function如就直接可以证明P!=NP了,感觉这个问题短时间内人类还是很难解决。

超网络用AI训练AI

参考论文:Parameter Prediction for Unseen Deep Architectures 大意是提供了一个新的模型支持AI训练AI

基础算法改进

参考natural论文Discovering faster matrix multiplication algorithms with reinforcement learning。矩阵乘法是矩阵变化的基础运算,也是许多计算任务的核心组成部分。这个算法可以在几乎线性的时间内解决这个问题。在日常生活中,它在很多方面都有应用,如互联网数据流、航空公司调度,甚至包含将求职者与空缺职位进行匹配等等。

交互式通信新理论

参考Braverman这个人的研究Information Equals Amortized Communication。这个研究真的很前沿,主要是关于量化交互式通信的研究,涉及信息成本、数据压缩等。为未来新技术中的新通信协议做准备。

总结:这个感觉离工程应用还十分遥远,我也没有很好的get到他的核心价值。

参考资料