当自然语言处理遇上量子计算与范畴论：人工智能开启更大想象空间

导语

无论是ChatGPT还是GPT-4的横行都让人看到了人工智能处理人类语言的巨大潜力。然而，这篇文章告诉我们，这远远不是机器语言学（机器智能与自然语言结合）的极限，量子信息、范畴论与自然语言处理的结合可以创造更大的想象空间。一方面，量子计算的助力将会让传统的自然语言处理任务出现质的提升；另一方面，该文指出，自然语言处理和量子力学存在着天然的类比关系，它们都是组合的分布式表示的特例。这一类比关系可以用一门方兴未艾的数学——范畴论加以严格的刻画。而且，本文的原作者并未止步于理论探索，他们还开发了一套基于Python的应用范畴论通用工具包DisCoPy，并展示了其在连接量子计算和自然语言处理任务的应用，为未来的应用范畴论和量子自然语言处理研究打下了良好的基础。

温馨提示：这篇文章牵涉了大量的范畴论的专业术语未加解释，建议大家先收藏然后再在PC上慢慢阅读，并逐个术语和文献地追踪溯源，这才是阅读这篇文章的正确姿势。

——张江

关键词：量子计算，自然语言处理，计算语言学，范畴论

Alexis TOUMI | 作者

陈天豪 | 译者

张江 | 审校

梁金 | 编辑

论文题目：Category Theory for Quantum Natural Language Processing
论文链接：https://arxiv.org/abs/2212.06615

本文翻译自上述论文的 Introduction 部分，文章分成了三部分：首先，作者对量子计算的发展历史进行了回顾；其次，作者系统性地梳理了从文法结构到现如今基于深度学习的自然语言处理领域的一些进展；最后，作者开始讨论量子力学与自然语言之间的类比关系，并系统性地梳理了如何使用范畴论来刻画不同事物背后的共性。

目录

摘要

量子计算机有什么长处？

为什么我们要让 NLP 量子化？

范畴论能提供什么帮助？

摘要

这篇论文介绍了量子自然语言处理（quantum natural language processing, QNLP）模型，基于计算语言学和量子力学之间的简单而有力的类比：将语法作为纠缠。文本和句子的语法结构将词语的意思联系起来，正如纠缠结构将量子系统的状态联系起来一样。范畴论让这样从语言到量子比特的类比得以形式化地表述为：从语法到向量空间的幺半函子（monoidal functor）。

我们将这种抽象类比转化为具体算法，将语法结构转化为参数化量子电路的架构。然后使用经典-量子混合算法来训练模型，这样评估电路就可以计算数据驱动任务中句子的含义。

QNLP 模型的实现推动了 DisCoPy（Distributional Compositional Python）的开发，DisCoPy 是应用范畴论的工具包。线图（string diagram）是 DisCoPy 的核心数据结构，允许在高度抽象的层级对计算进行推理。我们将展示线图如何编码语法结构和量子电路，以及逻辑公式、神经网络或任意 Python 代码。幺半函子使得将抽象的线图转换为具体的计算成为可能。

量子计算机有什么长处？

大自然不是经典的，该死，如果你想模拟大自然，你最好让它量子力学化，天哪，这是一个奇妙的问题，因为它看起来如此不容易。——用计算机模拟物理（Simulating Physics with Computers），费曼 （1981）

量子计算机利用叠加和纠缠等量子理论原理来解决信息处理任务。在过去42年中，量子计算已经从一种纯理论上的推测发展到了可以实现的机器，这些机器可以解决经典方法无法解决的问题。本节将简要介绍该领域的历史及其未来的挑战。

1980年，Benioff [1] 从计算的抽象定义出发，使量子计算这个定义物理化：他设计了一个量子力学系统，其时间演化编码了给定的图灵机的计算步骤。回想起来，这可能是量子力学可以模拟经典计算机的第一个证据。在同一年，Manin [2] 沿着相反的方向看问题：他认为经典计算机模拟一般量子系统应该需要指数长的时间。费曼[3; 4]也得出了同样的结论，并提出了一种更有效地模拟量子力学的方法：搭建量子计算机！

那么，量子计算机有什么长处呢？费曼的直觉给了我们第一个不言而喻的答案：至少量子计算机可以有效地模拟量子力学。Deutsch [5] 通过定义量子图灵机和电路模型，使问题形式化。Deutsch和Jozsa [6] 设计了第一个量子算法，并证明了它在解决某些问题上，与任何经典确定性算法相比（注7-1），速度能有指数级的提升。Simon [7] 改进了Deutsch和Jozsa的结果，他设计了一个问题，在应用量子计算机求解这个问题时与任何经典算法相比都能取得指数级的加速。Deutsch-Jozsa和Simon的工作依赖于预言机（oracles）（注8-1）和输入的承诺特性 （promises）（注8-2），他们的问题几乎没有实际用处。然而，他们启发了Shor的质因数分解和离散对数算法 [8]。这两个问题被认为在经典计算机上，需要指数时间来求解。这也是目前互联网上使用的公开密钥加密算法的基础。

1997年，Grover找到了量子计算机的另一种应用：“大海捞针” [9]。形式化地说，这个问题需要给定一个函数f: X→{0, 1}并且承诺存在唯一的x∈X使得f(x)=1成立，Grover 的算法可以在 步中找到x，与最优的经典算法的步比有二次方级别的加速。Grover 的算法可用于蛮力攻击比经典方法大两倍的对称加密密钥 [10] 系统。它在解决NP难问题（如约束满足问题 [11] ）所涉及的穷举搜索算法上还可以获得二次方级别的加速。Bennett等人 [12] 独立地证明了Grover的算法实际上是最优的，这为量子计算机无法在多项式时间内解决这些NP难题的猜想增添了证据。Chung等人 [13] 给出了量子算法的第一个实验演示，在两个量子比特上运行Grover算法。

Shor和Grover所发现的量子算法是第一次真实世界的应用，这引发了人们对量子计算的极大兴趣。随后，这两个算法的核心分别被抽象成两种子程序：相位估计 [14] 和振幅放大 [15]。利用这两种子程序，HHL（注8-3）算法 [16] 解决了科学计算中最无处不在的问题之一：求解线性方程组。给定一个矩阵和一个向量，我们想要找到一个向量x，使得Ax=b。在一些关于矩阵A的稀疏性和条件数假设下，HHL以对数的时间找到（近似的）x，而经典算法将花费二次方的时间读取矩阵A的每一个元素。这引发了人们对量子计算的新一波热情，它有望实现机器学习任务的指数级加速，这些任务包括有回归 [17]、聚类 [18]、分类 [19]、降维 [20]和推荐 [21] 等。这样的叙事很有吸引力：机器学习是关于在大量数据中寻找模式，这些数据被表示为高维向量和张量，这正是量子计算机擅长的。这个论点可以用复杂性理论形式化：HHL是BQP完备的，因此，如果量子算法有指数优势，那么HHL肯定有指数优势。

然而，HHL的指数加速也带来一些值得注意的问题，Aaronson [22] 对此进行了深入分析。其中两个挑战在许多量子算法中都很常见：1）将经典数据有效编码为量子态，2）通过量子测量有效提取经典数据。事实上，HHL真正作为输入的不是向量b，而是称为振幅编码的量子态。除非输入向量b具有足够的结构，我们才可以用一个简单、显式的公式来描述它。例如，在计算电磁散射截面时就是这种情况 [23]。或者我们假设我们的经典数据已经加载到了量子随机存取存储器（quantum random-access memory, qRAM）上，该存储器可以在对数时间内制备量子态 [24]。qRAM 也是一个令人生畏的挑战，不仅是从工程角度来看，在某些情况下，它还需要过多的错误校正才能有效地进行量子态制备 [25]。对称地，HHL的输出不是解向量x本身，而是一个量子态 |x〉，从中我们可以测量一些可观察的〈x|M|x〉。如果制备量子态 |b〉需要大量的量子门，比如指数级的量子比特数，或者如果我们需要对 |x〉进行指数级次数的测量来计算经典输出，那么量子加速就消失了。

Shor、Grover和HHL算法都假设有容错量子计算机 [26] 。事实上，我们可以构建的任何机器在执行量子操作时都会受到噪声的影响，错误是不可避免的：我们需要一种纠错码，它可以比出现的错误更快地纠正这些错误。这正是量子阈值定理（quantum threshold theorem）的内容 [27] ，该定理证明了在物理错误率低于某一阈值的情况下容错量子计算的可能性。这种量子纠错方案的一个值得注意的例子是Kitaev的复曲面编码 [28] 和拓扑量子计算的一般思想 [29]，这为“通过其物理性质”容错的量子计算机带来了长期的希望。然而，这种希望依赖于称为Majorana零模 (Majorana zero-modes) 的准粒子的存在，截至2021年，这种准粒子的存在尚未得到实验的验证 [30] 。

通往大规模容错量子计算的道路很可能是漫长的。那么与此同时，利用现有的含噪声的中等规模量子 (noisy intermediate-scale quantum, NISQ) 机器，我们可以在这个所谓的NISQ时代 [31] 做些什么呢？大多数答案涉及混合的经典-量子方法，其中经典的算法被用于优化量子态的制备[32]。突出的例子包括用于组合问题（如最大切割问题，Maximum cut）的量子近似优化算法（quantum approximate optimisation algorithm, QAOA [33]）和用于近似化学系统基态的变分量子本征求解器（variational quantum eigensolver, VQE [34]）。这些变分算法取决于根据问题的结构和可用资源，选择一种称为ansatz的参数化量子电路。一些ansätze族，如瞬时量子多项式时间（instantaneous quantum polynomial-time，IQP）电路，被认为即使在恒定深度下也很难被经典方法模拟 [35]，这为可能在近期实现NISQ加速打开了大门。

尽管混合方法最初出现在机器学习的背景下[36]，但使用参数化量子电路作为机器学习模型的想法在十年内几乎没有被注意到 [37]。直到它以量子神经网络 [38] 的名义被重新发现，然后在两个量子比特 [39] 上实现，为量子机器学习带来了新的关注浪潮。这个想法很简单：1）通过我们选择的ansatz将输入向量编码为量子态，2）再次通过某种选择的ansatz，初始化参数的随机向量，并将其编码为测量M_θ，3）选取概率作为模型的预测。然后，经典算法使用此量子预测作为子程序，以在某些诸如分类的数据驱动任务中，找到最优的参数θ。

使用参数化量子电路解决真实世界问题还面临许多挑战，其中之一就是所谓“贫瘠高原”的现象 (barren plateaus) [40]：使用随机电路作为ansatz，非零梯度的概率随着在量子比特的数量增长呈指数级的减少，经典优化的梯度丢失于平坦的“地形”中。人们不禁注意到这与二十年前提出的经典神经网络的消失梯度问题具有惊人的相似性 [41]。贫瘠高原不会出现在具有足够结构的电路（如量子卷积网络 [42]）中，它们也可以通过结构化初始化策略来缓解 [43]。另一个方向是完全避免梯度，并使用核方法[44]：我们使用NISQ器件来估计嵌入到我们ansatz的高维Hilbert空间中的输入向量对之间的距离，而不是学习测量M_θ。然后，我们使用经典的支持向量机来找到分离数据的最优超平面，理论上保证学习量子模型至少与变分方法一样好 [45]。

随机量子电路也许不适合机器学习，但它们对寻求量子优势发挥着至关重要的作用，即通过实验演示用量子计算机解决任何合理时间内无法用经典方法解决的任务。让我们回到费曼最初的直觉：从随机量子电路采样是这种任务（译者注：指模拟量子力学）的完美候选。2019年底，首次有人声称53量子比特的计算机具有这样的优势 [46]。这一说法几乎立即遭到了来自经典模拟的质疑，人们对54量子比特的电路进行了经典模拟，模拟采样时间仅仅只需要两天半[47]，随后的结果压缩到五分钟内[48]。Zhong等人[49] 以76光子的线性光学量子计算机提出新主张，然后是66量子比特计算机 [50l; 51]。他们估计，完成他们在几个小时内完成的采样任务的经典模拟至少需要一万年的时间。

如今，量子计算机被证明可以计算超越经典计算机的所能算东西，但问题仍然存在：它们可以计算一些有用的东西吗？

为什么我们要让NLP量子化？

一名女孩操作员用键盘以英语字符敲入以下俄文：“Mi pyeryedayem mislyi posryedstvom ryechi”。机器几乎同时打印翻译：“我们通过言语传播思想。”操作员不懂俄语。

纽约时报（1954年1月8日）

上一节提示了这样一个事实，即量子计算不能简单地更快地解决任何问题。量子计算机需要有一些可以利用的结构：物理模拟问题中自带的结构，或者Shor算法中密码协议的群论结构。

那么，我们为什么期望量子计算机在自然语言处理（NLP）方面有任何长处呢？本节将论证，自然语言与量子理论有着共同的结构，其形式有两个语言学的原则：组合性（compositionality）和分布性（distributionality）。

我们从1950年代图灵所提出的一个哲学问题[52] 来开启人工智能（AI）的历史：“机器能思考吗？”这个问题被重新表述为一个人机游戏，现在也被称为图灵测试。在游戏中，机器试图说服人类询问者它也是人类。为了让人和机器平起平坐，图灵建议只让他们通过书面语言进行交流：他的思想实验实际上定义了一个NLP任务。仅仅四年后，NLP就从哲学思考转向实验演示：IBM 701计算机成功地将俄语句子翻译成英语，如“他们用土豆生产酒精” [53]。这项首次的NLP实验只有六条语法规则和250个来自有机化学和其他一般话题的词汇，引起了公众广泛的关注，人们过分乐观地预测机器翻译是一种将在“五年内，也许三年” 被拿下的任务。

两年后， Chomsky [54; 55] 提出了自然语言语法模型的层次结构，它提示了为什么NLP不会这么快被解决。在他认为最适合研究自然语言的，最具表现力的模型中，（语法）分析问题（the parsing problem）实际上是图灵完备的。仅仅决定一个给定的单词序列是否符合语法就可以超越任何物理计算机的能力，就更不用说机器翻译了。Chomsky的分析问题实际是对Thue [56] 的一个旧问题的语言学上的重新解释，现在被称为幺半群的单词问题（word problem for monoids）（注12-1），并且被Post [57] 和Markov [58] 独立证明是不可判定的（undecidable）。这揭示了理论语言学、计算机科学和抽象代数之间的三向联系，这将贯穿本文的大部分内容。但是，如果我们有兴趣解决实际的NLP问题，为什么我们应该关心诸如形式文法（formal grammars）这样的抽象构造呢？

大多数有实际价值的NLP任务都涉及自然语言语义：我们希望机器计算句子的含义。给定一个句子的语法结构，我们可以将句子的意义作为该句子基本语词的意义的函数来计算。这就是所谓的组合原则（principle of compositionality），这是由Frege提出来的。（注释12-2）组合原则被蕴藏在Boole的《思维规律》（laws of thought） [59] 中，然后由Carnap [60] 加以明确。Montague [61；62；63] 随后将这个原则形式化为从语法代数（即文法，grammar）到语义代数（即逻辑）的同构（homomorphism）。他首次将组合性应用于语言学，认为“在自然语言与逻辑学家的人工语言之间，并没有重要的理论差异”。组合性成为NLP符号化方法的基础，也被称为有效的老式AI（good old-fashioned AI , GOFAI）[64]。单词的意义首先被编码为机器可读的格式，然后机器可以组合它们来回答复杂的问题。2011年，IBM 的计算机问答系统Watson在一档以问答形式为主的老牌电视智力竞赛节目《危险边缘》（Jeopardy!）中击败了一位人类冠军，意味着这种GOFAI方法达到了顶峰 [65]。

译注： 

• 部分表达式和复合表达式的意义：应用组合原则获得的复合表达式的意义不仅依赖部分表达式的意义，还需要把这些部分表达式的意义组合起来的方式，即复合表达式的意义是意义的运算函项对部分表达式的意义进行计算的产物；

 • 组合原则应用上的必要条件是，一是又组成复合表达式的部分表达式及其意义，二是把部分表达式的意义组成复合表达式意义的运算函项。（出自《逻辑语义学中的组合原则》）

同年，苹果公司在数百万用户的兜里（的智能设备）推出了他们的虚拟助手Siri，很快，互联网巨头亚马逊和谷歌也紧急跟进。虽然Siri、Alexa及其竞争者已经让NLP成为主流，但它们都没有显式地应用任何形式文法。这些下一代NLP机器的人工智能由深度神经网络和大数据机器学习所驱动，而不是像Watson这样的专家系统，基于复杂的文法分析和知识表示。尽管它们的架构越来越复杂，但这些神经网络实现了一个简单的统计概念：语言模型，即单词序列上的概率分布。与符号AI的复合性不同，这些统计方法依赖于另一个语言原则，即分布性（distributionality）：具有相似分布的单词具有相似的含义。

这一原则可以追溯到维特根斯坦（Wittgenstein）的《哲学研究》（Philosophical Investigations）：“一个词的意义就是它在语言中的使用”[66]，通常简称为“意义即使用” （meaning is use）。随后，它在计算语言学的背景下被Harris [67]，Weaver [68] 和Firth [69] 等人加以明确。Firth还创造了一句名言：“你可以透过与之搭配的单词来认识一个词！”（You shall know a word by the company it keeps!）向量空间模型 （vector space models）是深度神经网络接管这个领域之前，形式化分布性的标准方法[70]。我们有一组N个单词构成的一组M个文档中，我们只需计算每个单词在每个文档中出现的次数，就可以得到一个M×N矩阵。用像tf-idf算法（term frequency by inverse document frequency，词频-逆文档频率）这样的加权方法对矩阵进行归一化，并对其进行因子分解（例如，通过奇异值分解或非负矩阵因子分解），然后就完事了！这时，矩阵的列就编码了单词的含义，取其内积作为单词间相似性的度量，然后可以用于分类或聚类等任务。这种方法的优点是简单，而且它在从垃圾邮件检测到电影推荐的广泛应用中取得了令人惊讶的好效果[71]。它的主要不足之处是，这里，一个句子不是作为一个序列被表示的，而是“一袋”单词（a bag of words），无论语料库中包含的是“狗咬人”还是“人咬狗”，其词向量都是相同的。解决这一问题的一种标准方法是在计算向量时，不是计算一个个孤立的单词，而是取n个单词，即具有n个连续单词的窗口，n是某种固定大小的n。然而，这种方法又有其局限性：如果n太小，我们无法检测任何长程相关性；如果n太大，那么矩阵太稀疏，我们根本无法检测到任何东西。

相比之下，Rumelhart、Hinton和Williams[72]的递归神经网络（RNN）本质上是序贯的模型（即一个一个字符/单词地处理），它们的内部状态可以编码任意的长程相关性。在每一步，网络都会处理序列中的下一个单词，并更新其内部状态。然后，该内部存储器可以用于预测序列的其余部分，或者作为输入被馈送到另一个网络，例如用于翻译成另一种语言。一旦训练的障碍被克服（如上一节提到的梯度消失），各种RNN架构，如长短期记忆（LSTM）[73]等，便在各种NLP任务中创造了记录，如语言建模[74]、语音识别[75]和机器翻译[76]。RNN的纯串行的方法被证明是有局限的：只有当网络完成阅读时，即来自第一个单词的信息必须在整个文本中被传播，然后翻译才能进行。双向RNN [77] 通过从左到右和从右到左读取来解决此问题。尽管如此，从认知角度来看，它还是有点令人不满意的（既然人类能够理解文本而不需要从后向前阅读，为什么机器要这样做？），而且在需要一次处理一个单词的在线环境中也难堪大任。

注意力机制提供了一个更优雅的解决方案：我们再不需要假设一个单词的“同伴”是它的直接左右邻居，而是让神经网络自己学习哪些单词与哪些单词相关。注意力首先作为一种提高RNN在翻译任务上的性能的方法而引入 [78]，随后成为Transformer模型的基础[79]：完全不重复地处理序列的一组注意力机制。从BERT [80] 开始，各种transformer取代了RNN成为最先进的NLP模型，最终GPT-3语言生成模型在《卫报》[81]上发表了自己的文章：“一个机器人写出了这篇文章。你害怕了吗，人类？”

事实上，我们为什么要害怕？因为我们不知道机器人是如何写成这篇文章的，而且我们无法解释它数十亿个参数中的什么使它能够以这样的方式写文章。Transformer和神经网络一般都是黑盒：我们可以探索它们将输入映射到输出的方式，但如果我们查看其间TB级的权重，我们就无法解释映射。此外，没有可解释性，就没有公平性：如果我们不能解释其决策是如何做出的，我们就很难阻止网络复制数据集和数据科学家做出的假设中存在的歧视。我们认为，可解释的人工智能需要通过赋予分布黑盒一种可组合的结构来使其透明化：我们需要组合分布（compositional distributional, DisCo）模型来协调符号的GOFAI和深度学习。

DisCo模型的根源在于神经心理学而非人工智能。事实上，它们最初是作为大脑的模型出现的，而不是机器学习的架构。在McCullogh和Pitts的开创性工作[82]中，他们给出了神经网络的第一个正式定义，并展示了它们的“全有或全无”（all-or-nothing）的行为（注15-1）是如何编码命题逻辑的片段的。Hebb[83]随后介绍了解释学习和结构化感知的第一个生物学机制：“一起激发的神经元更倾向于连接在一起”（ neurons that fire together, wire together）。这些大脑的计算模型成为人工智能方法中的连接主义[84；85]和神经符号主义[86]的基础：高级的符号推理来自低级神经网络。一个有影响力的例子是Smolensky的张量积表示[87]，其中列表和树等离散结构被嵌入到两个向量空间的张量积中，一个用于变量，另一个用于值。更具体地，一个列表的n个d维向量x₁，…，x_n被表示成一个张量。Smolensky [87] 也是第一个将人工智能中组成结构的分布表示与量子物理的群表示进行类比的人。他认为，通过表示论（representation theory，这是范畴论的前身，我们将在下一节讨论）我们可以看到，符号结构嵌入神经网络的方式与粒子的对称性嵌入其状态空间的方式相同。

Clark和Pulman[88]提出将这种张量积表示应用于NLP，但他们注意到其主要缺点是：不同长度的列表不存在于同一空间，这使得其无法比较具有不同语法结构的句子。Clark、Coecke和Sadrzadeh的范畴组合分布（categorical compositional distributional, DisCoCat）模型 [89；90] 通过进一步类比量子化来克服了这一问题。词义和文法结构之于语言学，就像量子态和纠缠结构之于物理学一样。DisCoCat的词义存在于向量空间中，它们由张量积组成：量子理论的量子态也是如此。文法会告诉你，单词是如何连接的，信息是如何在句子中流动的，同样，纠缠的量子态会告诉你信息如何在复杂的量子系统中流动。这种类比允许借用量子理论中的成熟数学工具，在经典的硬件上实现，并在诸如句子比较[91]和词义消歧[92；93]的小规模任务上取得一些实证上的成功。然而，将句子的意义表示为量子过程是有代价的：经典地模拟它们可能面临指数级的困难。

如果DisCoCat模型对于经典计算机来说非常棘手，那么为什么不用量子计算机呢？Zeng和Coecke[94]用第一个量子自然语言处理（QNLP）算法（注16-1）证明了句子分类任务的二次方加速，回应了这个问题。Wieber等人[95]后来基于推广的张量积表示定义了一个QNLP算法，并证明它是BQP完全的：如果任何量子算法具有指数优势，那么原则上QNLP必须有其一个。然而，无论这两种算法多么有前途，它们都假定了容错性，并且至少与Grover和HHL一样，远离真实世界问题。

这就是本论文所做的工作：我们表明，在目前可用的机器上实现DisCoCat模型是可能的。作者和合作者[96；97]通过将DisCoCat模型转化为变分量子算法，为QNLP引入了第一个NISQ友好框架。然后，我们实现了这个框架，并在玩具问答任务上演示了第一个QNLP实验[98]，最近的实验在更大规模的分类任务上显示了实证上的成功[99]。我们的框架后来被应用于机器翻译[100；101]、词义消歧[102]甚至音乐生成[103]。未来的实验必须证明QNLP不仅仅是一个类比，它可以在有用的任务上获得量子优势。但在详细讨论我们的实现之前，我们必须使DisCoCat的类比形式化。

范畴论能提供什么帮助？

我仍然希望创造一种普遍的象征主义（spécieuse générale），在这种主义中，所有理性的真理都将被简化为一种微积分。——给尼古拉斯·雷蒙（Nicolas Remond）的信，莱布尼茨（1714）

“每个足够好的类比都渴望成为函子”[104]，我们将看到DisCoCat模型背后的类比确实是函子。Coecke等人[105]在他们的自然语言模型和拓扑量子场论（topological quantum field theories, TQFTs）之间进行了元类比（meta-analogy）。直观地说，时空区域和量子过程之间存在一个类比：两者都可以按串行或并行的方式组合。TQFTs将这种类比形式化：他们以尊重串行和并行的组合方式，将量子系统分配给每个空间区域，并将量子过程分配给每个时空区域。以相同的保持结构的方式，DisCoCat模型为每个语法类型分配一个向量空间，为每个语法类别分配一个线性映射。TQFTs和DisCoCat都可以根据范畴论给出一句话的定义：它们是向量空间范畴中函子的例子。

同样的“泛式抽象废话”（general abstract nonsense，范畴论的一个绰号）如何适用于量子引力和自然语言处理？而这种“废话”对QNLP算法的实现又有什么帮助呢？本节将介绍范畴论的历史及其在量子物理学和计算语言学中的应用，从元数学（meta-mathematics）的抽象框架到NLP量子硬件的具体工具箱。首先，关于“函子”和“范畴”这两个词的词源的简短哲学题外话将为它们在数学和语言学中的不同含义带来一些启示。

“函子” (functor) 一词首次出现在Carnap的《语言逻辑语法》（Logical syntax of language）[106]中，是这本现代教科书中用来描述一阶逻辑的函数符号。他将它们作为一种将物理学等经验科学定律简化为其形式逻辑的纯粹语法的方法，以温度函子T为例，使得T(3)=5意味着“位置3处的温度为5”（注17-1）。这一意思后来逐渐变成了虚词的同义词，如“这样”、“作为”、“与”等。这些词并不指世界上的任何事物，而是作为描述事物和行为的实义词汇之间的文法粘合剂。它们不到我们词汇的千分之一，但几乎占我们所说单词的一半[107]。

范畴（categories，来自古希腊的κατηγορία，“可以说的”）有着更古老的哲学历史。在亚里士多德（Aristotle）的著作《范畴篇》中，他首先区分了简单的言语形式（“不加任何组合地说”的事物，如“人”或“争论”）和组合的言语形式，如“人争论”。然后，他将简单，原子的事物分为十个范畴：“实体、数量、性质、关系、地点、时间、姿态、状况、活动、遭受”。亚里士多德如何得出这样一个列表，一个常见的解释[108]是，它来自于可能的问题类型：“它是什么？”的答案必须是一个实体，“多少？”的回答必须是一个数量，等等。尽管他把语言作为工具，但他的范畴体系旨在对世界上的事物进行分类，而不是对言语形式进行分类：作为一种本体论，而不是文法。

在《纯粹理性批判》[109]中，康德（Kant）重新审视了亚里士多德的体系，不仅对世界进行了分类，还对心灵进行了分类：他定义的是理解的范畴，而不是存在的范畴。每一个对象（无论是在世界上还是在头脑中）都是一种特定类型的对象，这一观点随后成为数理逻辑和罗素（Russell）类型论的基础[110]。同样的想法在语言学中也产生了巨大的影响，尤其是在由Ajdukiewicz[111]和BarHillel[112；113]开创的范畴文法传统中，范畴现在已经成为文法类型的同义词。正如我们将在第2.1.2节中看到，从亚里士多德范畴到范畴文法的关键创新在于文法类型现在具有某种结构：我们可以将原子范畴组合在一起，以形成复杂的类型，称为函子范畴，这可能有点使人混淆。

有别于范畴和函子在语言学中的应用，Eilenberg和MacLane的一系列论文[114；115；116]给出了它们当前的数学定义。受亚里士多德的事物范畴和康德的思想范畴的启发，他们将范畴定义为数学结构的类型：集合、群、空间等。他们最优秀的洞察是不再聚焦对象（元素、点等）的内容，而聚焦于它们之间箭头的组合：函数、同态、连续映射等。将同样的洞察力应用于范畴本身，真正重要的是它们之间的箭头：函子，从一个范畴到另一个范畴的映射，并保持箭头的形式。（注释18-1）

一个典型的例子是庞加莱（Poincaré）对拓扑空间的基本群的构造[117]，它可以被定义为从（被指向的）拓扑空间范畴到（它的）群范畴的函子：空间之间的每个连续映射都在其基本群之间以一种保留组合和单位元的方式引入同态。因此，范畴论的抽象使得拓扑和代数之间的类比形式化，使用另一种方法证明了一种方法的结果。然后它在Grothendieck的讨论班[118]中被用作代数几何基础的工具，它将几何形状和代数方程之间的类比带入了一个新的抽象层次，并引领了拓扑斯理论（topos theory）的发展。

范畴论作为一门独立学科和数学基础的建立，很大程度上归功于Lawvere的工作。在他关于函子语义（functorial semantics）的有很大影响的博士论文[119]中，他为模型理论（model theory）建立了一个框架，其中逻辑理论是范畴，其模型是函子。然后，他对集合范畴[120]和范畴的范畴[121]进行了公理化。由此产生的基本拓扑斯符号（notion of elementary topos）[122]包含了Grothendieck的定义，并强调了伴随（adjunction）的基本概念[123；124]。“伴随函子无处不在”成为MacLane的经典教科书《写给“工作数学家“的范畴》（Categories for the working mathematician）的标语[125]。Lambek[126；127；128]使用笛卡尔闭合范畴（cartesian closed categories）的相关概念将逻辑和计算之间的Curry Howard对应性扩展到具有范畴论的三位一体：证明和程序是箭头，逻辑公式和数据类型是对象。根据Scott[129]调查，正是这种三重联系的发现，导致了范畴论在理论计算机科学中的广泛应用。

在数学、逻辑和计算机科学的范畴被统一之后，物理学的范畴基础由Lawvere对经典动力学的拓扑学处理[130]和Schanuel的连续介质物理学[131]中萌发。正如我们在本节开头提到的，Atiyah[132]、Baez和Dolan[133]在TQFTs上的工作表明，范畴和函子是量子引力大统一（the grand unification project）[134]的重要工具。现在，物理学、数学、逻辑和计算之间的四元类比被Baez和Stay在他们的工作[135]中推广开来。在更具体的层次上，范畴论和量子物理学之间的联系出现在Selinger提出的量子编程语言[136]和量子lambda演算[137；138；139]中。同样的见解在Abramsky和Coecke[140]领导的范畴量子力学（categorical quantum mechanics, CQM）学派中得到了发展，其中量子过程是紧封闭范畴中的箭头。这种方法在Coecke和Duncan的ZX演算[141；142]中达到了顶峰，这是一种范畴的公理化，被证明完全适用于量子比特的量子计算[143；144]，应用包括纠错[145；146]、电路优化[147；148；149]、编译[150；151]和提取[152]。

也是在量子计算中，伴随（adjunction）是最基本的：它是纠缠定义的基础，也是传送协议（teleportation protocol）正确性证明的基础。早在2004年，当Coecke在McGill范畴论研讨会上首次提出这一结果时，Lambek立即指出了与他的《预群文法》（pregroup grammars） [153；154]的相似之处，其中的伴随是唯一的语法规则（注19-1）。半个世纪前，兰贝克演算（Lambek calculus）[155; 156; 157]揭示了范畴文法中的推导和数理逻辑中的证明树之间的类比。然后，他在《范畴和范畴文法》[158]中扩展了这一类比，在那里他证明了这些文法派生事实上是封闭幺半范畴中的箭头，并提出将蒙太古语义（Montague semantics）作为拓扑值函子（topos-valued functor）。后来，他认为不是“范畴应该在语言学中发挥作用，但事实上它们已经发挥了作用”[159]。事实上，Hotz[160]已经证明Chomsky的生成文法是自由的幺半群范畴，尽管他最初的德语文章从未被翻译成英语。使用函子作为语义的想法藏在Knuth [161]的上下文无关语言中，在Benson[162]的无限制文法得到明确描述。从语言学的这一范畴形式中，Lambek[163]首先提出了语言学和物理学之间的类比，这是本论文的基础：作为量子过程的预群化简（pregroup reductions as quantum processes）。

值得注意的是，Lambek可以在没有线图（string diagrams）的情况下预见QNLP（注20-1），而线图可能是应用范畴论学家手中最强大的工具。它们首次出现在Hotz[164]的另一篇文章中，作为电子领域常用图表的形式化。Penrose[165]随后使用了相同的符号作为繁琐的张量计算的非正式快捷方式，后来与Rindler[166]一起将其应用于相对论。Joyal和Street[167；168；169]给出了线图的第一个拓扑定义，并将其描述为自由幺半范畴（free monoidal categories）的箭头。Girard[170]引入了称为证明网络（proof nets）的线图的一般化，作为将其线性逻辑的证明从“语法官僚主义”（the bureaucracy of syntax）中解放出来的一种方式，然后将其应用于Lambek演算[171]及其多模态扩展[172]。

起初，线图是一种手工绘制在黑板上、很少出现在出版物中的数学“民间传说”，随着 Latex 和TikZ等排版工具的出现，线图开始以更大的规模被发表。Selinger的调查[173] 使范畴结构的层次结构（对称、紧凑闭合等）对应于一种图形化小工具的层次结构（交换、导线弯曲等）。在《描绘量子过程》（Picturing Quantum Processes）[174]中，Coecke和Kissinger用一千多张图介绍了量子理论。线图的应用清单正不断增长：电子学[175]和化学[176]，控制论[177]和并发[178]，数据库[179]和知识表示[180]，贝叶斯推断[181；182]和因果关系[183]，认知[184]和博弈论[185]，函数式编程[186]和机器学习[187]。

如果线图是撰写科学论文的好工具，那么它也可以成为开发软件应用程序的强大数据结构：quantomatic[188]及其后续PyZX[189]在ZX演算中自动重写这些图，Globalar[190]及其后续的homotopy.io[191]是高阶范畴论（higher category theory）的证明助手，cartographer [192] 和catlab [193]实现了对称幺半范畴的图，它也隐含编译器[194]的电路数据结构中。线图也是QNLP算法的主要数据结构：我们将句子的图翻译为量子电路图。由于现有的范畴论软件都不够灵活，我们不得不实现我们自己的软件：DisCoPy[195]，这是一个Python库，用于使用函子和幺半范畴中的图进行计算。DisCoPy随后成为lambeq[196]的基础引擎，这是一个实验性QNLP的高级库。尽管它的开发是由量子计算机上DisCoCat模型的实现推动的，但DisCoPy被设计为应用范畴论的通用工具包。它是自由获取的（注21-1）（作为免费软件和开源软件）、可靠的（100%的代码覆盖率），并具有丰富的文档（注21-2）。

总之，范畴论真的可以是任何事物的理论：从代数几何、量子引力到自然语言处理。范畴论和作为通用图形语言的线图，以及莱布尼茨三百年前所梦想的通用表意文字（characteristica universalis）和微积分推理机（calculus ratiocinator）有着惊人的相似之处，这是一种能够表达所有数学、科学和哲学的形式语言和计算框架。实际上，范畴不仅可以成为“工作数学家”（出自MacLane的经典教科书《写给“工作数学家“的范畴》，译者注）和科学家的工具，也可以帮助哲学家。在格拉斯曼（Grassmann）知名的《扩展的理论》（Ausdehungslehre） [197]和他的黑格尔代数形式化研究的足迹中，Lawvere [198；199；200；201] 着手从伴随（adjunctions）的角度阐述黑格尔辩证法。这促使Schreiber、Corfield和他们的合作者在nLab[202]上不断努力，以范畴论的角度“翻译”黑格尔的名著《逻辑学》（Wissenschaft Der Logik）[203]。范畴论不仅可以容纳黑格尔的绝对理想主义（absolute idealism），还可以处理皮尔士（Peirce）的实用主义（pragmatism）[204]，皮尔士独立于弗雷格（Frege）发展了一阶逻辑，在此过程中使用了后来被公认为第一个线图[205；206；207；208]。线图也被用于将维特根斯坦的语言游戏（language games）建模为从文法到游戏范畴的函子[209]。在最近的工作中[210]，我们将这些函子式语言游戏应用于问题回答，通过范畴论桥接哲学游戏和NLP。

脚注

注7-1：一个经典的随机算法以高概率在恒定时间内解决问题。

注8-1：预言机是一个黑盒，它允许图灵机在一个步骤中解决一个特定问题。

注8-2：输入承诺满足某个特定属性，这可能很难检查。

注8-3：以其发现者Harrow、Hassidim和Lloyd命名。

注9-1：BQP完全问题是一个多项式时间等价于电路模型的问题，这是量子计算机在多项式时间内以有界误差解决的最困难的问题。

注12-1：历史上，Thue、Markov和Post都在研究半群，即无单位幺半群。

注12-2：Frege的任何发表中都没有出现组合性（Compositionality）这个词[211]。然而，Frege确实阐述了所谓的“语境原则”（context principle）：“句子作为一个整体有意义就足够了，它的某个部分会因此获得意义”。这可以被视为一种组合的双重性：单词的含义是句子含义的函数。

注15-1：无论刺激强度如何，神经元的反应要么最大，要么为零。

注16-1：我们排除了以前受量子理论启发但在经典计算机上运行的算法，如Chen[212]和Blacoe等人[213]的框架。

注17-1:MacLane[214]随后会指出，Carnap的形式语言不能表达位置的坐标系，也不能表达测量温度的尺度。

注18-1：我们可以再次玩同样的游戏：重要的不是函子本身，而是它们之间的自然转换，这就是范畴论最初要定义的。如果继续这个游戏，就掉进了无限范畴论这个无底洞 [215]。

注19-1：有关这个故事的第一手描述和对Jim Lambek的赞扬，请参见[216]。

注20-1：Lambek发表的任何作品中都没有出现线图。相反，他要么使用方程组、证明树，要么使用“下连线”表示准群（pregroup）的伴随[217]。他承认他“没有耐心吸收”Joya-Street线图的拓扑定义[218]。

注21-1：https://github.com/oxford-quantum-group/discopy

注21-2：https://discopy.readthedocs.io/

参考文献

[1] Paul Benioff. “The Computer as a Physical System: A Microscopic Quantum Mechanical Hamiltonian Model of Computers as Represented by Turing Machines”. In: Journal of Statistical Physics 22.5 (May 1, 1980), pp. 563–591. doi: 10.1007/BF01011339.[2] Yuri Manin. “Computable and Uncomputable”. In: Sovetskoye Radio, Moscow 128 (1980).[3] Richard P. Feynman. “Simulating Physics with Computers”. In: International Journal of Theoretical Physics 21.6 (June 1, 1982), pp. 467–488. doi: 10.1007/BF02650179.[4] Richard P Feynman. “Quantum Mechanical Computers”. In: Optics news 11.2 (1985), pp. 11–20. url: http://www.mathweb.zju.edu.cn:8080/wjd/notespapers/F.pdf.[5] David Deutsch. “Quantum Theory, the Church–Turing Principle and the Universal Quantum Computer”. In: Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences 400.1818 (1985), pp. 97–117.[6] David Deutsch and Richard Jozsa. “Rapid Solution of Problems by Quantum Computation”. In: Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences 439.1907 (Dec. 8, 1992), pp. 553–558. doi: 10.1098/rspa.1992.0167.[7] D. Simon. “On the Power of Quantum Computation”. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. Los Alamitos, CA, USA: IEEE Computer Society, Nov. 1994, pp. 116–123. doi: 10.1109/SFCS.1994.365701.[8] P.W. Shor. “Algorithms for Quantum Computation: Discrete Logarithms and Factoring”. In: Proceedings 35th Annual Symposium on Foundations of Computer Science. 35th Annual Symposium on Foundations of Computer Science. Santa Fe, NM, USA: IEEE Comput. Soc. Press, 1994, pp. 124–134. doi: 10.1109/SFCS.1994.365700.[9] Lov K. Grover. “Quantum Mechanics Helps in Searching for a Needle in a Haystack”. In: Physical Review Letters 79.2 (July 14, 1997), pp. 325–328. doi: 10.1103/PhysRevLett.79.325. arXiv: quant-ph/9706033.[10] Daniel J Bernstein, Johannes Buchmann, and Erik Dahmén. Post-Quantum Cryptography. Berlin: Springer, 2009.[11] A. Ambainis. “Quantum Search Algorithms”. In: ACM SIGACT News 35.2 (June 1, 2004), pp. 22–35. doi: 10.1145/992287.992296.[12] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. “Strengths and Weaknesses of Quantum Computing”. In: SIAM Journal on Computing 26.5 (Oct. 1, 1997), pp. 1510–1523. doi: 10.1137/S0097539796300933.[13] Isaac L. Chuang, Neil Gershenfeld, and Mark Kubinec. “Experimental Implementation of Fast Quantum Searching”. In: Physical Review Letters 80.15 (Apr. 13, 1998), pp. 3408–3411. doi: 10.1103/PhysRevLett.80.3408.[14] A. Yu Kitaev. “Quantum Measurements and the Abelian Stabilizer Problem”. In: ArXiv e-prints (Nov. 20, 1995). arXiv: quant-ph/9511026.[15] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. “Quantum Amplitude Amplification and Estimation”. In: ArXiv e-prints 305 (2002), pp. 53–74. doi: 10.1090/conm/305/05215. arXiv: quant-ph/0005055.[16] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. “Quantum Algorithm for Linear Systems of Equations”. In: Physical Review Letters 103.15 (Oct. 7, 2009), p. 150502. doi: 10.1103/PhysRevLett.103.150502.[17] Nathan Wiebe, Daniel Braun, and Seth Lloyd. “Quantum Algorithm for Data Fitting”. In: Physical Review Letters 109.5 (Aug. 2, 2012), p. 050505. doi: 10.1103/PhysRevLett.109.050505.[18] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. “Quantum Algorithms for Supervised and Unsupervised Machine Learning”. In: ArXiv e-prints (Nov. 4, 2013). arXiv: 1307.0411.[19] Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. “Quantum Support Vector Machine for Big Data Classification”. In: Physical Review Letters 113.13 (Sept. 25, 2014), p. 130503. doi: 10.1103/PhysRevLett.113.130503.[20] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. “Quantum Principal Component Analysis”. In: Nature Physics 10.9 (Sept. 2014), pp. 631–633. doi: 10.1038/nphys3029. arXiv: 1307.0401.[21] Iordanis Kerenidis and Anupam Prakash. “Quantum Recommendation Systems”. In: ArXiv e-prints (Mar. 29, 2016). arXiv: 1603.08675.[22] Scott Aaronson. “Read the Fine Print”. In: Nature Physics 11.4 (4 Apr. 2015), pp. 291–293. doi: 10.1038/nphys3272.[23] B. D. Clader, B. C. Jacobs, and C. R. Sprouse. “Preconditioned Quantum Linear System Algorithm”. In: Physical Review Letters 110.25 (June 18, 2013), p. 250504. doi: 10.1103/PhysRevLett.110.250504.[24] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. “Quantum Random Access Memory”. In: Physical Review Letters 100.16 (Apr. 21, 2008), p. 160501. doi: 10.1103/PhysRevLett.100.160501.[25] Srinivasan Arunachalam, Vlad Gheorghiu, Tomas Jochym-O’Connor, Michele Mosca, and Priyaa Varshinee Srinivasan. “On the Robustness of Bucket Brigade Quantum RAM”. In: New Journal of Physics 17.12 (Dec. 7, 2015), p. 123010. doi: 10.1088/1367-2630/17/12/123010.[26] Peter W Shor. “Fault-Tolerant Quantum Computation”. In: Proceedings of 37th Conference on Foundations of Computer Science. IEEE. 1996, pp. 56–65.[27] Dorit Aharonov and Michael Ben-Or. “Fault-Tolerant Quantum Computation with Constant Error Rate”. In: SIAM Journal on Computing 38.4 (Jan. 1, 2008), pp. 1207–1282. doi: 10.1137/S0097539799359385.[28] A. Yu. Kitaev. “Fault-Tolerant Quantum Computation by Anyons”. In: Annals of Physics 303.1 (Jan. 1, 2003), pp. 2–30. doi: 10.1016/S0003-4916(02)00018-0.[29] Michael Freedman, Alexei Kitaev, Michael Larsen, and Zhenghan Wang. “Topological Quantum Computation”. In: Bulletin of the American Mathematical Society 40.1 (2003), pp. 31–38.[30] Philip Ball. Major Quantum Computing Strategy Suffers Serious Setbacks. Quanta Magazine. url: https://www.quantamagazine.org/majorquantum-computing-strategy-suffers-serious-setbacks-20210929/ (visited on 10/26/2021).[31] John Preskill. “Quantum Computing in the NISQ Era and Beyond”. In: Quantum 2 (Aug. 6, 2018), p. 79. doi: 10.22331/q-2018-08-06-79.[32] Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik. “The Theory of Variational Hybrid Quantum-Classical Algorithms”. In: New Journal of Physics 18.2 (Feb. 4, 2016), p. 023023. doi: 10.1088/1367-2630/18/2/023023.[33] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. “A Quantum Approximate Optimization Algorithm”. In: ArXiv e-prints (Nov. 14, 2014). arXiv: 1411.4028.[34] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O’Brien. “A Variational Eigenvalue Solver on a Photonic Quantum Processor”. In: Nature Communications 5.1 (1 July 23, 2014), p. 4213. doi: 10.1038/ncomms5213.[35] Dan Shepherd and Michael J. Bremner. “Temporally Unstructured Quantum Computation”. In: Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 465.2105 (May 8, 2009), pp. 1413–1439. doi: 10.1098/rspa.2008.0443.[36] Jeongho Bang, James Lim, M. S. Kim, and Jinhyoung Lee. “Quantum Learning Machine”. In: ArXiv e-prints (Mar. 31, 2008). arXiv: 0803.2976.[37] Marcello Benedetti, Erika Lloyd, and Stefan H. Sack. “Parameterized Quantum Circuits as Machine Learning Models”. In: CoRR abs/1906.07682 (2019). arXiv: 1906.07682.[38] Edward Farhi and Hartmut Neven. “Classification with Quantum Neural Networks on Near Term Processors”. Version 2. In: ArXiv e-prints (Aug. 30, 2018). arXiv: 1802.06002.[39] Vojtech Havlicek, Antonio D. Córcoles, Kristan Temme, Aram W. Harrow, Abhinav Kandala, Jerry M. Chow, and Jay M. Gambetta. “Supervised Learning with Quantum Enhanced Feature Spaces”. In: Nature 567.7747 (Mar. 2019), pp. 209–212. doi: 10.1038/s41586-019-0980-2. arXiv: 1804.11326.[40] Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven. “Barren Plateaus in Quantum Neural Network Training Landscapes”. In: Nature Communications 9.1 (Dec. 2018), p. 4812. doi: 10.1038/s41467-018-07090-4. arXiv: 1803.11173.[41] Sepp Hochreiter. “The Vanishing Gradient Problem During Learning Recurrent Neural Nets and Problem Solutions”. In: International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 06.02 (Apr. 1998), pp. 107–116. doi: 10.1142/S0218488598000094.[42] Arthur Pesah, M. Cerezo, Samson Wang, Tyler Volkoff, Andrew T. Sornborger, and Patrick J. Coles. “Absence of Barren Plateaus in Quantum Convolutional Neural Networks”. In: Physical Review X 11.4 (Oct. 15, 2021), p. 041011. doi: 10.1103/PhysRevX.11.041011.[43] Edward Grant, Leonard Wossnig, Mateusz Ostaszewski, and Marcello Benedetti. “An Initialization Strategy for Addressing Barren Plateaus in Parametrized Quantum Circuits”. In: Quantum 3 (Dec. 9, 2019), p. 214. doi: 10.22331/q-2019-12-09-214.[44] Maria Schuld and Nathan Killoran. “Quantum Machine Learning in Feature Hilbert Spaces”. In: Physical Review Letters 122.4 (Feb. 1, 2019), p. 040504. doi: 10.1103/PhysRevLett.122.040504. arXiv: 1803.07128.[45] Maria Schuld. “Quantum Machine Learning Models Are Kernel Methods”. In: ArXiv e-prints (Jan. 26, 2021). arXiv: 2101.11020.[46] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P. Harrigan, Michael J. Hartmann, Alan Ho, Markus Hoffmann, Trent Huang, Travis S. Humble, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V. Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandrà, Jarrod R. McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C. Platt, Chris Quintana, Eleanor G. Rieffel, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Kevin J. Sung, Matthew D. Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, and John M. Martinis. “Quantum Supremacy Using a Programmable Superconducting Processor”. In: Nature 574.7779 (7779 Oct. 2019), pp. 505–510. doi: 10.1038/s41586-019-1666-5.[47] Edwin Pednault, John A. Gunnels, Giacomo Nannicini, Lior Horesh, and Robert Wisnieff. “Leveraging Secondary Storage to Simulate Deep 54-Qubit Sycamore Circuits”. In: ArXiv e-prints (Oct. 22, 2019). arXiv: 1910.09534.[48] Yong, Liu, Xin, Liu, Fang, Li, Haohuan Fu, Yuling Yang, Jiawei Song, Pengpeng Zhao, Zhen Wang, Dajia Peng, Huarong Chen, Chu Guo, Heliang Huang, Wenzhao Wu, and Dexun Chen. “Closing the "Quantum Supremacy" Gap: Achieving Real-Time Simulation of a Random Quantum Circuit Using a New Sunway Supercomputer”. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (Nov. 14, 2021), pp. 1–12. doi: 10.1145/3458817.3487399. arXiv: 2110.14502.[49] Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, Peng Hu, Xiao-Yan Yang, Wei-Jun Zhang, Hao Li, Yuxuan Li, Xiao Jiang, Lin Gan, Guangwen Yang, Lixing You, Zhen Wang, Li Li, Nai-Le Liu, Chao-Yang Lu, and Jian-Wei Pan. “Quantum Computational Advantage Using Photons”. In: Science 370.6523 (Dec. 18, 2020), pp. 1460–1463. doi: 10.1126/science.abe8770. arXiv: 2012.01625.[50] Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han, Linyin Hong, He-Liang Huang, Yong-Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chun Lin, Jin Lin, Haoran Qian, Dan Qiao, Hao Rong, Hong Su, Lihua Sun, Liangyuan Wang, Shiyu Wang, Dachao Wu, Yu Xu, Kai Yan, Weifeng Yang, Yang Yang, Yangsen Ye, Jianghan Yin, Chong Ying, Jiale Yu, Chen Zha, Cha Zhang, Haibin Zhang, Kaili Zhang, Yiming Zhang, Han Zhao, Youwei Zhao, Liang Zhou, Qingling Zhu, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu, and Jian-Wei Pan. “Strong Quantum Computational Advantage Using a Superconducting Quantum Processor”. In: Physical Review Letters 127.18 (Oct. 25, 2021), p. 180501. doi: 10.1103/PhysRevLett.127.180501.[51] Qingling Zhu, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han, Linyin Hong, He-Liang Huang, Yong-Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chun Lin, Jin Lin, Haoran Qian, Dan Qiao, Hao Rong, Hong Su, Lihua Sun, Liangyuan Wang, Shiyu Wang, Dachao Wu, Yulin Wu, Yu Xu, Kai Yan, Weifeng Yang, Yang Yang, Yangsen Ye, Jianghan Yin, Chong Ying, Jiale Yu, Chen Zha, Cha Zhang, Haibin Zhang, Kaili Zhang, Yiming Zhang, Han Zhao, Youwei Zhao, Liang Zhou, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu, and Jian-Wei Pan. “Quantum Computational Advantage via 60-Qubit 24-Cycle Random Circuit Sampling”. In: Science Bulletin (Oct. 25, 2021). doi: 10.1016/j.scib.2021.10.017.[52] A. M. Turing. “Computing Machinery and Intelligence”. In: Mind LIX.236 (Oct. 1, 1950), pp. 433–460. doi: 10.1093/mind/LIX.236.433.[53] W John Hutchins. “The Georgetown-Ibm Experiment Demonstrated in January 1954”. In: Conference of the Association for Machine Translation in the Americas. Springer. 2004, pp. 102–114[54] Noam Chomsky. “Three Models for the Description of Language”. In: IRE Transactions on Information Theory 2.3 (Sept. 1956), pp. 113–124. doi: 10.1109/TIT.1956.1056813.[55] Noam Chomsky. Syntactic Structures. The Hague: Mouton and Co., 1957.[56] Axel Thue. “Probleme Über Veränderungen von Zeichenreihen Nach Gegebenen Regeln.” In: Natur. KI 10 (1914).[57] Emil L. Post. “Recursive Unsolvability of a Problem of Thue”. In: Journal of Symbolic Logic 12.1 (Mar. 1947), pp. 1–11. doi: 10.2307/2267170.[58] A Markov. “On Certain Insoluble Problems Concerning Matrices”. In: Doklady Akad. Nauk SSSR. Vol. 57. 6. 1947, pp. 539–542.[59] George Boole. An Investigation of the Laws of Thought on Which Are Founded the Mathematical Theories of Logic and Probabilities. In collab. with University of California Libraries. London : Walton and Maberly, 1854. 450 pp. url: http://archive.org/details/investigationofl00boolrich (visited on 09/07/2019).[60] Rudolf Carnap. Meaning and Necessity: A Study in Semantics and Modal Logic. University of Chicago Press, 1947.[61] Richard Montague. “English as a Formal Language”. In: Formal Philosophy. Selected Papers of Richard Montague. Ed. by R.H. Thomason. Yale University Press, New Haven, 1974, pp. 188–221.[62] Richard Montague. “Universal Grammar”. In: Theoria 36.3 (1970), pp. 373–398. doi: 10.1111/j.1755-2567.1970.tb00434.x.[63] Richard Montague. “The Proper Treatment of Quantification in Ordinary English”. In: Approaches to Natural Language (1973). Ed. by K. J. J. Hintikka, J. Moravcsic, and P. Suppes, pp. 221–242.[64] John Haugeland. Artificial Intelligence: The Very Idea. MIT press, 1989.[65] Adam Lally and Paul Fodor. “Natural Language Processing with Prolog in the IBM Watson System”. In: The Association for Logic Programming (ALP) Newsletter 9 (2011).[66] Ludwig Wittgenstein. Philosophical Investigations. Oxford: Basil Blackwell, 1953.[67] Zellig S. Harris. “Distributional Structure”. In: WORD 10.2-3 (Aug. 1, 1954), pp. 146–162. doi: 10.1080/00437956.1954.11659520.[68] Warren Weaver. “Translation”. In: Machine translation of languages 14.15-23 (1955), p. 10.[69] John R Firth. “A Synopsis of Linguistic Theory, 1930-1955”. In: Studies in linguistic analysis (1957).[70] G. Salton, A. Wong, and C. S. Yang. “A Vector Space Model for Automatic Indexing”. In: Commun. ACM 18.11 (1975), pp. 613–620. doi: 10.1145/361219.361220.[71] P. D. Turney and P. Pantel. “From Frequency to Meaning: Vector Space Models of Semantics”. In: Journal of Artificial Intelligence Research 37 (Feb. 27, 2010), pp. 141–188. doi: 10.1613/jair.2934.[72] David E. Rumelhart, Geoffrey E. Hinton, and Ronald J. Williams. “Learning Representations by Back-Propagating Errors”. In: Nature 323.6088 (6088 Oct. 1986), pp. 533–536. doi: 10.1038/323533a0.[73] Sepp Hochreiter and Jürgen Schmidhuber. “Long Short-term Memory”. In: Neural computation 9 (Dec. 1, 1997), pp. 1735–80. doi: 10.1162/neco.1997.9.8.1735.[74] Ilya Sutskever, James Martens, and Geoffrey E Hinton. “Generating Text with Recurrent Neural Networks”. In: ICML. 2011.[75] Alex Graves, Abdel-rahman Mohamed, and Geoffrey Hinton. “Speech Recognition with Deep Recurrent Neural Networks”. In: 2013 IEEE International Conference on Acoustics, Speech and Signal Processing. Ieee. 2013, pp. 6645–6649.[76] Ilya Sutskever, Oriol Vinyals, and Quoc V Le. “Sequence to Sequence Learning with Neural Networks”. In: Advances in Neural Information Processing Systems. Vol. 27. Curran Associates, Inc., 2014. url: https://proceedings.neurips.cc/paper/2014/hash/ a14ac55a4f27472c5d894ec1c3c743d2-Abstract.html (visited on 11/22/2021).[77] M. Schuster and K.K. Paliwal. “Bidirectional Recurrent Neural Networks”. In: IEEE Transactions on Signal Processing 45.11 (Nov. 1997), pp. 2673–2681. doi: 10.1109/78.650093.[78] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. “Neural Machine Translation by Jointly Learning to Align and Translate”. In: 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings. Ed. by Yoshua Bengio and Yann LeCun. 2015. url: http://arxiv.org/abs/1409.0473.[79] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. “Attention Is All You Need”. In: ArXiv e-prints (Dec. 5, 2017). arXiv: 1706.03762.[80] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. “BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding”. In: Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume 1 (Long and Short Papers). Ed. by Jill Burstein, Christy Doran, and Thamar Solorio. Association for Computational Linguistics, 2019, pp. 4171–4186. doi: 10.18653/v1/n19-1423.[81] GPT-3. “A Robot Wrote This Entire Article. Are You Scared yet, Human?” In: The Guardian. Opinion (Sept. 8, 2020). url: https://www.theguardian.com/commentisfree/2020/sep/08/robotwrote-this-article-gpt-3 (visited on 11/19/2021).[82] Warren S McCulloch and Walter Pitts. “A Logical Calculus of the Ideas Immanent in Nervous Activity”. In: The bulletin of mathematical biophysics 5.4 (1943), pp. 115–133.[83] Donald Olding Hebb. The Organisation of Behaviour: A Neuropsychological Theory. Science Editions New York, 1949.[84] P. Smolensky. “Connectionist AI, Symbolic AI, and the Brain”. In: Artificial Intelligence Review 1.2 (1987), pp. 95–109. doi: 10.1007/BF00130011.[85] Paul Smolensky. “On the Proper Treatment of Connectionism”. In: Behavioral and Brain Sciences 11.1 (Mar. 1988), pp. 1–23. doi: 10.1017/S0140525X00052432.[86] Melanie Hilario. “An Overview of Strategies for Neurosymbolic Integration”. In: Connectionist-Symbolic Integration: From Unified to Hybrid Approaches (1997), pp. 13–36.[87] Paul Smolensky. “Tensor Product Variable Binding and the Representation of Symbolic Structures in Connectionist Systems”. In: Artificial Intelligence 46.1 (Nov. 1, 1990), pp. 159–216. doi: 10.1016/0004-3702(90)90007-M.[88] Stephen Clark and Stephen Pulman. “Combining Symbolic and Distributional Models of Meaning”. In: Quantum Interaction, Papers from the 2007 AAAI Spring Symposium, Technical Report SS-07-08, Stanford, California, USA, March 26-28, 2007. AAAI, 2007, pp. 52–55. url: http: //www.aaai.org/Library/Symposia/Spring/2007/ss07-08-008.php.[89] Stephen Clark, Bob Coecke, and Mehrnoosh Sadrzadeh. “A Compositional Distributional Model of Meaning”. In: Proceedings of the Second Symposium on Quantum Interaction (QI-2008). 2008, pp. 133–140.[90] Stephen Clark, Bob Coecke, and Mehrnoosh Sadrzadeh. “Mathematical Foundations for a Compositional Distributional Model of Meaning”. In: A Festschrift for Jim Lambek. Ed. by J. van Benthem and M. Moortgat. Vol. 36. Linguistic Analysis. 2010, pp. 345–384. arXiv: 1003.4394.[91] Edward Grefenstette, Mehrnoosh Sadrzadeh, Stephen Clark, Bob Coecke, and Stephen Pulman. “Concrete Sentence Spaces for Compositional Distributional Models of Meaning”. In: Proceedings of the Ninth International Conference on Computational Semantics, IWCS 2011, January 12-14, 2011, Oxford, UK. Ed. by Johan Bos and Stephen Pulman. The Association for Computer Linguistics, 2011. arXiv: 1101.0309.[92] Edward Grefenstette and Mehrnoosh Sadrzadeh. “Experimental Support for a Categorical Compositional Distributional Model of Meaning”. In: Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, EMNLP 2011, 27-31 July 2011, John McIntyre Conference Centre, Edinburgh, UK, A Meeting of SIGDAT, a Special Interest Group of the ACL. ACL, 2011, pp. 1394–1404. arXiv: 1106.4058.[93] Dimitri Kartsaklis, Mehrnoosh Sadrzadeh, and Stephen Pulman. “Separating Disambiguation from Composition in Distributional Semantics”. In: Proceedings of the Seventeenth Conference on Computational Natural Language Learning, CoNLL 2013, Sofia, Bulgaria, August 8-9, 2013. Ed. by Julia Hockenmaier and Sebastian Riedel. ACL, 2013, pp. 114–123. url: https://aclanthology.org/W13-3513/.[94] William Zeng and Bob Coecke. “Quantum Algorithms for Compositional Natural Language Processing”. In: Electronic Proceedings in Theoretical Computer Science 221 (Aug. 2, 2016), pp. 67–75. doi: 10.4204/EPTCS.221.8. arXiv: 1608.01406.[95] Nathan Wiebe, Alex Bocharov, Paul Smolensky, Matthias Troyer, and Krysta M. Svore. “Quantum Language Processing”. In: ArXiv e-prints (Feb. 13, 2019). arXiv: 1902.05162.[96] Konstantinos Meichanetzidis, Stefano Gogioso, Giovanni de Felice, Nicolò Chiappori, Alexis Toumi, and Bob Coecke. “Quantum Natural Language Processing on Near-Term Quantum Computers”. In: Proceedings 17th International Conference on Quantum Physics and Logic, QPL 2020, Paris, France, June 2 - 6, 2020. Ed. by Benoît Valiron, Shane Mansfield, Pablo Arrighi, and Prakash Panangaden. Vol. 340. EPTCS. 2020, pp. 213–229. doi: 10.4204/EPTCS.340.11. arXiv: 2005.04147.[97] Bob Coecke, Giovanni de Felice, Konstantinos Meichanetzidis, and Alexis Toumi. “Foundations for Near-Term Quantum Natural Language Processing”. In: ArXiv e-prints (2020). arXiv: 2012.03755.[98] Konstantinos Meichanetzidis, Alexis Toumi, Giovanni de Felice, and Bob Coecke. “Grammar-Aware Question-Answering on Quantum Computers”. In: ArXiv e-prints (2020). arXiv: 2012.03756.[99] Robin Lorenz, Anna Pearson, Konstantinos Meichanetzidis, Dimitri Kartsaklis, and Bob Coecke. “QNLP in Practice: Running Compositional Models of Meaning on a Quantum Computer”. In: ArXiv e-prints (Feb. 25, 2021). arXiv: 2102.12846.[100] Mina Abbaszade, Vahid Salari, Seyed Shahin Mousavi, Mariam Zomorodi, and Xujuan Zhou. “Application of Quantum Natural Language Processing for Language Translation”. In: IEEE Access 9 (2021), pp. 130434–130448. doi: 10.1109/ACCESS.2021.3108768.[101] Irene Vicente Nieto. Towards Machine Translation with Quantum Computers. 2021. url: http://urn.kb.se/resolve?urn=urn:nbn:se:su:diva-196602 (visited on 12/02/2021).[102] Thomas Hoffmann. “Quantum Models for Word- Sense Disambiguation”. In: (2021). url: https://odr.chalmers.se/handle/20.500.12380/302687 (visited on 12/02/2021).[103] Eduardo Reck Miranda, Richie Yeung, Anna Pearson, Konstantinos Meichanetzidis, and Bob Coecke. “A Quantum Natural Language Processing Approach to Musical Intelligence”. In: ArXiv e-prints (Nov. 10, 2021). arXiv: 2111.06741.[104] John Baez. “Quantum Quandaries: A Category-Theoretic Perspective”. In: The Structural Foundations of Quantum Gravity. Oxford: Oxford University Press, 2006. doi: 10.1093/acprof:oso/9780199269693.003.0008.[105] Bob Coecke, Edward Grefenstette, and Mehrnoosh Sadrzadeh. “Lambek vs. Lambek: Functorial Vector Space Semantics and String Diagrams for Lambek Calculus”. In: Ann. Pure Appl. Log. 164.11 (2013), pp. 1079–1100. doi: 10.1016/j.apal.2013.05.009. arXiv: 1302.0393.[106] Rudolf Carnap. Logical Syntax of Language. London: Kegan Paul and Co., Ltd, 1937.[107] Cindy Chung and James Pennebaker. “The Psychological Functions of Function Words”. In: Social communication (Jan. 1, 2007).[108] G. Ryle. “Categories”. In: Proceedings of the Aristotelian Society 38 (1937), pp. 189–206. JSTOR: 4544305.[109] Immanuel Kant. Critique of Pure Reason. Trans. by Norman Kemp Smith. Read Books Ltd. (2011), 1781.[110] Bertrand Russell. The Principles of Mathematics. Routledge, 1903.[111] Kazimierz Ajdukiewicz. “Die Syntaktische Konnexität”. In: Studia Philosophica (1935), pp. 1–27.[112] Yehoshua Bar-Hillel. “A Quasi-Arithmetical Notation for Syntactic Description”. In: Language 29.1 (Jan. 1953), pp. 47–58. doi: 10.2307/410452. JSTOR: 410452.[113] Yehoshua Bar-Hillel. “Logical Syntax and Semantics”. In: Language 30.2 (Apr. 1954), p. 230. doi: 10.2307/410265. JSTOR: 410265.[114] Samuel Eilenberg and Saunders MacLane. “Group Extensions and Homology”. In: Annals of Mathematics 43.4 (1942), pp. 757–831. doi: 10.2307/1968966. JSTOR: 1968966.[115] Samuel Eilenberg and Saunders MacLane. “Natural Isomorphisms in Group Theory”. In: Proceedings of the National Academy of Sciences of the United States of America 28.12 (1942), p. 537.[116] Samuel Eilenberg and Saunders MacLane. “General Theory of Natural Equivalences”. In: Transactions of the American Mathematical Society 58 (1945), pp. 231–294. doi: 10.1090/S0002-9947-1945-0013131-6.[117] Henri Poincaré. Analysis Situs. Gauthier-Villars Paris, France, 1895.[118] Alexandre Grothendieck and Jean Dieudonné. “Eléments de Géométrie Algébrique”. In: Publications Mathématiques de l’Institut des Hautes Études Scientifiques 4.1 (1960), pp. 5–214.[119] F. William Lawvere. “Functorial Semantics of Algebraic Theories”. In: Proceedings of the National Academy of Sciences of the United States of America 50.5 (1963), pp. 869–872. JSTOR: 71935.[120] F William Lawvere. “An Elementary Theory of the Category of Sets”. In: Proceedings of the National academy of Sciences of the United States of America 52.6 (1964), p. 1506.[121] F. William Lawvere. “The Category of Categories as a Foundation for Mathematics”. In: Proceedings of the Conference on Categorical Algebra. Ed. by S. Eilenberg, D. K. Harrison, S. MacLane, and H. Röhrl. Springer Berlin Heidelberg, 1966, pp. 1–20.[122] F William Lawvere. “Quantifiers and Sheaves”. In: Actes Du Congres International Des Mathematiciens, Nice. Vol. 1. 1970, pp. 329–334[123] F. William Lawvere. “Adjointness in Foundations”. In: Dialectica 23.34 (1969), pp. 281–296. doi: 10.1111/j.1746-8361.1969.tb01194.x.[124] F. William Lawvere. “Equality in Hyperdoctrines and the Comprehension Schema as an Ad-Joint Functor”. In: 1970.[125] Saunders MacLane. Categories for the Working Mathematician. Graduate Texts in Mathematics. Springer New York, 1971. url: https://books.google.fr/books?id=eBvhyc4z8HQC.[126] Joachim Lambek. “Deductive Systems and Categories”. In: Mathematical Systems Theory 2.4 (1968), pp. 287–318.[127] Joachim Lambek. “Deductive Systems and Categories II. Standard Constructions and Closed Categories”. In: Category Theory, Homology Theory and Their Applications I. Springer, 1969, pp. 76–122.[128] Joachim Lambek. “Deductive Systems and Categories III. Cartesian Closed Categories, Intuitionist Propositional Calculus, and Combinatory Logic”. In: Toposes, Algebraic Geometry and Logic. Springer, 1972, pp. 57–82.[129] Phill J Scott. “Some Aspects of Categories in Computer Science”. In: Handbook of Algebra. Vol. 2. Elsevier, 2000, pp. 3–77.[130] F William Lawvere. “Categorical Dynamics”. In: Topos theoretic methods in geometry 30 (1979), pp. 1–28.[131] F William Lawvere and Stephen H Schanuel. Categories in Continuum Physics: Lectures given at a Workshop Held at SUNY, Buffalo 1982. Lecture Notes in Mathematics 1174. Springer, 1986.[132] Michael F Atiyah. “Topological Quantum Field Theory”. In: Publications Mathématiques de l’IHÉS 68 (1988), pp. 175–186.[133] John C Baez and James Dolan. “Higher-Dimensional Algebra and Topological Quantum Field Theory”. In: Journal of mathematical physics 36.11 (1995), pp. 6073–6105.[134] John Baez. “Quantum Quandaries: A Category-Theoretic Perspective”. In: The Structural Foundations of Quantum Gravity. Oxford: Oxford University Press, 2006. doi: 10.1093/acprof:oso/9780199269693.003.0008.[135] John Baez and Mike Stay. “Physics, Topology, Logic and Computation: A Rosetta Stone”. In: New Structures for Physics. Springer, 2010, pp. 95–172. arXiv: 0903.0340.[136] Peter Selinger. “Towards a Quantum Programming Language”. In: Mathematical Structures in Computer Science 14.4 (2004), pp. 527–586.[137] André Van Tonder. “A Lambda Calculus for Quantum Computation”. In: SIAM Journal on Computing 33.5 (2004), pp. 1109–1135.[138] Peter Selinger and Benoit Valiron. “A Lambda Calculus for Quantum Computation with Classical Control”. In: Mathematical Structures in Computer Science 16.3 (June 2006), pp. 527–552. doi: 10.1017/S0960129506005238.[139] Peter Selinger, Benoıt Valiron, et al. “Quantum Lambda Calculus”. In: Semantic techniques in quantum computation (2009), pp. 135–172.[140] Samson Abramsky and Bob Coecke. “A Categorical Semantics of Quantum Protocols”. In: 19th IEEE Symposium on Logic in Computer Science (LICS 2004), 14-17 July 2004, Turku, Finland, Proceedings. IEEE Computer Society, 2004, pp. 415–425. doi: 10.1109/LICS.2004.1319636.[141] Bob Coecke and Ross Duncan. “Interacting Quantum Observables”. In: Automata, Languages and Programming. Ed. by Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz. Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2008, pp. 298–310. doi: 10.1016/0022-4049(80)90101-2.[142] Bob Coecke and Ross Duncan. “Interacting Quantum Observables: Categorical Algebra and Diagrammatics”. In: New Journal of Physics 13 (2011), p. 043016. arXiv: 0906.4725.[143] Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. “A Complete Axiomatisation of the ZX-Calculus for Clifford+T Quantum Mechanics”. In: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (Oxford, United Kingdom). LICS ’18. New York, NY, USA: ACM, 2018, pp. 559–568. doi: 10.1145/3209108.3209131.[144] Amar Hadzihasanovic, Kang Feng Ng, and Quanlong Wang. “Two Complete Axiomatisations of Pure-state Qubit Quantum Computing”. In: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (Oxford, United Kingdom). LICS ’18. New York, NY, USA: ACM, 2018, pp. 502–511. doi: 10.1145/3209108.3209128.[145] Nicholas Chancellor, Aleks Kissinger, Joschka Roffe, Stefan Zohren, and Dominic Horsman. “Graphical Structures for Design and Verification of Quantum Error Correction”. In: ArXiv e-prints (Jan. 12, 2018). arXiv: 1611.08012.[146] Craig Gidney and Austin G. Fowler. “Flexible Layout of Surface Code Computations Using AutoCCZ States”. In: ArXiv e-prints (May 21, 2019). arXiv: 1905.08916.[147] Aleks Kissinger and John van de Wetering. “Reducing T-count with the ZX-calculus”. In: Physical Review A 102.2 (Aug. 11, 2020), p. 022406. doi: 10.1103/PhysRevA.102.022406. arXiv: 1903.10477.[148] Ross Duncan, Aleks Kissinger, Simon Perdrix, and John van de Wetering. “Graph-Theoretic Simplification of Quantum Circuits with the ZX-calculus”. In: Quantum 4 (June 4, 2020), p. 279. doi: 10.22331/q-2020-06-04-279. arXiv: 1902.03178.[149] Niel de Beaudrap, Xiaoning Bian, and Quanlong Wang. “Fast and Effective Techniques for T-Count Reduction via Spider Nest Identities”. In: 15th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2020, June 9-12, 2020, Riga, Latvia. Ed. by Steven T. Flammia. Vol. 158. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, 11:1–11:23. doi: 10.4230/LIPIcs.TQC.2020.11.[150] Alexander Cowtan, Will Simmons, and Ross Duncan. “A Generic Compilation Strategy for the Unitary Coupled Cluster Ansatz”. In: ArXiv e-prints (Aug. 27, 2020). arXiv: 2007.10515.[151] Arianne Meijer-van de Griend and Ross Duncan. “Architecture-Aware Synthesis of Phase Polynomials for NISQ Devices”. In: ArXiv e-prints (Apr. 13, 2020). arXiv: 2004.06052.[152] Miriam Backens, Hector Miller-Bakewell, Giovanni de Felice, Leo Lobski, and John van de Wetering. “There and Back Again: A Circuit Extraction Tale”. In: Quantum 5 (2021), p. 421. doi: 10.22331/q-2021-03-25-421.[153] Joachim Lambek. “Type Grammar Revisited”. In: Logical Aspects of Computational Linguistics. Ed. by Alain Lecomte, François Lamarche, and Guy Perrier. Berlin, Heidelberg: Springer Berlin Heidelberg, 1999, pp. 1–27.[154] Joachim Lambek. “Type Grammars as Pregroups”. In: Grammars 4 (2001), pp. 21–39. doi: 10.1023/A:1011444711686.[155] Joachim Lambek. “The Mathematics of Sentence Structure”. In: The American Mathematical Monthly 65.3 (Mar. 1, 1958), pp. 154–170. doi: 10.1080/00029890.1958.11989160.[156] Joachim Lambek. “Contributions to a Mathematical Analysis of the English Verb-phrase”. In: Canadian Journal of Linguistics/Revue canadienne de linguistique 5.2 (1959), pp. 83–89. doi: 10.1017/S0008413100018715.[157] Joachim Lambek. “On the Calculus of Syntactic Types”. In: Structure of Language and Its Mathematical Aspects. Ed. by Roman Jakobson. Vol. 12. Proceedings of Symposia in Applied Mathematics. American Mathematical Society, 1961, pp. 166–178. doi: 10.1090/psapm/012.[158] J. Lambek. “Categorial and Categorical Grammars”. In: Categorial Grammars and Natural Language Structures. Ed. by Richard T. Oehrle, Emmon Bach, and Deirdre Wheeler. Studies in Linguistics and Philosophy. Dordrecht: Springer Netherlands, 1988, pp. 297–317. doi: 10.1007/978-94-015-6878-4_11.[159] Joachim Lambek. “Deductive Systems and Categories in Linguistics”. In: Logic, Language and Reasoning. Ed. by Hans Jürgen Ohlbach and Uwe Reyle. Red. by Ryszard Wójcicki, Petr Hájek, David Makinson, Daniele Mundici, Krister Segerberg, and Alasdair Urquhart. Vol. 5. Trends in Logic. Dordrecht: Springer Netherlands, 1999, pp. 279–294. doi: 10.1007/978-94-011-4574-9_12.[160] Günter Hotz. “Eindeutigkeit Und Mehrdeutigkeit Formaler Sprachen”. In: J. Inf. Process. Cybern. (1966). doi: 10.5604/16431243.1040101.[161] Donald E. Knuth. “Semantics of Context-Free Languages”. In: Mathematical Systems Theory. 1968, pp. 127–145.[162] David B. Benson. “Syntax and Semantics: A Categorical View”. In: Information and Control 17.2 (Sept. 1970), pp. 145–160. doi: 10.1016/S0019-9958(70)90517-6.[163] J. Lambek. “Compact Monoidal Categories from Linguistics to Physics”. In: New Structures for Physics. Ed. by Bob Coecke. Vol. 813. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 467–487. doi: 10.1007/978-3-642-12821-9_8.[164] Günter Hotz. “Eine Algebraisierung Des Syntheseproblems von Schaltkreisen I”. Trans. by Johannes Drever. In: Elektronische Informationsverarbeitung und Kybernetik 1 (1965), pp. 185–205. url: https://github.com/drever/hotz-translation (visited on 05/10/2022).[165] Roger Penrose. “Applications of Negative Dimensional Tensors”. In: Combinatorial mathematics and its applications 1 (1971), pp. 221–244. url: http://www.math.uic.edu/~kauffman/Penrose.pdf (visited on 05/10/2022).[166] Roger Penrose and Wolfgang Rindler. Spinors and Space-Time: Volume 1: Two-Spinor Calculus and Relativistic Fields. Vol. 1. Cambridge Monographs on Mathematical Physics. Cambridge: Cambridge University Press, 1984. doi: 10.1017/CBO9780511564048.[167] André Joyal and Ross Street. “Planar Diagrams and Tensor Algebra”. In: Unpublished manuscript, available from Ross Street’s website (1988).[168] André Joyal and Ross Street. “The Geometry of Tensor Calculus, I”. In: Advances in Mathematics 88.1 (July 1, 1991), pp. 55–112. doi: 10.1016/0001-8708(91)90003-P.[169] André Joyal and Ross Street. “The Geometry of Tensor Calculus II”. In: Unpublished draft, available from Ross Street’s website 312 (1995), p. 313.[170] Jean-Yves Girard. “Linear Logic”. In: Theoretical computer science 50.1 (1987), pp. 1–101.[171] Dirk Roorda. “Proof Nets for Lambek Calculus”. In: 2.2 (1992), pp. 211–231. doi: 10.1093/logcom/2.2.211.[172] Richard Moot and Quintijn Puite. “Proof Nets for the Multimodal Lambek Calculus”. In: Stud Logica 71.3 (2002), pp. 415–442. doi: 10.1023/A:1020525032763.[173] P. Selinger. “A Survey of Graphical Languages for Monoidal Categories”. In: New Structures for Physics (2010), pp. 289–355. doi: 10.1007/978-3-642-12821-9_4.[174] Bob Coecke and Aleks Kissinger. Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning. Cambridge: Cambridge University Press, 2017. doi: 10.1017/9781316219317.[175] John C. Baez and Brendan Fong. “A Compositional Framework for Passive Linear Networks”. In: (2015). eprint: arXiv:1504.05625.[176] John C. Baez and Blake S. Pollard. “A Compositional Framework for Reaction Networks”. In: Reviews in Mathematical Physics 29.09 (Oct. 2017), p. 1750028. doi: 10.1142/S0129055X17500283. arXiv: 1704.02051.[177] John C. Baez and Jason Erbele. “Categories in Control”. In: ArXiv e-prints (May 27, 2014). arXiv: 1405.6881.[178] Filippo Bonchi, Paweł Sobociński, and Fabio Zanasi. “A Categorical Semantics of Signal Flow Graphs”. In: CONCUR 2014 – Concurrency Theory. Ed. by Paolo Baldan and Daniele Gorla. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer, 2014, pp. 435–450. doi: 10.1007/978-3-662-44584-6_30.[179] Filippo Bonchi, Jens Seeber, and Pawel Sobocinski. “Graphical Conjunctive Queries”. In: ArXiv e-prints (Apr. 20, 2018). arXiv: 1804.07626.[180] Evan Patterson. “Knowledge Representation in Bicategories of Relations”. In: ArXiv e-prints (June 1, 2017). arXiv: 1706.00526.[181] Bob Coecke and Robert W. Spekkens. “Picturing Classical and Quantum Bayesian Inference”. In: Synthese 186.3 (June 2012), pp. 651–696. doi: 10.1007/s11229-011-9917-5. arXiv: 1102.2368.[182] Kenta Cho and Bart Jacobs. “Disintegration and Bayesian Inversion via String Diagrams”. In: Mathematical Structures in Computer Science 29.7 (Aug. 2019), pp. 938–971. doi: 10.1017/S0960129518000488. arXiv: 1709.00322.[183] Aleks Kissinger and Sander Uijlen. “A Categorical Semantics for Causal Structure”. In: ArXiv e-prints (2019). doi: 10.23638/LMCS-15(3:15)2019. arXiv: 1701.04732.[184] Joe Bolt, Bob Coecke, Fabrizio Genovese, Martha Lewis, Dan Marsden, and Robin Piedeleu. “Interacting Conceptual Spaces I : Grammatical Composition of Concepts”. In: CoRR abs/1703.08314 (2017). arXiv: 1703.08314.[185] Neil Ghani, Jules Hedges, Viktor Winschel, and Philipp Zahn. “Compositional Game Theory”. In: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018, Oxford, UK, July 09-12, 2018. Ed. by Anuj Dawar and Erich Grädel. ACM, 2018, pp. 472–481. doi: 10.1145/3209108.3209165.[186] Mitchell Riley. “Categories of Optics”. In: ArXiv e-prints (Sept. 3, 2018). arXiv: 1809.00738.[187] Brendan Fong, David I. Spivak, and Rémy Tuyéras. “Backprop as Functor: A Compositional Perspective on Supervised Learning”. In: (2017). eprint: arXiv:1711.10455.[188] Aleks Kissinger and Vladimir Zamdzhiev. “Quantomatic: A Proof Assistant for Diagrammatic Reasoning”. In: Automated Deduction - CADE-25. Ed. by Amy P. Felty and Aart Middeldorp. Lecture Notes in Computer Science. Springer International Publishing, 2015, pp. 326–336. arXiv: 1503.01034.[189] Aleks Kissinger and John van de Wetering. “PyZX: Large Scale Automated Diagrammatic Reasoning”. In: ArXiv e-prints (Apr. 9, 2019). arXiv: 1904.04735.[190] Krzysztof Bar, Aleks Kissinger, and Jamie Vicary. “Globular: An Online Proof Assistant for Higher-Dimensional Rewriting”. In: Logical Methods in Computer Science 14.1 (2018). doi: 10.23638/LMCS-14(1:8)2018.[191] David Reutter and Jamie Vicary. “High-Level Methods for Homotopy Construction in Associative n-Categories”. In: 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). 2019, pp. 1–13. arXiv: 1902.03831.[192] Paweł Sobociński, Paul W. Wilson, and Fabio Zanasi. “CARTOGRAPHER: A Tool for String Diagrammatic Reasoning”. In: CALCO 2019. Vol. 139. 2019, 20:1–20:7. doi: 10.4230/LIPIcs.CALCO.2019.20.[193] Evan Patterson, David I. Spivak, and Dmitry Vagner. “Wiring Diagrams as Normal Forms for Computing in Symmetric Monoidal Categories”. In: ArXiv e-prints (Jan. 25, 2021). doi: 10.4204/EPTCS.333.4. arXiv: 2101.12046.[194] Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington, and Ross Duncan. “Tket: A Retargetable Compiler for NISQ Devices”. In: Quantum Science and Technology 6.1 (2020), p. 014003. arXiv: 2003.10611.[195] Giovanni de Felice, Elena Di Lavore, Mario Román, and Alexis Toumi. “Functorial Language Games for Question Answering”. In: Proceedings of the 3rd Annual International Applied Category Theory Conference 2020, ACT 2020, Cambridge, USA, 6-10th July 2020. Ed. by David I. Spivak and Jamie Vicary. Vol. 333. EPTCS. 2020, pp. 311–321. doi: 10.4204/EPTCS.333.21.[196] Dimitri Kartsaklis, Ian Fan, Richie Yeung, Anna Pearson, Robin Lorenz, Alexis Toumi, Giovanni de Felice, Konstantinos Meichanetzidis, Stephen Clark, and Bob Coecke. “Lambeq: An Efficient High-Level Python Library for Quantum NLP”. In: CoRR abs/2110.04236 (2021). arXiv: 2110.04236.[197] Hermann Grassmann. Die Lineale Ausdehnungslehre Ein Neuer Zweig Der Mathematik: Dargestellt Und Durch Anwendungen Auf Die Übrigen Zweige Der Mathematik, Wie Auch Auf Die Statik, Mechanik, Die Lehre Vom Magnetismus Und Die Krystallonomie Erläutert. Vol. 1. O. Wigand, 1844.[198] F William Lawvere. “Display of Graphics and Their Applications, as Exemplified by 2-Categories and the Hegelian “Taco””. In: Proceedings of the First International Conference on Algebraic Methodology and Software Technology, University of Iowa. 1989, pp. 51–74.[199] F. William Lawvere. “Some Thoughts on the Future of Category Theory”. In: Category Theory. Ed. by Aurelio Carboni, Maria Cristina Pedicchio, and Guiseppe Rosolini. Vol. 1488. Lecture Notes in Mathematics. Berlin, Heidelberg: Springer Berlin Heidelberg, 1991, pp. 1–13. url: http://link.springer.com/10.1007/BFb0084208 (visited on 12/15/2021).[200] F. William Lawvere. “Categories of Space and of Quantity”. In: The Space of Mathematics. Ed. by Javier Echeverria, Andoni Ibarra, and Thomas Mormann. Berlin, Boston: DE GRUYTER, Jan. 31, 1992. doi: 10.1515/9783110870299.14.[201] F. William Lawvere. “Unity and Identity of Opposites in Calculus and Physics”. In: Applied Categorical Structures 4.2-3 (1996), pp. 167–174. doi: 10.1007/BF00122250.[202] Urs Schreiber, David Corfield, and nLab. Science of Logic. 2021. url: https://ncatlab.org/nlab/show/Science+of+Logic (visited on 12/15/2021).[203] Georg Wilhelm Friedrich Hegel. Wissenschaft Der Logik. F. Frommann, 1812.[204] Charles Santiago Sanders Peirce. “Prolegomena to an Apology of Pragmaticism”. In: The Monist 16.4 (1906), pp. 492–546. JSTOR: 27899680.[205] Geraldine Brady and Todd H. Trimble. “A String Diagram Calculus for Prediate Logic and C. S. Peirce’s System Beta”. 1998. url: http://people.cs.uchicago.edu/~brady/beta98.ps.[206] Geraldine Brady and Todd Trimble. “A Categorical Interpretation of C.S. Peirce’s Propositional Logic Alpha”. In: Journal of Pure and Applied Algebra 149 (June 2000), pp. 213–239. doi: 10.1016/S0022-4049(98)00179-0.[207] Paul-André Melliès and Noam Zeilberger. “A Bifibrational Reconstruction of Lawvere’s Presheaf Hyperdoctrine”. In: ArXiv e-prints (Aug. 12, 2016). arXiv: 1601.06098.[208] Nathan Haydon and Pawel Sobocinski. “Compositional Diagrammatic First-Order Logic”. In: (2020), p. 16.[209] Jules Hedges and Martha Lewis. “Towards Functorial Language-Games”. In: ArXiv e-prints (July 20, 2018). arXiv: 1807.07828.[210] Giovanni de Felice, Alexis Toumi, and Bob Coecke. “DisCoPy: Monoidal Categories in Python”. In: Proceedings of the 3rd Annual International Applied Category Theory Conference, ACT. Vol. 333. EPTCS, 2020. doi: 10.4204/EPTCS.333.13.[211] Francis Jeffry Pelletier. “Did Frege Believe Frege’s Principle?” In: Journal of Logic, Language and information 10.1 (2001), pp. 87–114.[212] Joseph CH Chen. “Quantum Computation and Natural Language Processing”. Staats-und Universitätsbibliothek Hamburg Carl von Ossietzky, 2002.[213] William Blacoe, Elham Kashefi, and Mirella Lapata. “A Quantum-Theoretic Approach to Distributional Semantics”. In: Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. NAACL-HLT 2013. Atlanta, Georgia: Association for Computational Linguistics, June 2013, pp. 847–857. url: https://aclanthology.org/N13-1105 (visited on 12/01/2021).[214] Saunders MacLane. “Carnap on Logical Syntax”. In: Bulletin of the American Mathematical Society 44.3 (1938), pp. 171–176.[215] Emily Riehl and Dominic Verity. “Infinity Category Theory from Scratch”. In: ArXiv e-prints (2016).[216] Bob Coecke. “The Mathematics of Text Structure”. In: Joachim Lambek: The Interplay of Mathematics, Logic, and Linguistics. Ed. by Claudia Casadio and Philip J. Scott. Cham: Springer International Publishing, 2021, pp. 181–217. doi: 10.1007/978-3-030-66545-6_6[217] Joachim Lambek. From Word to Sentence: A Computational Algebraic Approach to Grammar. Open Access Publications. Polimetrica, 2008.[218] J. Lambek. “Compact Monoidal Categories from Linguistics to Physics”. In: New Structures for Physics. Ed. by Bob Coecke. Vol. 813. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 467–487. doi: 10.1007/978-3-642-12821-9_8.

（参考文献可上下滑动查看）

范畴论课程

范畴论是一个研究结构的理论，提供了一种系统、精确、抽象的跨领域科学方法论，可直接付诸于各领域考察的问题，寻求跨领域的解决之道。这种数学语言与复杂性科学有众多相似之处，加之其本身作为数学工具的严密性，后续可能能为解决复杂性科学问题提供一把钥匙。

详情请点击：

后ChatGPT读书会招募中

2022年11月30日，一个现象级应用程序诞生于互联网，这就是OpenAI开发的ChatGPT。从问答到写程序，从提取摘要到论文写作，ChatGPT展现出了多样化的通用智能。于是，微软、谷歌、百度、阿里、讯飞，互联网大佬们纷纷摩拳擦掌准备入场……但是，请先冷静一下…… 现在 all in 大语言模型是否真的合适？要知道，ChatGPT的背后其实就是深度学习+大数据+大模型，而这些要素早在5年前的AlphaGo时期就已经开始火热了。5年前没有抓住机遇，现在又凭什么可以搭上大语言模型这趟列车呢？

集智俱乐部特别组织“后 ChatGPT”读书会，由北师大教授、集智俱乐部创始人张江老师联合肖达、李嫣然、崔鹏、侯月源、钟翰廷、卢燚等多位老师共同发起，旨在系统性地梳理ChatGPT技术，并发现其弱点与短板。本系列读书会线上进行，2023年3月3日开始，每周五晚 19:00-21:00，欢迎报名交流。

详情请见：

推荐阅读

点击“阅读原文”，报名读书会