Petri网、离散物理与分布式量子计算

### Petri网、离散物理与分布式量子计算 #### 1. 引言 本文聚焦于三个看似截然不同领域之间的联系： - 并发计算模型，尤其是Petri网。 - 物理学，特别是量子力学和量子信息。 - 具有额外结构的幺半范畴（如紧致闭包）。 我们的研究受到以下前期工作的启发： - Petri的开创性工作，始终强调其网络理论与物理学之间的联系。 - Ugo Montanari和Jos´e Meseguer的先驱性工作，将幺半范畴作为网络理论的框架，后经Marti - Oliet和Meseguer进一步扩展。 - 作者与Bob Coecke的研究，利用幺半范畴对量子力学进行新的公理化，并应用于量子信息领域。 这些联系可以用以下关系图表示： ```mermaid graph LR A[Petri Nets] -->|Petri| B[Monoidal Categories] C[Physics] -->|A and Coecke| B A -->|M*| B ``` #### 2. 作为离散物理的Petri网 与“语言”方法（如进程演算）相比，Petri对并发的概念有其独特之处。它试图以一种独立于语法的“几何”方式解释因果关系、并发、进程等基本概念。此外，Petri的思想明显受到物理学的影响，例如K - 密度就源自Carnap对相对论的公理化之一。在很大程度上，网络理论可以被视为一种离散物理：线代表类似时间的因果流，割代表类似空间的区域，标记网的进程展开类似于微分方程的解轨迹。 如今，“信息即物理”这一观点在快速发展的量子信息学领域具有新的意义。同时，认识分布式系统的空间结构的需求也变得明显，如环境演算和Milner的双图等形式化方法就明确体现了这一点。 以下是一些相关的描述： - **第0层：并发结构**：并发是指“世界点的共时二元关系”，这里紧密遵循相对论时空的公理化。个体是信号的时间层，即物理效应的最小传播者。一些信号是粒子，其他信号通过相互作用传播。每个信号的历史是一条“世界线”，由世界点组成。定义如下关系： - \(x < y\) 表示 \(x \neq y\) 且有信号从 \(x\) 传递到 \(y\)。 - \(x \text{ co } y \Leftrightarrow\) 既不是 \(x < y\) 也不是 \(y < x\)。 - \(x \text{ li } y \Leftrightarrow\) \(x < y\) 或 \(y < x\) 或 \(x = y\)。 - 定义 \(Co(x) := \{z | x \text{ co } z\}\) 和 \(Li(x) := \{z | x \text{ li } z\}\)。如果 \(Co(x) = Co(y)\) 或 \(Li(x) = Li(y)\)，则将 \(x\) 和 \(y\) 归为一个簇，这些簇是世界点的等价类，将成为第1层的个体。 - **第1层：发生网**：描述所有发生事件的集合 \(X\) 的结构，以及它划分为状态元素集合 \(S\) 和转换元素集合 \(T\)。子集 \(l \subset X\) 若为两两具有 \(li\) 关系的最大发生事件集合，则称为线；子集 \(c \subset X\) 若为两两具有 \(co\) 关系的最大发生事件集合，则称为割。“每个割代表一个空间分布”这一古老的物理假设现在可以表述为“每个割与每条线相交”，即K - 密度。 #### 2.1 因果集与其他途径 物理学家在量子引力的研究中，独立地有了类似的思考。因果集的目标是构建一个最终（在“普朗克尺度”）离散的时空理论。因果集是一个局部有限偏序集，元素是事件，顺序是因果关系。其理念是“顺序 + 数量 = 几何”，“数量”指计算给定时空区域内发生的事件数量，这会引出“体积”的概念，并且偏序集的增长会产生“动力学”，时空的大规模结构特性应从这种增长的随机特性中显现出来。 此外，Lee Smolin的著作以及Keye Martin和Prakash Panangaden的工作也与这些思想相关。 #### 3. 插曲：对称幺半范畴 我们简要回顾并介绍对称幺半范畴的基本概念。 - **范畴**：范畴 \(C\) 有对象（类型） \(A, B, C, \cdots\)，对于每对对象 \(A, B\) 有一组态射 \(C(A, B)\)（记为 \(f : A \to B\)），还有恒等态射 \(id_A : A \to A\)，以及类型匹配时的复合 \(g \circ f\)。范畴允许我们明确处理类型化的进程，如下表所示： | 领域 | 对象 | 态射 | | ---- | ---- | ---- | | 逻辑 | 命题 | 证明 | | 编程 | 数据类型 | 程序 | | 计算 | 状态 | 转换 | - **