{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreie2sypwxkuaez3uhcmx2uwc5llc6fwrecctdlzeoqf3rrdo35t5yi",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mnkrgibyhgn2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.06287v1",
  "publishedAt": "2026-06-05T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Shan Jiang",
    "Pan Peng"
  ],
  "textContent": "**Authors:** Shan Jiang, Pan Peng\n\nTriangles 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.",
  "title": "Quantum Algorithms for Triangle Cut Sparsification"
}