编辑 | 紫罗

时间序列广泛应用于数理统计、数学金融、医学医疗、天气预报、语音识别和生物等领域。

时间序列是作为一系列时间上均匀分布的样本收集的一组数据，例如一个月每个市场日结束时股票指数的价值，或者一个城市一年中每天的平均温度。

高维时间序列在每个采样时刻由多条信息组成，而不是只有一条信息，因此高维时间序列的处理和分析计算量更大。

动态模式分解（DMD）算法是时间序列分析中广泛使用的因式分解和降维技术。在分析高维时间序列时，DMD 算法需要极大的计算能力。

为了加速 DMD 算法，来自中国科学技术大学和合肥综合性国家科学中心人工智能研究院的研究团队，提出了一种量子经典混合算法，称为量子动态模态分解（QDMD）算法。

研究人员在三个应用场景中测试了他们的算法：数据去噪、场景背景提取和流体动力学分析。研究确定 QDMD 只需少量样本即可运行，并且在高维时间序列分析中具有量子优势。

该研究以「Quantum Dynamic Mode Decomposition Algorithm for High-Dimensional Time Series Analysis」 为题，于 2023 年 7 月 28 日发表在《Intelligent Computing》杂志上。

为了加速高维时间序列分析，研究人员开发并测试了 QDMD 算法。它通过降低对时间序列数据执行的操作的复杂性来实现指数加速。

QDMD 算法的框架如下图所示。输入是时间序列 oracle。首先在初始状态准备步骤中准备由 X0的主奇异向量组成的初始状态，然后对 X0生成的矩阵进行量子奇异值分解，得到包含分解矩阵的主奇异值和奇异向量的输出状态。然后对获得的输出状态进行低采样频率处理，并使用采样结果计算投影 DMD 算子 A。最后，使用一元线性组合 (LCU) 技术计算 DMD 特征值并准备 DMD 模态的幅度编码状态。

在目前的形式下，它也可以用来加速对某些其他类型数据集的分析。此外，研究人员计划创建其算法的新变体，专门用于其他动态模态分解应用，如库普曼分析。

量子算法的主要限制是样本数量必须保持小，否则不会降低算法的复杂度，失去量子优势。研究人员在设计算法时充分意识到这一点，因此对样本数量设定了上限，以确保强大的性能。

不过，合肥综合性国家科学中心人工智能研究院研究员Cheng Xue解释道：「通过数值测试，我们发现分析特定时间序列所需的样本数量低于我们推导的界限，这进一步说明了我们算法的加速性能。」

为了测试改变样本数量的效果，研究人员探索了他们的量子算法在不同领域的应用。第一个是数据去噪，是类似于从图像中去除噪声的过程。第二，场景背景提取，是计算机视觉中的常见任务。它是一种通过比较同一场景的一系列图像来去除前景项目的图像处理方法。第三种是流体动力学分析，用于预测气体或液体的运动。该算法成功地执行了这些任务。

第一个应用是数据去噪，这是去除噪声并重建原始数据的过程。研究人员使用 QDMD 算法解决特定的时间序列去噪问题。

图 2 为 k = 0，4，8，12 时的 4 个快照（snapshot）。图 2A ~ C 分别为噪声快照、重构快照和原始快照。重构后的图像更接近原始图像，表明去噪成功。

QDMD 算法的第二个应用是场景背景提取，其中从背景被多个前景对象遮挡的图像序列中获得背景模型。场景背景提取具有广泛的应用，从视频监控到计算摄影。

随着样本数量的增加，QDMD 算法变得更加稳定。当样本数达到 10, 000 个时，QDMD 算法的性能相对较好。使用 QDMD 算法提取的背景。3 个数据集的空间维度分别为 230,400、921,600 和 1,440,000，均显著大于10,000。此外，样本数 M 对 MSSSIM 的影响与 n 无关；因此，随着 n 的增加，QDMD 算法提供了更大的量子优势。

在许多可能的应用中，流体动力学尤其重要。「动态模态分解最初用于流场数据分析，」 Cheng Xue解释道。「流体动力学的研究往往会产生高维流场数据，数据维度达到数十亿级。从这些数据中提取有意义的流场特征是一个具有挑战性的问题。」

接下来，利用 QDMD 算法加速流场数据分析是 QDMD 一个有前景的应用场景。研究人员应用 QDMD 算法，测试样本数 M 对获得的 DMD 特征值和 DMD 模态的影响；结果如下图所示，当样本数量相对较少时，QDMD 算法的保真度接近 1。因此，QDMD 算法对于流体动力学分析也很有效。

由于量子计算机仍处于开发阶段且相对难以获得，该研究在量子算法方面的工作由「理论推导加数值模拟」 组成，但她表示，量子芯片技术正在与量子算法的「协同」 关系中快速发展，在不远的将来，这有望带来「革命性的突破」。

量子计算机的力量来自两个不直观的特性：叠加和纠缠，这使得它们能够并行执行许多计算。然而，量子计算「只能加速特定问题的速度，并不能取代经典计算机」 。

未来，研究人员将利用 QDMD 算法加速库普曼（Koopman）分析，并开发量子库普曼分析算法来提取时间序列的非线性特征。