{"ID":3083658,"CreatedAt":"2026-06-05T06:46:15.197025399Z","UpdatedAt":"2026-06-07T09:00:11.459356253Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.06287","arxiv_id":"2606.06287","title":"Quantum Algorithms for Triangle Cut Sparsification","abstract":"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 \\emph{triangle cut sparsification}, which aims to reduce the graph size while approximately preserving triangle counts across every cut. We investigate \\emph{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}\\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)$, 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 $\\widetilde{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 $Ω(n/\\varepsilon^2)$ on the size of any $\\varepsilon$-triangle cut sparsifiers.","short_abstract":"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 \\emph{triangle cut sparsification}, which aims to reduce the graph size while approximately preserving triangle co...","url_abs":"https://arxiv.org/abs/2606.06287","url_pdf":"https://arxiv.org/pdf/2606.06287v1","authors":"[\"Shan Jiang\",\"Pan Peng\"]","published":"2026-06-04T15:25:34Z","proceeding":"quant-ph","tasks":"[\"quant-ph\",\"cs.DS\"]","methods":"[]","has_code":false}