{
  "annotation_id": "b0ea6845-6965-4537-9440-177c0b6d7b31",
  "date_created": "2026-03-02T18:02:03.346000Z",
  "date_modified": "2026-03-02T18:02:03.346000Z",
  "file_hash": "6030cd9432c071477aa6a1e02909d4ca16fc57b37bfd4e5a31a168a20cb2dafe",
  "private": false,
  "record": {
    "abstract": "We present two new quantum algorithms that either find a triangle (a copy of\n$K_{3}$) in an undirected graph $G$ on $n$ nodes, or reject if $G$ is triangle\nfree. The first algorithm uses combinatorial ideas with Grover Search and makes\n$\\tilde{O}(n^{10/7})$ queries. The second algorithm uses $\\tilde{O}(n^{13/10})$\nqueries, and it is based on a design concept of Ambainis~\\cite{amb04} that\nincorporates the benefits of quantum walks into Grover search~\\cite{gro96}. The\nfirst algorithm uses only $O(\\log n)$ qubits in its quantum subroutines,\nwhereas the second one uses O(n) qubits. The Triangle Problem was first treated\nin~\\cite{bdhhmsw01}, where an algorithm with $O(n+\\sqrt{nm})$ query complexity\nwas presented, where $m$ is the number of edges of $G$.",
    "arxiv_id": "quant-ph/0310134",
    "authors": [
      "Frederic Magniez",
      "Miklos Santha",
      "Mario Szegedy"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "Quantum Algorithms for the Triangle Problem",
    "url": "https://arxiv.org/abs/quant-ph/0310134"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "e1a0e168-2134-4f41-af48-889f6153e0c3",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}