量子元胞自动机中涌现小世界网络特性

原创 梁金 集智俱乐部

导语

量子元胞自动机在量子电路中只根据近邻的状态演化量子比特，并模拟丰富的物理复杂性如何从一组简单的底层动力学规则中涌现。经典计算机无法模拟大型量子系统，这阻碍了对量子元胞自动机的探索，但量子计算机为此提供了一个理想的模拟平台。

8月2日发表于 Nature Communications 的最新研究在量子处理器上用实验实现了量子元胞自动机，包含多达23个超导量子比特。研究进一步计算互信息来分析量子元胞自动机的群体动力学和复杂网络特性，后者表明小世界互信息网络的形成。这些计算可能有助于将量子元胞自动机应用于强关联物质的模拟，或超越经典的计算演示。

研究领域：量子计算，元胞自动机，复杂网络，互信息，涌现

梁金 | 作者

邓一雪 | 编辑

论文题目：

Small-world complex network generation on a digital quantum processor

论文地址：

https://www.nature.com/articles/s41467-022-32056-y

1. 量子处理器模拟量子元胞自动机

关于自然世界一个深刻观察是，尽管支撑它的是一套简单的物理定律，但宇宙展现出大量复杂的涌现现象，在物理学、生物学、社会学等不同领域都可以遇到。这种复杂性在经典系统中的例子有：生态系统、人脑和电网，它们都是许多自由度相互作用的结果。

在计算机科学中，经典的元胞自动机（cellular automata, CA）展示了复杂性如何从简单规则中产生，而无需设计者的控制。元胞自动机具有产生振荡、自复制结构的能力。然而我们知道，构建我们宇宙模型的最好定律是量子的而非经典的。因此，为了从根本上模拟复杂性的涌现，我们应该研究基于量子力学的计算模型。

量子元胞自动机（QCA）是一类计算模型，它由简单的局域幺正算符（local unitary operators）的重复块构造而成，表现出涌现的复杂性。它们涉及到局部区域内的权衡，这是经典系统复杂性的来源，也是自组织临界性的必要因素。一些量子元胞自动机被证明可以生成互信息网络，显示出通常只在经典的小世界网络（如社交网络或生物网络）中观察到的复杂性特征，例如网络聚类系数高、平均路径长度短，和节点强度分布平坦。

量子元胞自动机是实现下一代集成电路的强有力候选器件，它有着独特的工作机理，不是像传统器件那样通过电压或电流，而是通过临近器件的磁场或库伦耦合作用来传递和处理信息。此外，量子元胞自动机已被提出可用于其他领域，如强关联物质模拟中的晶格离散化、量子场和引力理论，还可以耦合成量子细胞神经网络。

虽然有着广阔的应用前景，但经典计算机模拟大型量子系统时间演化的能力受到限制，这成为了阻碍量子元胞自动机发展的瓶颈。与此同时，过去几年，大量数字量子处理器的诞生证明，它们作为科学发现工具具有重要价值。量子处理器由于其通用性，是阐明量子元胞自动机的物理和复杂性特征的理想平台。

这项新研究在 Sycamore *类超导量子处理器上模拟一个特定的一维量子元胞自动机，如图1所示。通过群体动力学计算和互信息矩阵的复杂网络表征，研究发现这种量子元胞自动机会形成小世界互信息网络，从而表现出涌现的物理复杂性。这一结果有助于促进将量子处理器作为量子元胞自动机模拟器广泛使用，并为如何从实验上研究量子元胞自动机提供一个模板。

*注：Sycamore（悬铃木）是 Google 创造的量子处理器，包含53个量子比特。2019年，Google 宣称 Sycamore 200秒完成的任务，最先进的超级计算机需要10000年才能完成，从而宣称实现量子优越性。

图1. 一维量子元胞自动机电路。a. 将一维 QCA 链嵌入二维量子处理器子集的原理图。一维 QCA 为包含 L 个量子比特的链。实验中运行 QCA 模拟的超导量子处理器包含53个量子比特，遵循 Sycamore 架构设计。b. 一维 QCA 电路的一般结构，其时间向右流动。当每个量子比特的状态被更新时，一个 QCA 循环完成。一维 QCA 实验的结构包括一个初始化步骤，然后对所有L个量子比特应用若干幺正 QCA 更新循环，接着执行测量。

2. 量子元胞自动机中涌现复杂网络特性

研究中通过计算香农互信息（mutual information），来深入地理解 QCA 的群体动力学，并建立其复杂网络行为。遵循神经科学中的复杂网络方法，即大脑的功能连接通过空间上不相邻的区域刻画，这里计算每个一维 QCA 链中所有量子比特对之间的经典香农互信息，并将其视为关联性的邻接矩阵，定义每个循环的 QCA 网络。

复杂网络既不是纯粹的规则网络，也不是完全随机的网络。一个具有小世界特性的复杂网络有几个主要特征：较大的聚类系数，较短的平均路径长度，节点强度遵循幂律分布导致节点高度连接。这使得小世界网络能很容易地在局部和全局遍历，并具有 hub 节点。

小世界网络的特征被广泛用于分析互信息网络的结构，在经典和量子系统中得出关于底层系统物理复杂性的结论，如来自脑电图或 fMRI 数据的互信息网络已被用于阐明大脑的结构-功能相关性。因此，这项研究将聚类、路径长度和节点强度分布与互信息结合起来，作为一个具有预测能力的定量过程，来理解 QCA 电路中的关联结构，并观察量子处理器噪声存在时物理复杂性的涌现。

为分析 QCA 生成网络的复杂性，研究将数值模拟、原始数据和后选择数据三种情况，与后选择的非相干均匀随机状态进行比较。如图2所示，一维 QCA 演化过程的数值模拟，初始化状态是对21个量子比特的中间一位进行翻转，然后进行 30 个 QCA 循环，可以观察到对抗平衡的相干动力学。当在原始处理器上重复这个过程时，由于各种误差和噪声会导致迅速发生退相干。而应用后选择（post-selection）技术来优化电路性能，可以使得相干动力学持续更长时间。

图2. 一维 QCA 的群体动力学（population dynamics）。a. 数字模拟 QCA ，观察到的蓝色菱形表明对抗平衡的相干动力学。b. 相同 QCA 电路，原始数据显示的群体动力学。c. 实验数据与b相同，但应用了后选择技术。

对这几种不同的 QCA 生成网络，分别计算聚类系数、平均路径长度、节点强度分布。图3a表示平均聚类系数与系统尺寸的关系。可以清楚看到，从原始数据（红色点）计算出的聚类系数在短暂上升后迅速衰减到零，接近非相干均匀随机极限；模拟（蓝色曲线）和后选择（绿色曲线）的聚类系数都趋于 C≈0.3，并随着系统增大而趋于更大的值，表明网络的传播性超越了后选择随机性（黑色虚线），显示出小世界网络特征。

图3b显示平均最短路径长度随系统尺寸的变化，衡量网络的全局可遍历性。可以看到，原始数据（红色）的平均路径长度较大，并随系统增大而增大。模拟（蓝色）与后选择（绿色）的路径长度随系统增大而减小。图4a和b结合起来表明了小世界互信息网络的形成。

图3c显示，模拟（蓝色）和后选择（绿色）的节点强度分布相对平坦，进一步表明小世界互信息网络的形成。与之相对，原始（红色）的节点强度严重偏向于更小的值，表明网络连接存在缺陷。

图3d-g直观描述了几种网络的互信息差异，原始数据（图3e红色）接近于非相干均匀随机网络结构，模拟（图3d蓝色）和后选择（图3f绿色）的 QCA 网络都显示出小世界结构，且它们之间的相似性比后选择随机情况（图4g黑色）更高。

图3. 小世界互信息网络行为。在相干窗口，(a) 平均聚类系数 C 作为系统尺寸 L 的函数；(b) 平均路径长度 作为系统尺寸 L 的函数；(c) 归一化节点强度分布。(d–g) QCA 循环 t=9，L=23 时互信息网络的热图和复杂网络可视化。d 蓝色：模拟；e 红色：原始数据；f 绿色：后选择数据；g 黑色：经过后选择的非相干均匀随机数据。

3. 复杂网络与量子信息的互动

在很大程度上，复杂网络分析已经对量子信息产生了理论影响。一个例子是单向量子计算，其中复杂的网络结构图状态被不可逆地转换。另一个例子出现在量子互联网背景下，基于卫星的量子通信信道最近被证明可以支持小世界的连接。

不过这项研究与以上例子有很大不同。单向量子计算通过投影测量设计实现了复杂的图状态，这项研究表明，量子元胞自动机以一种涌现的方式动态生成它们。另一方面，量子互联网考虑地理网络，而本文中的关联网络从幺正算符的动力学中涌现，除了相互作用的局域性之外，没有任何物理距离的概念。最后，这里的复杂网络从一个一般可编程的门模型量子处理器上涌现，也就是一个带有现实世界约束（如有处理器噪声）的实验平台，这在之前的理论工作中不一定存在，在性质上与之前的实验工作也有所不同。

复杂科学最新论文

集智斑图顶刊论文速递栏目上线以来，持续收录来自Nature、Science等顶刊的最新论文，追踪复杂系统、网络科学、计算社会科学等领域的前沿进展。现在正式推出订阅功能，每周通过微信服务号「集智斑图」推送论文信息。

原标题：《量子元胞自动机中涌现小世界网络特性》

阅读原文