量子科技中心_量科网

三角形能够捕捉图中的高阶结构，是聚类和网络分析等应用的基础。为了在大规模场景下高效利用这类结构，该团队研究了\emph{三角割稀疏化}问题，其目标是在近似保留每个割的三角计数的情况下减小图的规模。该团队针对此问题研究了\emph{量子算法}，并以三角列举作为主要技术手段。具体而言，该团队提出了一种用于三角列举的量子算法，对于具有 \(n\) 个顶点、\(m\) 条边和 \(t\) 个三角形的图，该算法运行时间为 \(T_{\mathrm{q\text{-}list}} =\) \(\widetilde{O}\bigl(\min(n^{5/4}t^{7/12} + n^{7/6}t^{7/9}, m + m^{3/4}t^{1/2},\) \(n^{3/2}t^{1/2})\bigr)\)，在广泛的参数范围内优于已知的最佳经典算法。该算法基于重轻顶点划分，并扩展了通过量子游走和Grover搜索进行三角检测的方法。基于此结果，该团队设计了一种量子算法，用于构建大小为 \(\widetilde{O}(n/\varepsilon^2)\) 的 \(\varepsilon\)-三角割稀疏化器，运行时间为 \(\widetilde{O}(T_{\mathrm{q\text{-}list}} + \sqrt{mn}/\varepsilon)\)。最后，该团队展示了该算法在基于三角相关度量的聚类算法中的应用，并证明了任何 \(\varepsilon\)-三角割稀疏化器的大小下界为 \(\Omega(n/\varepsilon^2)\)。