Quantum Algorithms for Triangle Cut Sparsification

会议: ICML2026
arXiv: 2606.06287
代码: 无（纯理论论文）
领域: 学习理论 / 量子算法 / 图稀疏化
关键词: 三角形割稀疏化, 三角形枚举, 量子游走, Grover 搜索, motif 稀疏化

一句话总结

为「三角形割稀疏化」设计量子算法：先给出第一个有可证明加速的量子三角形枚举算法（融合重轻顶点划分、量子游走、Grover 三套路并取最优），再把它嵌进 Kapralov 等人的 motif 稀疏化框架并对后处理采样也做量子加速，从而以 \(\widetilde{O}(\sqrt{mn}/\varepsilon)\) 量级的额外开销构造出 \(\widetilde{O}(n/\varepsilon^2)\) 大小的 \(\varepsilon\)-三角形割稀疏子图，并配上匹配的 \(\Omega(n/\varepsilon^2)\) 大小下界。

研究背景与动机

领域现状：图稀疏化（spanner、cut sparsifier、spectral sparsifier）通过保留少量加权边来近似保持原图的关键结构，是大图算法和机器学习的基础工具。近年 Kapralov 等人（2022）提出 motif cut sparsifier——不再保持「边」横跨每个割的数量，而是保持某种固定子图（motif，如三角形）横跨每个割的加权数量，以刻画社交网络、推荐系统、图聚类里至关重要的高阶结构。

现有痛点：Kapralov 等人的框架虽然能做到线性大小（\(\widetilde{O}(n)\) 条边）的稀疏子图，但其经典实现有两个计算瓶颈：① 需要显式枚举所有三角形（triangle listing），代价高昂；② 每轮迭代要做 \(\widetilde{O}(m)\) 时间的后处理边采样（post-sampling）。这两步合起来主导了整体运行时间。

核心矛盾：高阶结构（三角形）带来表达力，但枚举高阶结构本身就贵——三角形枚举是细粒度复杂性里出了名的难题，经典最优界 \(\widetilde{O}(m^{4/3}+mt^{1/3})\) 被广泛认为在某些假设下是条件最优的。想加速稀疏化，就绕不开加速三角形枚举。

切入角度：量子计算已经在稀疏化上初露锋芒——Apers & De Wolf（2022）给出了第一个 \(\widetilde{O}(\sqrt{mn}/\varepsilon)\) 的量子谱稀疏化算法，Liu 等人（2025）把它推广到超图。但三角形割稀疏化这个高阶版本从未从量子视角研究过。同时，量子三角形检测（detection，只判断是否存在一个三角形）已经有 \(\widetilde{O}(n^{5/4})\) 的成熟结果，而量子三角形枚举（listing，列出全部 \(t\) 个）几乎是空白。作者认为这正是可以撬动的杠杆点。

核心 idea：把「量子三角形枚举」做成可证明加速的技术原语，再用它同时加速 motif 稀疏化框架的枚举阶段和后采样阶段——即「用量子枚举 + 量子采样替换经典枚举 + 经典采样」来加速三角形割稀疏化，并顺带给三角形聚类算法提速。

方法详解

整体框架

整篇工作沿用 Kapralov 等人「基于强度（strength-based）的 motif 稀疏化」流水线：把每个三角形当成一条超边，迭代地保留估计重要性高的边、对其余边做采样，最终得到 \(\widetilde{O}(n/\varepsilon^2)\) 大小的稀疏子图。瓶颈在「枚举」和「后采样」两个阶段，本文对这两阶段分别注入量子加速：

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入：加权图 G(V,E,w)<br/>QRAM 查询访问"] --> B["量子三角形枚举<br/>三套路并行取最优"]
    B --> B1["重轻顶点划分<br/>m + m^3/4 t^1/2"]
    B --> B2["量子游走<br/>n^5/4 t^7/12 + n^7/6 t^7/9"]
    B --> B3["Grover 直搜<br/>n^3/2 t^1/2"]
    B1 --> C["量子后采样<br/>找关键边 + 隐式采样"]
    B2 --> C
    B3 --> C
    C -->|迭代直到达到 O~(n/ε²) 大小| C
    C --> D["输出：ε-三角形割稀疏子图<br/>+ Ω(n/ε²) 匹配下界"]

其中量子三角形枚举（Q-TriangleListing，对应 Theorem 1.3）是核心技术贡献，它本身又是三套并行算法取最先终止者，得到运行时间

\[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).\]

最终稀疏化定理（Theorem 1.2）的总时间是 \(T_{\mathrm{q\text{-}list}}+\widetilde{O}(\sqrt{mn}/\varepsilon)\)。所有算法都假设输入图存放在量子可访问的经典存储（QRAM）里，支持度查询、邻居查询、点对查询三种相干查询。

关键设计

1. 重轻顶点划分：用度数阈值把三角形拆成两类各个击破

针对「直接枚举三角形太贵」的痛点，这条路把顶点按度数阈值 \(\Delta\) 分成重顶点 \(V_H=\{v:\deg(v)>\frac{9}{10}\Delta\}\) 和轻顶点 \(V_L=\{v:\deg(v)\le\frac{11}{10}\Delta\}\)（重叠区给度数估计留松弛，不影响正确性）。由握手引理 \(\sum_v\deg(v)=2m\)，重顶点数量至多 \(|V_H|\le\frac{20m}{9\Delta}\)。于是每个三角形要么至少含一个轻顶点、要么完全由重顶点构成，两类分别处理。

对每个轻顶点 \(v\)，其邻居对构成搜索空间 \(\binom{\deg(v)}{2}\)，用重复版 Grover 搜索列出所有过 \(v\) 的三角形，代价 \(\widetilde{O}(\deg(v)\sqrt{t_v})\)；处理完立刻删掉 \(v\) 及其边以保证每个三角形只被列一次。对全体轻顶点用 Cauchy–Schwarz 求和并代入 \(\sum_v\deg^2(v)\le 2m\Delta\)、\(\sum_v t_v\le 3t\)，得轻顶点阶段 \(\widetilde{O}(\sqrt{m\Delta t})\)。剩下纯重顶点诱导的三角形，对所有重顶点三元组直接重复 Grover 搜索，代价 \(\widetilde{O}((m/\Delta)^{3/2}t^{1/2})\)。令两项相等解出 \(\Delta=\sqrt{m}\)，总时间 \(\widetilde{O}(m+m^{3/4}t^{1/2})\)。在稀疏图上这一项最优，且只要 \(t\le m^{3/2}\)（对所有图都成立）它就不大于经典最优界 \(\widetilde{O}(m^{4/3}+mt^{1/3})\)，体现量子优势。

2. 两层量子游走：把三角形检测扩展成枚举且不重复

针对「三角形数量适中（moderate）时希望比划分法更快」的需求，这条路推广 Le Gall（2014）的量子三角形检测框架。分两阶段：预枚举（Pre-Listing） 随机采一个大小约 \(s\) 的顶点子集 \(S\)，用 Grover 列出所有含 \(S\) 中顶点的三角形，并把它们边上关联的三角形也一并列出、随后从 oracle 删除这些边。关键性质是：随机采样后，任意点对若不与 \(S\) 共享公共邻居，则它要么直接成边构成过 \(S\) 的三角形、要么根本不参与任何三角形——于是预枚举结束后，剩余三角形全部支撑在「不与 \(S\) 共邻」的点对集 \(\Delta_G(V,S)\) 上，且候选点对数从 \(n|X|^2\) 锐减到 \(\frac{n|X|^2}{s}\)。

穷举枚举（Exhaustive Listing） 阶段反复跑一个两层量子游走 Q-WalkSearch：外层在 Johnson 图 \(J(V,h)\) 上游走找含某剩余三角形一条边的子集，内层对固定 \(w\) 在 \(J(H,h^{2/3})\) 上游走检查 \(\Delta_G(H',w,S)\) 是否含真边。每找到一个新三角形就枚举其边上关联的全部三角形并删掉这三条边（用辅助比特做标准 oracle 掩码实现「删边」），直到再无三角形。难点在于界定外层游走里「被标记状态」的占比——作者不用经典的简单数边法，而是用组合打包论证：取一组两两边不相交的剩余三角形、抽出最大度较低的认证边集，再做二阶矩计算，从而在不假设三角形支撑边相互独立的情况下给出严格的标记占比下界。配合按估计 \(\hat t=\Theta(t)\) 分三段设定参数 \((s,h)\)，得 \(\widetilde{O}(n^{5/4}t^{7/12}+n^{7/6}t^{7/9})\)（Theorem 3.4）。这套设计避免了把检测当黑盒包一层，去掉量子组件就会失去多项式收益。

3. Grover 直搜 + 三路并行取最优：覆盖稠密多三角形区间并合成最终界

针对「稠密图、三角形丰富」的情形，第三条路直接对三元组用 Grover 搜索，得 \(\widetilde{O}(n^{3/2}t^{1/2})\)；它逼近 Grover 最优性（不可能再被改进超过对数因子），且在 \(t=\Theta(n^3)\) 极端下退化为 \(\Theta(n^3)\)——这是输出规模决定的、量子经典都绕不开的下界。最终的枚举算法 Q-TriangleListing（Theorem 1.3）把三套路并行跑、谁先终止用谁的输出，取三者最小值得到 \(T_{\mathrm{q\text{-}list}}\)。两个极端可作合理性检验：\(t=1\) 时退化为 \(\widetilde{O}(n^{5/4})\)，恰好匹配已知最优的量子三角形检测界；\(t=\Theta(n^3)\) 时为 \(\Theta(n^3)\)，是输出规模的硬下界。

4. 量子后采样：隐式编码采样决策，只在最后才显式取回幸存边

针对「每轮 \(\widetilde{O}(m)\) 后采样」这个第二瓶颈，作者把它也量子化。后采样的两步分别是「找关键边（critical edges，估计重要性超阈值的边）」和「对其余边采样」。第一步用上面的量子三角形枚举 + Grover 加速；第二步借鉴 Apers & De Wolf（2022）的技巧，不显式写出每条边的采样结果，而是把采样决策隐式编码，只在最后用量子搜索把幸存下来的边取回，从而把每轮后采样从 \(\widetilde{O}(m)\) 降到 \(\widetilde{O}(\sqrt{mn}/\varepsilon)\)。注意作者强调不能直接套量子超图稀疏化（把每个三角形当超边）——因为一条边可能同时出现在被保留和被丢弃的超边里，语义对不上，所以必须基于强度的 motif 框架重新设计。综合枚举与后采样，得最终 Theorem 1.2：以 \(T_{\mathrm{q\text{-}list}}+\widetilde{O}(\sqrt{mn}/\varepsilon)\) 时间构造出 \(\widetilde{O}(n/\varepsilon^2)\) 大小的 \(\varepsilon\)-三角形割稀疏子图。

损失函数 / 训练策略

本文为纯算法理论工作，无训练目标。正确性与运行时间均以「high probability（至少 \(1-\mathrm{poly}(1/n)\)）」给出，参数设定（如 \(\Delta=\sqrt{m}\)、分三段的 \((s,h)\)）由平衡各阶段代价导出；缺乏三角形总数 \(t\) 的精确值时用常数比例的「猜测调度（guessing schedule）」逐步逼近 \(\hat t=\Theta(t)\)。

实验关键数据

本文是理论论文，没有数值实验，核心「结果」是运行时间界与下界。下表把本文量子界与已知经典最优界对照（\(\omega<2.372\) 为矩阵乘法指数，假设 \(\omega=2\) 时简化）。

主结果：运行时间对比

任务	经典最优界	本文量子界	量子优势条件
三角形枚举（稀疏图）	\(\widetilde{O}(m^{4/3}+mt^{1/3})\)（\(\omega=2\)，被认为条件最优）	\(\widetilde{O}(m+m^{3/4}t^{1/2})\)	\(t\le m^{3/2}\)（对所有图成立）时恒不更大
三角形枚举（稠密图）	\(\widetilde{O}(n^2+nt^{2/3})\)（\(\omega=2\) 猜想下界）	\(\widetilde{O}(\min(n^{5/4}t^{7/12}+n^{7/6}t^{7/9},\ n^{3/2}t^{1/2}))\)	\(t\le n^{15/14}\) 时本文 \(\le\widetilde{O}(n^2)\)，匹配或更优
三角形割稀疏化（总时间）	\(\widetilde{O}(\min\{T_{\mathrm{c\text{-}list}},n^\omega\}+m)\)	\(T_{\mathrm{q\text{-}list}}+\widetilde{O}(\sqrt{mn}/\varepsilon)\)	枚举阶段 + 后采样 \(\widetilde{O}(m)\!\to\!\widetilde{O}(\sqrt{mn}/\varepsilon)\)

极端情形与下界

情形	本文结果	说明
\(t=1\)（仅一个三角形）	\(\widetilde{O}(n^{5/4})\)	匹配已知最优量子三角形检测界（Le Gall 2014）
\(t=\Theta(n^3)\)（最稠密）	\(\Theta(n^3)\)	输出规模硬下界，量子经典都绕不开
\(\widetilde{O}(n^{3/2}t^{1/2})\) 项	逼近 Grover 最优	无法再改进超过对数因子
稀疏子图大小下界	\(\Omega(n/\varepsilon^2)\)（Theorem 5.2）	首个专门针对三角形 motif 的匹配下界，证明本文 \(\widetilde{O}(n/\varepsilon^2)\) 近乎紧

关键发现

• 三套枚举算法各管一段区间：重轻划分管稀疏图、量子游走管三角形适中、Grover 直搜管稠密多三角形；并行取最优让 \(T_{\mathrm{q\text{-}list}}\) 在很宽的参数范围内都优于经典。
• 加速来自非平凡量子原语而非黑盒包装：作者明确指出去掉量子组件（量子游走、Grover、变代价搜索）就会失去全部多项式收益——这不是简单地把经典算法套一层 Grover。
• 下界与上界几乎对齐：\(t=1\) 接检测界、\(t=\Theta(n^3)\) 接输出界、稀疏子图大小 \(\Omega(n/\varepsilon^2)\) 匹配上界，理论上相当干净。
• 聚类应用直接受益：把量子三角形枚举原语嵌入基于三角形度量的谱聚类、PageRank 聚类（Benson & Leskovec 2016；Yin 等 2017）即得相应量子加速。

亮点与洞察

• 把「检测」升级为「枚举」是真功夫：从只判断存在性的 \(\widetilde{O}(n^{5/4})\) 检测，到列出全部 \(t\) 个且不重复，作者用「找到一个就枚举其边上关联三角形并删边」+ oracle 掩码保证进度且不重复，外加二阶矩打包论证界定标记占比——这套「检测→枚举」的扩展手法可迁移到其他子图（如 \(k\)-clique、其他 motif）的量子枚举。
• 后采样的隐式编码思想很可复用：不显式物化每条边的采样决策、只在最后用量子搜索取回幸存边，把 \(\widetilde{O}(m)\) 降到 \(\widetilde{O}(\sqrt{mn}/\varepsilon)\)——这是在「采样结果稀疏」场景下普适的量子省时模式。
• 为什么不能套超图稀疏化讲得很清楚：一条边可能同时属于被保留和被丢弃的超边，语义冲突，所以必须回到强度框架——这个负面观察本身就有价值，提醒后人 motif 稀疏化 ≠ 超图稀疏化。
• 三路并行取最优是工程化的优雅：不强求单一算法全区间最优，而是让三套各自最优的算法竞速，组合出全局 min 界。

局限与展望

• 依赖 QRAM 强假设：所有界都建立在量子可访问经典存储（QRAM）上，比只数 oracle 查询的纯电路模型更强；作者承认这是标准但更强的假设。
• 渐进而非实操：明确说不给出具体硬件交叉点（crossover），多项式优势只有在大规模容错量子计算机出现后、对超大图才相关——目前无法在真机上验证。
• 缺三角形枚举的量子下界：作者坦言目前没有三角形枚举的量子下界，因此无法判断 \(T_{\mathrm{q\text{-}list}}\) 各项是否已最优（仅 \(n^{3/2}t^{1/2}\) 项逼近 Grover 最优）。
• 稀疏子图大小下界只对三角形：\(\Omega(n/\varepsilon^2)\) 专门针对三角形 motif，是否能推广到一般 \(k\)-顶点 motif 仍开放。

相关工作与启发

• vs Kapralov et al. (2022)（经典 motif 稀疏化）：他们提出 strength-based 框架并做到线性大小，但枚举 + \(\widetilde{O}(m)\) 后采样是瓶颈；本文沿用其框架，对两个瓶颈都做量子加速，并补上专门的 \(\Omega(n/\varepsilon^2)\) 匹配下界。
• vs Apers & De Wolf (2022)（量子谱稀疏化）：他们给出第一个 \(\widetilde{O}(\sqrt{mn}/\varepsilon)\) 量子谱（边）稀疏化并提出「能否推广到更广稀疏化任务」的开问；本文正是把这条路推到三角形这一高阶 motif，后采样的隐式采样技巧也直接借自他们。
• vs Liu et al. (2025)（量子超图稀疏化）：他们做超图谱稀疏化 \(\widetilde{O}(r\sqrt{mn}/\varepsilon)\)；本文指出不能直接把三角形当超边套用（边会同时落入保留/丢弃超边），必须另起炉灶。
• vs Le Gall (2014)（量子三角形检测）：他给出 \(\widetilde{O}(n^{5/4})\) 检测；本文把这套量子游走框架从「检测」扩展到「枚举」，是核心技术增量。
• vs Björklund et al. (2014)（经典三角形枚举）：经典最快枚举 \(\widetilde{O}(n^\omega+\ldots)\) / 稀疏图 \(\widetilde{O}(m^{4/3}+mt^{1/3})\)（被认为条件最优）；本文量子界在很宽区间内匹配或超越。

评分

• 新颖性: ⭐⭐⭐⭐⭐ 首个可证明加速的量子三角形枚举 + 首个量子三角形割稀疏化 + 首个三角形 motif 专属下界
• 实验充分度: ⭐⭐⭐⭐ 纯理论无数值实验，但运行时间界、极端检验与匹配下界相当完整自洽
• 写作质量: ⭐⭐⭐⭐⭐ 技术概览把三套路与瓶颈拆解得非常清楚，证明骨架与参数设定交代到位
• 价值: ⭐⭐⭐⭐ 量子图算法与高阶结构稀疏化的扎实推进，受 QRAM 与远期硬件假设限制，短期偏理论价值

相关论文

• [ICML 2026] Simple Algorithms for Bad Triangle Transversals with Applications to Correlation Clustering
• [ICML 2026] Matroid Algorithms Under Size-Sensitive Independence Oracles
• [ICML 2026] Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits
• [ICLR 2026] Transformers as Unsupervised Learning Algorithms: A study on Gaussian Mixtures
• [ICLR 2026] Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion