Quantum Algorithms for Triangle Cut Sparsification

Triangles capture higher-order structures in graphs and are fundamental to applications such as clustering and network analysis. To enable efficient use of such structures at scale, we study the problem of triangle cut sparsification, which aims to reduce the graph size while approximately preserving triangle counts across every cut. We investigate quantum algorithms for this problem, using triangle listing as our main technical ingredient. In particular, we present a quantum algorithm for triangle listing that, for a graph with $n$ vertices, $m$ edges, and $t$ triangles, runs in time $T_{\mathrm{q\text{-}list}} =\widetilde{O}\left(\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})\right)$, improving upon the best known classical bounds over a broad range of parameters. Our algorithm is based on a heavy–light vertex partition and an extension of triangle detection via quantum walks and Grover search. Leveraging this result, we design a quantum algorithm for constructing $\varepsilon$-triangle cut sparsifiers of size $\tilde{O}(n/\varepsilon^2)$ in time $\widetilde{O}(T_{\mathrm{q\text{-}list}} + \sqrt{mn}/\varepsilon)$. Finally, we demonstrate applications to clustering algorithms based on triangle-related measures and prove a lower bound of $\Omega(n/\varepsilon^2)$ on the size of any $\varepsilon$-triangle cut sparsifiers.

This paper studies how to compress large graphs while preserving information carried by triangles, which represent higher-order relationships among three vertices. We develop quantum algorithms for triangle listing and use them to construct small triangle cut sparsifiers more efficiently. Using our developed quantum algorithms can support downstream tasks such as triangle-based graph clustering. The results show that quantum techniques can provide theoretical speedups for higher-order graph sparsification.