量子科技中心_量科网

给定一个维度为M×N的矩阵A和一个向量b→，量子线性系统（QLS）问题要求制备一个与A⁻¹b→解成比例的量子态|y→⟩。现有的QLS算法通常具有与条件数κ(A)、矩阵A的稀疏度呈线性关系，以及与逆精度呈对数关系的运行时间。然而，这些算法往往忽略了输入向量b→的结构特性，尽管其与A的特征空间的对齐会显著影响性能。 在该工作中，该研究团队提出了一种新的QLS算法，明确利用了右侧向量b→的结构。定义矩阵的稀疏度为任意行或列中非零项的最大数量。该算法的运行时间多项式依赖于增广矩阵H=[A, -b→]的稀疏度s、逆精度、解y→=A⁺b→的ℓ₂范数，以及一个新的实例相关参数E_T=∑ᵢ₌₁ᴹ pᵢ²·dᵢ，其中p→=(AAᵀ)⁺b→，dᵢ表示H的第i行平方ℓ₂范数。 为了进一步降低某些应用的运行时间，该团队引入了一种针对解y→=A⁺b→量身定制的结构感知重缩放技术。与将系统转换为D A y→=D b→的左预处理方法不同，该方法应用右重缩放矩阵，将线性系统重新表述为A D z→=b→。 这种实例感知的QLS算法和重缩放策略的结合，重新开启了在非线性微分方程和多项式系统等多个领域实现超多项式量子加速的可能性。作为应用，该研究团队开发了一种新的量子算法，用于解决先前基于QLS方法失败的多元多项式系统。该工作的成果产生了一个新的端到端算法框架，基于新的QLS算法，适用于广泛的问题类别。 特别地，该团队将该方法应用于最大独立集（MIS）问题，将其表述为多项式系统的一个特例。给定一个图，MIS问题是计算顶点的最大子集，使得子集中任意两个顶点不共享边。该研究团队提供了详细的运行时间分析，并表明在某些条件下，该量子算法在多项式时间内运行。虽然在这些条件下尚未开发出经典算法，但该量子算法的一个有前景特性是其运行时间明确依赖于输入图中独立集的结构。