学界 | 中科大潘建伟团队在光量子处理器上成功实现拓扑数据分析

2018 年 1 月 25 日 机器之心

选自arXiv

作者：黄合良等

机器之心编译

参与：刘晓坤

近日，来自中国科学技术大学、中国科学院-阿里巴巴量子计算实验室等机构，由潘建伟院士、陆朝阳教授带领的团队完成了在光量子处理器上执行拓扑数据分析（TDA）的原理性实验演示验证。TDA 可以抵抗一定噪声的干扰，从数据中提取有用信息，而量子版本的 TDA 能实现对经典最优 TDA 算法的指数级加速。量子 TDA 算法也是继 Shor 算法（用于大数因子分解进行密码破译）、Grover 算法（用于搜索问题）、HHL 算法（用于解线性方程组）之后，人类在量子计算机上可使用的一种新算法。该研究为在量子计算机上进行高维数据处理、甚至人工智能算法领域的探索打开了方向。

论文：Demonstration of Topological Data Analysis on a Quantum Processor

论文链接：https://arxiv.org/abs/1801.06316

通过识别带噪声、非结构化数据的底层结构，拓扑数据分析（TDA）可以鲁棒地从数据中提取有用信息。最近，人们提出了一种有效的量子算法 [Lloyd, Garnerone, Zanardi, Nat. Commun. 7, 10138 (2016)]，用于计算数据点的贝蒂数（一种拓扑特征，描述散点图中各个维度的拓扑洞的总数）。我们利用一个六光子量子处理器实现了这个量子算法的原理性实验演示验证，成功地分析了一个包含三个数据点的网络的贝蒂数拓扑特征，为量子计算领域的数据分析提供了新的探索思路和研究方法。

在探索性数据分析和数据挖掘中，我们的收集到的大数据通常编码了非常有价值的信息，然而，这些数据往往规模很大，并且是非结构化的、带噪声的、不完整的，从而使得从数据中提取有用信息变得很有挑战性。TDA[1] 将拓扑学与数据分析进行结合，可以从无结构的数据中分析数据隐含的拓扑特征，对噪声具有较强的鲁棒性，提供了研究此类数据的一种分析方法。特别地，持续同调（persistent homology）[2][3] 通过计算和分析数据的贝蒂数，用于提取数据的有用信息。其中，贝蒂数是一种拓扑特征，第 k 个贝蒂数β_k 表示为数据集中的 k 维洞的数量。例如，β_0、β_1、β_2 分别代表了连通分支、一维洞和二维洞的数量。通过贝蒂数可以对数据进行了抽象化表示，将其转化为拓扑性的描述，这对于理解数据集的底层结构很有价值。使用 TDA 分析数据的贝蒂数这一分析方法近年来得到了快速发展，有望应用于图像识别 [4]、信号处理 [5]、网络科学 [6,7]、传感器分析 [8-11]、大脑连接 [12,13] 和 fMRI 数据分析 [14,15] 等。

然而实际上，当处理复杂数据的时候，经典的拓扑数据分析方法将面临计算量巨大的问题：n 个数据点的数据集拥有 2^n 个潜在拓扑结构，即使使用最强大的经典计算机也难以求解规模不太大的数据集。目前，估计数据集合所有阶贝蒂数的最优经典算法需要的时间复杂度为 O(2^nlog(1/δ)) [16–21]，其中δ为精度。此外，对某些类型的拓扑结构 [22]，计算所有阶贝蒂数是 PSPACE-hard 的。

最近，Lloyd 等人 [23,24] 将量子机器学习方法扩展到 TDA 中，以高效地计算所有阶的贝蒂数。如果从一个数据集中生成的 k-单纯形的比例足够大，则以精度δ计算所有阶贝蒂数的量子算法耗费的时间复杂度为 O(n^5/δ)，相比已知最好的经典算法，具有指数加速。此外，该算法不需要大规模的量子随机存取存储器（qRAM）[25]，只需要 O(n^2 ) 的比特数即可——用于存储 n 个数据点之间所有两两间距的信息。该算法的潜在计算加速能力和可行性有望令量子 TDA 作为未来量子计算机的新算法（量子算法包括 Shor 算法、[26,29]、量子模拟 [30-33]、求解线性系统 [34,35] 和线性向量的分类 [36-38] 等）。

我们首次利用一个小规模的光子量子处理器，进行了量子 TDA 算法的原理性演示验证。在实验中，我们在两种不同的距离参数下，监控和识别三个数据点的贝蒂数的拓扑特征，成功地展示了量子 TDA 算法的可行性，表明数据分析可能是未来量子计算的重要应用。

为了计算贝蒂数，我们首先以数据点之间的关系拓扑地表征数据。我们使用截断距离将数据点分类为单纯形（参见图 1（a）），即数据点的全连接子集。单纯形的集合构成一个单纯复形，然后可以从该拓扑结构中提取贝蒂数等特征。这些拓扑结构如图 1（b-d）所示。

通过确定ϵ所有范围的贝蒂数的完整集合，我们可以构建条形码（参见图 1（e））[39]，即贝蒂数的距离依赖形式的参数化版本。H_k 区域内的每个条形代表一个 k 维洞，条形的长度表示其在参数中的存在持续性。利用条形码，我们可以定量地将短条形当做拓扑噪声过滤掉，并将长条形作为重要的特征（条形的长度表示其对抗间距变化的存在持续性）。在图 1（e）中，在 H_1 区域有一个条形延展了很长的范围，从而我们确定该非结构化数据（图 1（b））的底层拓扑特征是一个圆。

图 1：（a）k-单纯形（图中展示了 k=0、1、2、3 的例子）是 k+1 个数据点的全连接集合。（b）数据点的散点图。（c）使用某些任意的指标以量化数据点之间的距离，（以数据点为，圆心直径为ϵ）圆彼此接触的数据点之间以边连接。（d）单纯复形是单纯形的集合。着色区域表示复形中的不同单纯形。（e）条形码的结构。水平轴代表距离ϵ。在 H_k 的任意区域中，条形和垂直线的交点数等于（距离ϵ对应的）贝蒂数β_k。

一般地，量子 TDA 算法有两个主要步骤（参见图 2（a））。首先访问数据，构造的拓扑结构 k-单纯形的均匀混态。该步骤的时间复杂度依赖于 k-单纯形的比例，在最差的情况下是指数量级的。但是在实际应用中，复杂拓扑结构中 k-单纯形的比例一般不会太小。所以，在实际应用中，无论用经典算法还是 Grover 算法（进一步的二次型算法加速）都可以高效地实现这个步骤。在量子算法中，这个步骤可以分成两小步：（1a）单纯复形量子态的制备；（1b）均匀混态的构造。（2）揭示结构中的拓扑不变量，这个步骤使用相位估计算法 [40] 实现，在量子计算机上，该算法相对经典算法能实现指数级加速，实际证明 [23,24] 它的时间复杂度为 O（n^5/δ），其中δ为计算精度。

图 2：量子 TDA 的量子线路。（a）原始量子算法线路的简单示意图。（b）包含三个数据点的散点图。

（c）1-单纯形量子态（3<ϵ_1<4）

的图表征。第一个和第二个数据点由一条边连接。

（d）1-单纯形量子态（4<ϵ_2<5）

第一个数据点分别和第二个和第三个数据点连接。（e）5 量子比特的优化量子线路。不同颜色的模块代表 4 个基本阶段（单纯复形制备、构造混态、相位估计、测量）。

图 3：实验装置。中心波长为 394nm 的紫外激光脉冲（脉冲持续时间为 150 飞秒，脉冲重复频率为 80MHz）通过三个偏硼酸钡（BBO）晶体 [42] 以生成三对纠缠光子对 (|H>|V>+|V>|H>)/√2（空间模式分别为 1-2、3-4、5-6，细节参见附录 1）。光子 2（3）和 4（5）在 PBS 上进行干涉。所有的光子使用 3-nm 带宽的过滤器进行光谱过滤。C-BBO：三明治形态的 BBO+HWP+BBO 组合；QWP：四分之一玻片；POL：起偏器；SC-YVO4：用于空间补偿的 YVO4 晶体；TC-YVO4：用于时间补偿的 YVO4 晶体。

图 4：最终的实验结果。最终的输出通过在泡利-Z 基上测量本征值寄存器确定。两个不同 1-单纯形的态输入的测量期望值（蓝色条形）和理论预测值（灰色条形）如（a）和（b）所示。误差线表示 1 个标准偏差，它是根据原始数据，通过泊松分布推导得出的（c）0<ϵ<5 的条形码。由于不存在 k≥1 的 k 维洞，这里只给出了第 0 个贝蒂数。当 0<ϵ<3 时，所有点之间都没有连接，因此第 0 个贝蒂数等于数据点个数，即 0<ϵ<3 时有三个条形。当 3<ϵ1<4 和 4<ϵ2<5 时，第 0 个贝蒂数分别等于 2 和 1。

（a）的量子态：